Cut-Based Conflict Analysis in Mixed Integer Programming

doi:10.1287/ijoc.2024.0999

Cut-Based Conflict Analysis in Mixed Integer Programming

2025-11-01

0

PRE

AI

DOI：10.1287/ijoc.2024.0999

Original

Original request for help

Save

Abstract

En 中文

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 Chvatal-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.

Keywords:

mixed integer linear programming

infeasibility analysis

conflict analysis

pseudo-Boolean solving and optimization

cutting planes proof system

Cut-Based Conflict Analysis in Mixed Integer Programming

Abstract

Journal

Organization