Optimization Online


Reoptimization Techniques for MIP Solvers

Gerald Gamrath(gamrath***at***zib.de)
Benjamin Hiller(hiller***at***zib.de)
Jakob Witzig(witzig***at***zib.de)

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.

Keywords: reoptimization, branch-and-bound, MIP, IP, warmstart

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Optimization Software and Modeling Systems (Problem Solving Environments )

Category 3: Integer Programming (0-1 Programming )

Citation: ZIB Report 15-24, Zuse Institut Berlin, Takustr. 7, D-14195 Berlin, Germany, April 2015

Download: [PDF]

Entry Submitted: 05/07/2015
Entry Accepted: 05/07/2015
Entry Last Modified: 05/07/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society