Optimization Online


Conflict-Driven Heuristics for Mixed Integer Programming

Jakob Witzig(witzig***at***zib.de)
Ambros Gleixner(gleixner***at***zib.de)

Abstract: Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.

Keywords: mixed integer programming; primal heuristics; conflict analysis; branch-and-bound

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: ZIB-Report 19-08, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany, 2019

Download: [PDF]

Entry Submitted: 02/07/2019
Entry Accepted: 02/07/2019
Entry Last Modified: 02/07/2019

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