7496
eng
reportzib
0
--
2019-11-06
--
Computational Aspects of Infeasibility Analysis in Mixed Integer Programming
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.
1438-0064
urn:nbn:de:0297-zib-74962
false
true
Jakob Witzig
Jakob Witzig
Timo Berthold
Stefan Heinz
ZIB-Report
19-54
Integer programming
Mixed integer programming
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Heinz, Stefan
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
BEAM-ME
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7496/supplement.pdf
https://opus4.kobv.de/opus4-zib/files/7496/ZR-19-54__Witzig_Berthold_Heinz__Computational_Aspects_of_Infeasibility_Analysis_in_MIP.pdf