Optimization Online


Conflict-Free Learning for Mixed Integer Programming

Jakob Witzig(witzig***at***zib.de)
Timo Berthold(timoberthold***at***fico.com)

Abstract: Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.

Keywords: conflict analysis; dual proof analysis; mixed integer programming; no-good learning; solution learning

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

Citation: ZIB-Report 19-59, Zuse Institute Berlin, Takustr. 7, 14195 Berlin

Download: [PDF]

Entry Submitted: 12/02/2019
Entry Accepted: 12/02/2019
Entry Last Modified: 12/02/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