@inproceedings{GamrathHillerWitzig2015, author = {Gamrath, Gerald and Hiller, Benjamin and Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, volume = {9125}, edition = {Experimental Algorithms, Lecture Notes in Computer Science}, publisher = {Springer}, isbn = {978-3-319-20086-6}, doi = {10.1007/978-3-319-20086-6_14}, pages = {181 -- 192}, year = {2015}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @misc{GamrathBertholdHeinzetal.2017, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, issn = {1438-0064}, doi = {10.1007/s12532-019-00159-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65387}, year = {2017}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{BertholdHendelKoch2016, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {The Three Phases of MIP Solving}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1392519}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61607}, year = {2016}, abstract = {Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.}, language = {en} } @misc{MaherDesaulniersSoumis2015, author = {Maher, Stephen J. and Desaulniers, Guy and Soumis, Francois}, title = {The tail assignment problem with look-ahead maintenance constraints}, issn = {1438-0064}, doi = {10.1016/j.ejor.2017.06.041}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56717}, year = {2015}, abstract = {The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to be operated the next day. The aim of this paper is to develop an operationally flexible tail assignment that satisfies short-range---within the next three days---aircraft maintenance requirements and performs the aircraft/flight gate assignment for each input line-of-flight. While maintenance plans commonly span multiple days, the related tail assignment problems can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by extending the one-day routes aircraft maintenance routing approach to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A mathematical model is presented that integrates the gate assignment and maintenance planning problems. To increase the satisfaction of maintenance requirements, an iterative algorithm is developed that modifies the fixed lines-of-flight provided as input to the tail assignment problem. The tail assignment problem and iterative algorithm are demonstrated to effectively satisfy maintenance requirements within appropriate run times using input data collected from three different airlines.}, language = {en} } @article{GamrathKochMartinetal.2015, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in presolving for mixed integer programming}, volume = {7}, journal = {Mathematical Programming Computation}, number = {4}, doi = {10.1007/s12532-015-0083-5}, pages = {367 -- 398}, year = {2015}, abstract = {This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 \% on affected instances while not degrading the performance on the remaining problems.}, language = {en} }