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 constraints. 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 generalized for MIP and integrated in MIP solving. 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 Chvátal-Gomory-based method in pseudo-Boolean solving.
We implement our new conflict analysis algorithm in the open-source MIP solver SCIP and evaluate it on a large and diverse set of MIP instances from MIPLIB 2017.

Cutting planes are one of the fundamental pieces for efficiently solving mixed integer linear optimization problems. Gurobi Optimizer 11 implements 21 different types of cutting plane separation algorithms.

We will discuss some of the most recent techniques that were added to our algorithm. We will briefly sketch the ideas behind them and present some computational results on a large set of models.

In this talk, we introduce the concept of discounted pseudocosts, inspired by the notion of discounted total reward in reinforcement learning, and explore their application in mixed-integer linear programming (MILP). Pseudocosts traditionally estimate the change in the objective function value resulting from changes in variable bounds during the branch-and-bound process. By integrating ideas from reinforcement learning, we propose a novel approach incorporating a forward-looking perspective into pseudocost estimation.

We present the motivation behind discounted pseudocosts and discuss how they represent the anticipated reward for branching after one level of exploration in the MILP problem space. Leveraging this concept, we aim to guide the branch-and-bound algorithm towards more promising regions of the solution space, potentially improving its efficiency and convergence rate.

Furthermore, we present the results of our initial experiments conducted to evaluate the effectiveness of discounted pseudocosts in MILP solvers. Through a series of computational experiments on MIPLIB 2017 benchmark instances, we demonstrate the impact of incorporating discounted pseudocosts on the performance of the branch-and-bound algorithm. Our findings suggest that this approach yields promising results, showcasing its potential to enhance branching strategies and accelerate the solution process for challenging MILP problems.

Domain propagation of variables throughout the solution process of a branch-and-bound algorithm is a powerful tool that is typically implemented in sophisticated mixed integer programming solvers. The variety of techniques spreads over combinatorial propagation, constraint propagation, and reduced cost strengthening. We present an approach that extends the idea of the latter by rotating the objective to retrieve more information about the underlying polytope. This leads to an increased number of fixed variables compared to simply applying reduced cost strengthening, especially since it is applicable to both, basic and non-basic variables. A careful analysis of the parameters used by our algorithm allows us to detect dead-ends early on and therefore restricts the running time. This approach can be seen as a heuristic look-ahead branching and is related to the estimation of the strong branching scores.
Our computational study on the MIPLIB instances shows that the integration of this technique in a branch-and-bound framework can lead to an improvement of the running time. Additionally, we observe a large benefit for the Vehicle Routing Problem with Heterogeneous Time Windows.