90C10 Integer programming
Refine
Year of publication
- 2012 (9) (remove)
Document Type
- ZIB-Report (9)
Language
- English (9)
Has Fulltext
- yes (9)
Is part of the Bibliography
- no (9)
Keywords
Institute
We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to
feasible rosters for one month. We present computational results in a
case-study on a German subnetwork which documents the practicability of our approach.
This paper provides a generic formulation for rolling stock planning
problems in the context of intercity passenger traffic. The main contributions
are a graph theoretical model and a Mixed-Integer-Programming
formulation that integrate all main requirements of the considered
Vehicle-Rotation-Planning problem (VRPP). We show that it is
possible to solve this model for real-world instances provided by our
industrial partner DB Fernverkehr AG using modern algorithms and
computers.
Rapid Branching
(2012)
We propose rapid branching (RB) as a general branch-and-bound heuristic
for solving large scale optimization problems in traffic and transport.
The key idea is to combine a special branching rule and a greedy node selection
strategy in order to produce solutions of controlled quality rapidly
and efficiently. We report on three successful applications of the method
for integrated vehicle and crew scheduling, railway track allocation, and
railway vehicle rotation planning.
Duty Scheduling Templates
(2012)
We propose duty templates as a novel concept to produce similar duty
schedules for similar days of operation in public transit. Duty templates
can conveniently handle various types of similarity requirements, and
they can be implemented with ease using standard algorithmic techniques.
They have produced good results in practice.
Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade.
We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models,
which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP
are technologies that should be considered along with CP for solving scheduling problems.
Vehicle rotation planning is a fundamental problem in
rail transport. It decides how the railcars, locomotives, and
carriages are operated in order to implement the trips of the
timetable. One important planning requirement is operational
regularity, i.e., using the rolling stock in the same way on every
day of operation. We propose to take regularity into account by
modeling the vehicle rotation planning problem as a minimum cost
hyperassignment problem (HAP). Hyperassignments are generalizations
of assignments from directed graphs to directed hypergraphs.
Finding a minimum cost hyperassignment is
NP-hard.
Most instances arising from regular vehicle rotation planning, however, can
be solved well in practice. We show that, in particular, clique
inequalities strengthen the canonical LP relaxation substantially.