Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Reoptimization Techniques in MIP Solvers

Please always quote using this URN: urn:nbn:de:0297-zib-54375
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Jakob WitzigORCiD, Gerald GamrathORCiD, Benjamin HillerORCiD
Document Type:ZIB-Report
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:J. Computer Applications
Date of first Publication:2015/09/04
Series (Serial Number):ZIB-Report (15-24)
ISSN:1438-0064
Published in:Lecture Notes in Computer Science
Preprint:urn:nbn:de:0297-zib-54375
DOI:https://doi.org/10.1007/978-3-319-20086-6_14
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.