Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Reoptimization Techniques for MIP Solvers
verfasst von : Gerald Gamrath, Benjamin Hiller, Jakob Witzig
Erschienen in: Experimental Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.