Conflict analysis has been successfully generalized from Boolean
satisfiability (SAT) solving to mixed integer programming (MIP)
solvers, but although MIP solvers operate with general linear
inequalities, the conflict analysis in MIP has been limited to
reasoning with the more restricted class of clausal constraint.
This is in contrast to how conflict analysis is performed in
so-called pseudo-Boolean solving, where solvers can reason directly
with 0-1 integer linear inequalities rather than with
clausal constraints extracted from such inequalities.
In this work, we investigate how pseudo-Boolean conflict analysis
can be integrated in MIP solving, focusing on 0-1
integer linear programs (0-1 ILPs). Phrased in MIP
terminology, conflict analysis can be understood as a sequence of
linear combinations and cuts. We leverage this perspective to design
a new conflict analysis algorithm based on mixed integer rounding
(MIR) cuts, which theoretically dominates the state-of-the-art
division-based method in pseudo-Boolean solving.
We also report results from a first proof-of-concept implementation
of different pseudo-Boolean conflict analysis methods in the
open-source MIP solver SCIP. When evaluated on a large and
diverse set of 0-1 ILP instances from MIPLIB 2017,
our new MIR-based conflict analysis outperforms both previous
pseudo-Boolean methods and the clause-based method used in MIP.
Our conclusion is that pseudo-Boolean conflict analysis in MIP is a
promising research direction that merits further study, and that it
might also make sense to investigate the use of such conflict
analysis to generate stronger no-goods in constraint programming.
Article
View Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning