Cut-Based Conflict Analysis in Mixed Integer Programming
- 12 November 2025
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Abstract
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, and this 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 Solving Constraint Integer Programs (SCIP), testing it on a large and diverse set of MIP instances from MIPLIB2017. 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. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Research Campus Modal funded by the German Federal Ministry of Research, Technology, and Space [Grants 05M14ZAM, 05M20ZBM]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0999 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0999 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Computational aspects of infeasibility analysis in mixed integer programmingMathematical Programming Computation, 2021
- Learn to relax: Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven searchConstraints, 2021
- MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming libraryMathematical Programming Computation, 2021
- Knapsack polytopes: a surveyAnnals of Operations Research, 2019
- Cutting to the ChaseJournal of Automated Reasoning, 2013
- Generalized resolution and cutting planesAnnals of Operations Research, 1988
- On the complexity of cutting-plane proofsDiscrete Applied Mathematics, 1987
- Fourier-Motzkin elimination extension to integer programming problemsJournal of Combinatorial Theory, Series A, 1976
- Analysis of mathematical programming problems prior to applying the simplex algorithmMathematical Programming, 1975
- Edmonds polytopes and a hierarchy of combinatorial problemsDiscrete Mathematics, 1973