For almost two decades, mixed integer programming (MIP) solvers have used graph-
based conflict analysis to learn from local infeasibilities during branch-and-bound
search. In this paper, we improve MIP conflict analysis by instead using reasoning
based on cuts, inspired by the development of conflict-driven solvers for pseudo-
Boolean optimization. Phrased in MIP terminology, this type of conflict analysis
can be understood as a sequence of linear combinations, integer roundings, and
cut generation. We leverage this MIP perspective to design a new conflict analysis
algorithm based on mixed integer rounding cuts, which theoretically dominates
the state-of-the-art method in pseudo-Boolean optimization using Chvátal-Gomory
cuts. Furthermore, we extend this cut-based conflict analysis from pure binary
programs to mixed binary programs and—in limited form—to general MIP with
also integer-valued variables. We perform an empirical evaluation of cut-based
conflict analysis as implemented in the open-source MIP solver SCIP, testing it on
a large and diverse set of MIP instances from MIPLIB 2017. Our experimental
results indicate that the new algorithm improves the default performance of SCIP
in terms of running time, number of nodes in the search tree, and the number of
instances solved.
Article
View Cut-based Conflict Analysis in Mixed Integer Programming