90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2019 (12) (remove)
Document Type
- ZIB-Report (11)
- Doctoral Thesis (1)
Language
- English (12)
Is part of the Bibliography
- no (12)
Keywords
- Periodic Event Scheduling Problem (3)
- Periodic Timetabling (3)
- MINLP (2)
- ASTS orientations (1)
- Balanced Cuts (1)
- Balanced Hypergraphs (1)
- Column Generation (1)
- Crew Planning (1)
- Cutting planes (1)
- Factors (1)
Institute
- Mathematical Optimization (12) (remove)
We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant.
Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances.
It is implemented in the MIP solver SCIP and will be available in future releases.
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.