90C11 Mixed integer programming
Refine
Year of publication
- 2010 (5) (remove)
Document Type
- ZIB-Report (4)
- Master's Thesis (1)
Language
- English (5)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Keywords
- Fallstudie (1)
- IP (1)
- MIP (1)
- MIPLIB (1)
- Mixed Integer Programming (1)
- Netzwerkaggregation (1)
- ParaSCIP (1)
- Problem Instances (1)
- Simplon Korridor (1)
- Simplon corridor (1)
Institute
Generic Branch-Cut-and-Price
(2010)
MIPLIB 2010
(2010)
This paper reports on the fifth version of the Mixed Integer Programming Library.
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.
This includes the main benchmark test set of 87 instances, which
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to
test the accuracy of provided solutions using exact arithmetic.
Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.
This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters.
We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure.