Split cuts from sparse disjunctions

Abstract

Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the strength of split cuts that exploit sparsity. In particular, we show that restricting ourselves to sparse disjunctions—and furthermore, ones that have small disjunctive coefficients—still leads to a significant portion of the total gap closed with arbitrary split cuts. We also show how to exploit sparsity structure that is implicit in the MIP formulation to produce splits that are sparse yet still effective. Our results indicate that one possibility to produce good split cuts is to try and exploit such structure.

Appendix

1.1 Effect of heuristic features in computation

In order to examine the effect of some features and modifications we introduced to our separation routine, we ran the code on MIPLIB 3.0 instances with $M = +\infty$ and $U = 100$. We set the global time limit to an hour, and disabled the following features one at a time:

• cut strengthening (cut_str_off);

• stabilizing objective (stb_obj_off);

• set covering (set_cov_off).

We then plotted, for each scenario, the number of instances on which at least $x\%$ integrality gap was closed, for $x \in \{10, 20, \ldots , 90\}$. As shown in Fig. 9, the additional features indeed helped to obtain better results.

Among the three heuristics compared, using set covering to impose partial orthogonality between split cuts plays the most important role. The advantage of stabilizing objective is also evident. Note that, these results were obtained with a bound $U = 100$ already imposed on the disjunction coefficients. We thus expect to observe a more dramatic gain from stabilized objective, had we chosen a larger bound U to begin with. Table 7 shows the average gap closed in each computational setting. Note that we were able to close significantly more integrality gap when all features were used (default).

Fig. 9

Effect of heuristic features

Table 7 Average gap closed under different settings

Table 8 Gap closed for the full split closure under the original and the modified MILP($\theta$)

Table 9 Percentage of nonzero cut coefficients, before lifting, that (i) overlap with nonzero split coefficients (corr_n) (ii) overlap with the block where nonzero split coefficients come from (corr_b)

1.2 Gap closed for the full split closure under a modified separation routine

Our original implementation for the separation of arbitrary split cuts (with bounds $U = 100$ on disjunction coefficients) essentially finds a feasible solution to MILP($\theta$) whose objective value is less than a preset cut violation threshold $\epsilon < 0$. In theory, the same result can be achieved by adding the requirement that the objective value be less than $\epsilon$, $s^\top {\hat{x}} - \theta (\pi ^\top {\hat{x}} - \pi _0) < \epsilon$, as a constraint in MILP($\theta$), and then finding a feasible solution. Furthermore, in order to encourage some sparsity in split disjunctions, we can introduce a new objective function into MILP($\theta$), thus obtaining the following modified MILP($\theta$):

$$\begin{aligned} \begin{aligned} \min \;\;&\sum _{j=1}^p r_j \\ \text{ s.t. }&s^\top {\hat{x}} - \theta (\pi ^\top {\hat{x}} - \pi _0) < \epsilon \\&-Ur_j \le \pi _j \le Ur_j, \quad j = 1,2,\ldots ,p \\&{\texttt {plus original constraints of MILP(}}\theta {\texttt {)}} \end{aligned} \end{aligned}$$

Although, in theory, this modified formulation of MILP($\theta$) should produce the same results, provided that all the other computational parameters/heuristics are set to be the same, in practice the modified MILP($\theta$) could lead to very different results. In particular, we ran the modified separation routine with $U = 100$ as an approximation to the full split closure, and compare the results with those obtained from our original implementation. We set a global time limit to 24 h. As shown in Table 8, with the modified formulation of MILP($\theta$), we were able to close much more integrality gap on average within the same time limit.

1.3 Effect of split sparsity pattern on cut sparsity pattern

Table 9 presents the results discussed in Sect. 4 on how sparsity of the cuts and splits are related. Results of this table are for $M=10$ and $U=1$ parameters only.