Optimization Online


Computational Aspects of Infeasibility Analysis in Mixed Integer Programming

Jakob Witzig(witzig***at***zib.de)
Timo Berthold(timoberthold***at***fico.com)
Stefan Heinz(heinz***at***gurobi.coom)

Abstract: The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.

Keywords: mixed integer programming, conflict analysis, dual proof analysis, conflict graph analysis

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

Citation: ZIB-Report 19-54, Zuse Instite Berlin, Takustr. 7, 14195 Berlin, 2019

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