Generalized coefficient strengthening cuts for mixed integer programming

Abstract

Cutting plane methods are an important component in solving the mixed integer programming (MIP). By carefully studying the coefficient strengthening method, which is originally a presolving method, we are able to generalize this method to generate a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. The invariant property of the GCS inequalities is established under bound substitutions. Furthermore, we develop a separation algorithm for finding the violated GCS inequalities for a general mixed integer set. The separation algorithm is proved to have the polynomial time complexity. Extensive numerical experiments are made on standard MIP test sets, which demonstrate the usefulness of the resulting GCS separator.

1 Introduction

Consider the mixed integer programming (MIP) of the form

$$\begin{aligned} \underset{x}{\text {min}}\quad&c^T x \nonumber \\ \text {s.t.} \quad&Ax \le \beta \nonumber \\&l \le x \le u \nonumber \\&x \in \mathbb {Z}^p\times \mathbb {R}^{n-p}, \end{aligned}$$

(1)

where $A\in \mathbb {Q}^{m\times n}$ is a rational matrix, $c\in \mathbb {Q}^{n}$, $\beta \in \mathbb {Q}^{m}$ and $l, \, u \in \mathbb {Z}^{p}\times \mathbb {Q}^{n-p}$.

Cutting plane methods, which were proposed in [1] more than 50 years ago, have become one of the indispensable ingredients for solving MIP. As they can automatically improve the formulation of the original problem, cutting plane methods are contained in state of the art MIP solvers. General cutting planes, which do not require any knowledge about the problem structure, include Gomory Mixed Integer (GMI) Cuts [1], Mixed Integer Rounding (MIR) Cuts [2], Strong Chvátal–Gomory Cuts [3], Zero-half Cuts [4], Implied Bound Cuts [5], Clique Cuts [6, 7] and Disjunctive Cuts [8]. For special cutting planes, which make use of the problem structure, we have Knapsack Cover Cuts [6, 9], Flow Cover Cuts [11, 12], Flow Path Cuts [10], GUB Cover Cuts [13], Multi-commodity Flow Cuts [14], etc. The article [15] studied the impact of cutting plane methods in the commercial MIP solver CPLEX [16] and a 6.1$\times$ speedup is concluded on the set of test instances which required at least 10 s to solve by at least one version of the solvers.

Another key ingredient for solving MIP is the presolving method. It contains a set of routines that reduce the size of problem and strengthen the formulation of a given model. See [17] for a good survey about presolving methods. Here we just mention that the coefficient strengthening method [6, 18, 19] is one of the presolving methods and attempts to repair a bad formulation of the original problem (see also Sect. 2).

Although the coefficient strengthening method is a presolving method, we are able to generalize this method to generate the so-called generalized coefficient strengthening (GCS) inequality. Specifically, the GCS inequality is derived based on the general mixed integer set

$$\begin{aligned} M_{I} = M\cap (\mathbb {Z}^p \times \mathbb {R}^{n-p}), \end{aligned}$$

(2)

where M is the relaxation set

$$\begin{aligned} M = \{x \in \mathbb {R}^{n}: a^T x \le b, \ l\le x \le u \}. \end{aligned}$$

(3)

Here $a^T = {(a_1,a_2,a_3, \ldots ,a_n)}$ is any row of A and b is the corresponding right hand side. We show that GCS inequalities are invariant under bound substitutions. Furthermore, by analyzing variables bounds and utilizing the violated information, we are able to generalize the idea of [20] to develop a separation algorithm for finding GCS inequalities for the general mixed integer set $M_I$. The separation algorithm is proved to have the polynomial time complexity. Our numerical experiments demonstrated the usefulness of the resulting GCS separator.

Here we should notice that in [21], the authors considered a special case of $M_I$, that is

$$\begin{aligned} M_I^{(0)} = \{ (x,y)\in \mathbb {R}^n \times \mathbb {Z}: \sum _{i=1}^{n} x_i \le Dy, ~0 \le x \le u, ~y\ge 0\}, \end{aligned}$$

(4)

where $D>0$. They studied the convex hull of $M_I^{(0)}$ and derived an exponential family of valid inequalities, called residual capacity inequalities. It will be shown in Sect. 3 that such residual capacity inequalities are special GCS inequalities. Furthermore, a linear time separation algorithm is presented in [20] for finding the violated residual capacity inequalities. The separation algorithm proposed in this paper is based on [20], but can handle arbitrary variables bounds and arbitrary coefficients.

This paper is arranged as follows. In Sect. 2, we review the coefficient strengthening method. In Sect. 3, we extend the idea of the coefficient strengthening method by using more redundant information of $M_I$, which leads to the family of GCS inequalities. We show that GCS inequalities are invariant under bound substitutions. In Sect. 4, we first discuss the importance of infinite bounds for generating GCS inequalities. Then a polynomial time separation algorithm is presented to find the violated cuts. In Sect. 5, we test the effectiveness of the GCS cuts by inserting it as a separator in the open source solver SCIP [22]. Computational results on the test sets MIPLIB 3.0 [23], 2003 [24] and 2010 [25] are presented. Finally, in Sect. 6, we draw some conclusions and give some directions of future research.

Throughout this paper, we assume that the data is rational. Without loss of generality, we assume that $a_i \ne 0$ for all $1\le i \le n$ since if $a_i = 0$, $x_i$ can be dropped. Let $N := \{1,2,3,\cdots ,n\}$ and $I:=\{ 1,2,3,\ldots ,p \}$ be the index set of all variables and integer variables, respectively. We denote $\overline{\alpha }$ be the maximal activity of $a^Tx$ which defined as $\overline{\alpha } \, := \max \{a^Tx: \ l\le x\le u\} = \sum _{i: \,a_i>0} a_i u_i+\sum _{i: \,a_i<0} a_i l_i$. The inequality $\pi ^T x \le \pi _0$ is called a valid inequality for $M_I$ if it is satisfied by all points in $M_I$. Given any valid inequality $\pi ^T x \le \pi _0$ for $M_I$, we say $\pi ^T x \le \pi _0$ dominates $a^Tx \le b$ on M if $M':=\{ x\in \mathbb {R}^n:\pi ^Tx\le \pi _0 ,~ l\le x \le u \} \subseteq M$. Moreover, if $M' \subsetneq M$, then $\pi ^T x \le \pi _0$ strictly dominates $a^Tx \le b$ on M.

2 Coefficient strengthening method

In this section, we review the coefficient strengthening method [6, 18, 19]. The basic idea of the coefficient strengthening method is to change the coefficient of one integer variable and the right hand side via the redundant information so that the relaxation set M [as defined in (3)] is tighter without affecting the mixed integer set $M_I$. In this case, the constraint will become redundant if the corresponding variable does not take the value of the lower or upper bound. The details of the method is described in the following proposition. A proof is presented for completeness.

Proposition 1

Let $M_I$ be the mixed integer set in (2). For $a_j > 0, \ j\in I$, if $0< \overline{\alpha } -b < a_j$, then $a'^Tx\le b'$ is valid for $M_I$, where

$$\begin{aligned} \left\{ \begin{aligned} a'_i&= a_i, \qquad i\ne j, \\ a'_{j}&= \overline{\alpha } - b , \\ b'&= b - (a_j - a'_j)u_j. \end{aligned} \right. \end{aligned}$$

Furthermore, $a'^T x \le b'$ strictly dominates $a^Tx \le b$ on M.

Proof

Notice that $0<a'_j < a_j$. Given any point $x' \in M_I$, consider the following two cases.

• (i) $x'_j \in M_I \cap \{x \in \mathbb {R}^n: \ x_j \le u_j -1 \}$. In this case, we have that

  $$\begin{aligned} \begin{array}{rcl} a'^Tx' &{} \le &{} \overline{\alpha } - a_ju_j + a'_jx'_j \le \overline{\alpha } -a_j u_j + a'_j (u_j -1 ) \\ &{} = &{} \overline{\alpha } - (a_j-a'_j)u_j + b - \overline{\alpha } =b', \end{array} \end{aligned}$$

  where the first inequality follows from the definition of $\overline{\alpha } = \sum _{i: \,a_i>0} a_i u_i+\sum _{i: \,a_i<0} a_i l_i$.

• (ii) $x'_j \in M_I \cap \{x \in \mathbb {R}^n: \ x_j = u_j \}$. In this case, it follows that

  $$\begin{aligned} a'^Tx' = a^Tx' + (a'_j - a_j)x_j \le b + (a'_j - a_j)u_j = b'. \end{aligned}$$

Combining the above, we know that $a'^Tx \le b'$ is valid for $M_I$.

For the second part, we first prove that $\{x\in \mathbb {R}^n: a'^Tx \le b', \ l \le x \le u \} \subseteq M$.

In fact, for any point $x'$ with $a'^Tx' \le b'$ and $l\le x' \le u$, it follows that

$$\begin{aligned} a^Tx' = a'^Tx' + (a_j - a'_j)x'_j \le b' + (a_j - a'_j)u_j = b. \end{aligned}$$

It remains to show that there exists $x'$ with $l \le x' \le u$ such that $a^Tx' \le b$ and $a'^Tx' > b'$. Pick $x'$ with $x'_i = u_i$ if $a_i > 0$, $x'_i = l_i$ if $a_i < 0$ for all $i\ne j$ and $u_j -1< x'_j < \frac{b-\overline{\alpha } + a_ju_j}{a_j}$. It follows that

$$\begin{aligned} a^Tx' = \overline{\alpha } - a_j u_j + a_j x_j' \le \overline{\alpha } - a_j u_j + a_j \frac{b-\overline{\alpha } + a_ju_j}{a_j} = b \end{aligned}$$

and

$$\begin{aligned} a'^Tx' = \overline{\alpha } - a_ju_j + a'_jx'_j > \overline{\alpha } - a_ju_j + a'_j(u_j-1) = b - (a_j-a'_j)u_j = b'. \end{aligned}$$

Therefore, $a'^T x \le b'$ strictly dominates $a^Tx \le b$ on M. $\square$

Remark 1

Consider $n = 2$ and assume that $I=\{1\}$. If $0< \overline{\alpha } -b < a_1$, it is not difficult to verify that the two points $(u_1 - 1, \frac{\overline{\alpha }-a_1u_1}{a_2})$ and $(u_1 , \frac{b-a_1 u_1}{a_2})$ are extreme points of Conv$(M_I)$. Combining the two extreme points gives the valid inequality $a'_1 x_1 + a_2 x_2 \le b'$, where $a'_1 = \overline{\alpha } -b$ and $b' = b - (a_1 - a'_1)u_1$.

From the above proof, we know that if $0< \overline{\alpha }-b<a_j$, $a^Tx \le b$ will be satisfied when $x_j \le u_j -1$. This is also the reason why the coefficient $a_j$ can be strengthened.

By Proposition 1, we know that under suitable assumptions, a tighter relaxation set can be obtained without affecting the mixed integer set $M_I$ by replacing $a^T x \le b$ with $a'^T x \le b'$. This can also be interpreted as modifying one coefficient $a_j$ and the right hand side b in the original constraint that $a^T x \le b$. A similar conclusion can be drawn for the case that $a_j < 0$, $j \in I$. Thus all coefficients of integer variables are likely to be strengthened to tighten the relaxation set.

3 Generalized coefficient strengthening inequality

The condition that $0< \overline{\alpha } - b < a_j$ is quite strong as it requires that $x_j$ plays a significant role in the inequality that $a^T x \le b$. This restricts the applications of the coefficient strengthening method for solving MIP [17]. Assume again that $a_j>0$ for some $j\in I$. To weaken the condition, we may look for some integer $r \in \{0, 1,2,\ldots ,u_j - l_j-1\}$ such that $ra_j< \overline{\alpha }- b < (r+1)a_j$. Then we can see that the inequality that $a^T x \le b$ is redundant for $x_j \le u_j - r - 1$. Motivated by this observation, we will derive a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. Moreover, we will provide the invariant features of the GCS inequalities. As will be seen, although this generalization of the coefficient strengthening method cannot act as a presolving method any more, the GCS inequalities can be used as cutting planes to cut off the current relaxation solution.

Proposition 2

Assume that $a_j > 0$ for some $j\in I$. If there exists some integer $r \in \{0, 1,2,\ldots ,u_j - l_j-1\}$ such that $ra_j< \overline{\alpha }- b < (r+1)a_j$, then

• (1) $a'^T x \le b'$ is valid for the mixed integer set $M_I$ in (2), where

  $$\begin{aligned} \left\{ \begin{aligned} a'_i&= a_i, \qquad i\ne j, \\ a'_j&= \overline{\alpha } - b - r a_j, \\ b'&= b - (a_j - a'_j)(u_j - r); \end{aligned} \right. \end{aligned}$$

• (2) $a'^T x \le b'$ dominates $a^T x \le b$ on $M \cap \{x \in \mathbb {R}^n: x_j \le u_j -r \}$ and $a^T x \le b$ dominates $a'^T x \le b'$ on $M \cap \{x \in \mathbb {R}^n: x_j \ge u_j -r\}$.

Proof

Let $x' \in M_I \cap \{x \in \mathbb {R}^n: \ x_j \le u_j -r -1 \}$. It follows from $a'_j > 0$ and the defintion of $\overline{\alpha }$ that

$$\begin{aligned} a'^Tx' \le \overline{\alpha } - a_j u_j + a'_jx'_j \le \overline{\alpha } - a_j u_j + a'_j(u_j -r -1 ) = b'. \end{aligned}$$

In case of $x'_j \in M_I \cap \{x \in \mathbb {R}^n: \ x_j \ge u_j -r \}$, we also have that

$$\begin{aligned} a'^Tx' = a^Tx' - a_j x'_j+ a'_jx'_j \le b - (a_j - a'_j) (u_j - r) = b'. \end{aligned}$$

Thus $a'^Tx' \le b'$ is valid for $M_I$.

For the second part, we may just consider the case $x_j \le u_j -r$, as the other case is similar. In this case, for any point $x'$ with $l \le x' \le u$ and $a'^Tx' \le b'$, it follows from $a'_j < a_j$ that

$$\begin{aligned} a^Tx' = a'^Tx' + (a_j - a'_j)x'_j \le b' + (a_j - a'_j)(u_j-r) = b. \end{aligned}$$

This completes the proof. $\square$

Remark 2

Consider the disjunction $M_1 := M_I \cap \{x \in \mathbb {R}^n: \ x_j \le u_j -r -1 \}$ and $M_2 := M_I \cap \{x \in \mathbb {R}^n: \ x_j \ge u_j -r \}$. In the proof of Proposition 2, we prove the validity of the inequality $a'^Tx \le b'$ by verifying that it is valid for $M_1$ and $M_2$. Therefore, $a'^Tx \le b'$ may be viewed as a special disjunctive cut [8].

Similarly, we have the following result for the case that $a_j < 0$ for $j \in I$.

Proposition 3

Assume that $a_j < 0$ for some $j\in I$. If there exists $r \in \{0, 1,2,\ldots ,u_j - l_j-1\}$ such that $-ra_j< \overline{\alpha }- b < -(r+1)a_j$, then

• (1) $a'^T x \le b'$ is valid for the mixed integer set $M_I$ in (2), where

  $$\begin{aligned} \left\{ \begin{aligned} a'_i&= a_i, \qquad i\ne j, \\ a'_j&= -(\overline{\alpha } - b + r a_j), \\ b'&= b - (a_j - a'_j)(l_j + r), \end{aligned} \right. \end{aligned}$$

• (2) $a'^T x \le b'$ dominates $a^T x \le b$ on $M \cap \{x: x_j \ge l_j + r \}$ and $a^T x \le b$ dominates $a'^T x \le b'$ on $M \cap \{x: x_j \le l_j + r\}$.

For convenience, we call the valid inequality derived in Propositions 2 or 3 generalized coefficient strengthening (GCS) inequality. Notice that in the case that $r = 0$, Proposition 2 reduces to Proposition 1 since $M \cap \{x \in \mathbb {R}^n: x_j \le u_j -r \} = M$. Comparing with Proposition 1, the condition that $\ ra_j< \overline{\alpha }- b < (r+1)a_j$ for some $r \in \{0, 1,2,\ldots ,u_j - l_j-1\}$ in Proposition 2 is more general, but its conclusion is not so strong as that in Proposition 1. As illustrated in the following example, although the GCS inequality is still valid for $M_I$, we can not make a simple substitution to the original constraint that $a^Tx\le b$.

Example 1

Consider the mixed integer set

$$\begin{aligned} M_I^{(1)} = \{ (x_1,x_2)\in \mathbb {Z}^2: 2.7x_1 + 2.2x_2 \le 11,\, 0\le x_1 \le 3, \, 0 \le x_2 \le 4\}. \end{aligned}$$

It is easy to see that the maximal activity of $a^Tx$ over the set $M_I^{(1)}$ is $\overline{\alpha }=16.9$. For variable $x_1$, since $2 \times a_1<\overline{\alpha } - b = 5.9< 3 \times a_1$, let $r=2$. Take $a'_1 = 5.9-2\times 2.7 = 0.5$ and $b' = 11 - (2.7-0.5)\times (3-2) = 8.8$. By Proposition 2, we know that the inequality

$$\begin{aligned} 0.5x_1 + 2.2x_2 \le 8.8 \end{aligned}$$

is valid for $M_I^{(1)}$. However, simply replacing $2.7x_1 + 2.2x_2 \le 11$ with $0.5x_1 + 2.2x_2 \le 8.8$ in $M_I^{(1)}$ brings an extra integer point (3, 3), which is not feasible to the original set $M_I^{(1)}$.

Nevertheless, we may add the GCS inequality to the MIP formulation to tighten the relaxation set.

Proposition 4

Consider the GCS inequality derived in Proposition 2. There must exist some $x' \in M$ such that $a^Tx' \le b$ but $a'^T x' > b'$. Thus, adding $a'^T x \le b'$ into the constraints of $M_I$ leads to a more compact relaxation set.

Proof

Take any $x'$ satisfying

$$\begin{aligned} \sum _{i \ne j} a_i x'_i= \overline{\alpha } - a_j u_j \quad \text{ and }\quad x'_j \in (u_j-r-1, \frac{b-\overline{\alpha } + a_j u_j}{a_j }]. \end{aligned}$$

By direct calculations, we know that

$$\begin{aligned} a^Tx' = \overline{\alpha } - a_j u_j + a_j x'_j \le \overline{\alpha } - a_j u_j + a_j \frac{b - \overline{\alpha } + a_ju_j}{a_j} = b \end{aligned}$$

and

$$\begin{aligned} \begin{aligned} a'^T x'&= \overline{\alpha } - a_j u_j + a'_j x'_j \,>\, \overline{\alpha } - a_j u_j + a'_j(u_j - r - 1) \\&=\overline{\alpha } - a_j u_j + a'_j(u_j - r ) - \overline{\alpha } + b + r a_j \, = \, b'. \end{aligned} \end{aligned}$$

This completes our proof. $\square$

Therefore, although the above generalization of the coefficient strengthening method cannot be used as a presolving method any more as the purpose of presolving method is to reduce the size of the original problem, we may add the new valid inequality to the MIP formulation as a cutting plane to tighten the relaxation set. This will also be helpful to solve MIP as demonstrated by our numerical experiments in Sect. 5.

In what follows, we describe the invariant property of the GCS inequality. For any variable $x_k$, it is shown that the GCS inequality is invariant under either of the bound substitutions

$$\begin{aligned} y_k := x_k - l_k \ \ \text{ and } \ \ y_k := u_k - x_k. \end{aligned}$$

(5)

Proposition 5

Assume that $M_I$ is the mixed integer set in (2). For any $k\in N$, let $y_k := x_k - l_k$ and $y_i := x_i, \ i \ne k$ and consider the corresponding transformed mixed integer set

$$\begin{aligned} M_I^y := \{y\in \mathbb {Z}^p\times \mathbb {R}^{n-p}: \ a^T y \le b - a_k l_k, l^y \le y \le u^y\}, \end{aligned}$$

where $l^y_k = 0$, $u_k^y = u_k - l_k$ and $l^y_i = l_i$, $u_i^y =u_i$, $i\ne k$. If there exists a GCS inequality that $a'^Tx \le b'$ for $M_I$ given by Propositions 2 or 3, then there also exists a GCS inequality for $M_I^y$ which is equivalent to $a'^Tx \le b'$.

Proof

We may just consider the case that $a'^Tx \le b'$ is generated by Proposition 2 as the other case is similar. The definition of $M_I^y$ indicates that $\overline{\alpha }^y = \overline{\alpha } - a_k l_k$ and $\overline{\alpha }^y - (b - a_kl_k) = \overline{\alpha } - b$. By Proposition 2, $a'^T y \le b - a_k l_k - (a_j - a'_j)(u^y_j - r)$ is valid for $M_I^y$. Now consider the following two cases.

• (i) If $k \ne j$, then $u_j^y = u_j$.

• (ii) If $k = j$, then $u_j^y = u_j -l_j$.

In either case, the substitution that $y_k = x_k - l_k$ and $y_i = x_i, \ i \ne k$ leads to the same GCS inequality $a'^T x \le b'$. $\square$

Similarly, we have the following proposition.

Proposition 6

Assume that $M_I$ is the mixed integer set in (2). For any $k\in N$,

let $y_k := u_k - x_k$ and $y_i := x_i, \ i \ne k$ and consider the corresponding transformed mixed integer set

$$\begin{aligned} M_I^y := \{y\in \mathbb {Z}^p\times \mathbb {R}^{n-p}: \ (a^y)^T y \le b - a_k u_k, l^y \le y \le u^y\}, \end{aligned}$$

where $a^y_k = -a_k$, $l^y_k = 0$, $u_k^y = u_k - l_k$ and $a^y_i= a_i$, $l^y_i = l_i$, $u_i^y =u_i$, $i\ne k$. If there exists a GCS inequality that $a'^Tx \le b'$ for $M_I$ given by Propositions 2 or 3, then there also exists a GCS inequality for $M_I^y$ which is equivalent to $a'^Tx \le b'$.

Now we shall mention more possibilities of generating the GCS inequalities. At first, for the same constraint, different GCS inequalities may be generated if different integer variables are chosen. Consider Example 1 again. It is easy to verify that, if we pick the integer variable $x_2$, the GCS inequality that $2.7 x_1 + 1.5 x_2 \le 9.6$ will be generated, which is valid for X as well. In addition, we may also drop some terms of the constraint to derive GCS inequalities, as illustrated in the following example.

Example 2

Consider the mixed integer set

$$\begin{aligned} \begin{array}{ccl} &{} M_I^{(2)} = \{ (x_1, x_2, x_3)\in \mathbb {Z}^3: &{} 2.7x_1 + 2.2x_2 + 2.2 x_3 \le 11, \\ &{} &{} 0\le x_1 \le 3,~ 0 \le x_2 \le 4,~ 0\le x_3 \le 4 \}. \end{array} \end{aligned}$$

If dropping the term $2.2 x_3$ from the linear inequality of $M_I^{(2)}$, we are led to the reduced inequality that $2.7x_1 + 2.2x_2 \le 11$, which is valid for $M_I^{(2)}$ due to $2.2 x_3 \ge 0$. Furthermore, by Example 1, we can generate the GCS inequality that $0.5x_1 + 2.2x_2 \le 8.8$ based on the reduced mixed integer set, which is exactly $M_I^{(1)}$ in Example 1. This GCS inequality is valid for $M_I^{(2)}$ as well. In a similar way, dropping the term $2.2 x_2$ from the linear inequality of $M_I^{(2)}$ can yield another GCS inequality that $0.5x_1 + 2.2x_3 \le 8.8$.

As a matter of fact, we can also consider to drop multiple terms of the constraint to generate GCS inequalities. As shown in the next section, this approach is very important for how to make better use of the GCS technique in solving MIP. For convenience, for $i\in N$, we call the term $a_i x_i$ is an inactive term if it is dropped from the inequality and the corresponding variable $x_i$ is called an inactive variable. The term $a_i x_i$ which remains in the inequality is called an active term and the corresponding variable $x_i$ is called an active variable. In addition, for $j\in I$, we call the integer variable $x_j$ by GCS variable if we are going to consider the GCS inequality based on this variable. All GCS inequalities generated by choosing different GCS variables and different active variables constitute the family of GCS inequalities.

To end this section, we remark that the residual capacity inequality [21] for the set $M_I^{(0)}$ in (4) is a GCS inequality.

Proposition 7

Consider the mixed integer set $M_I^{(0)}$ in (4). Let $S\subseteq N$, $\eta = \lceil \frac{\sum _{i\in S} u_i}{D} \rceil$ and $\tau = \sum _{i\in S} u_i - D(\eta -1)$. If $0< \tau < D$, then the residual capacity inequality

$$\begin{aligned} \sum _{i \in S}x_i \le \tau y + (\eta -1)(D-\tau ) \end{aligned}$$

(6)

is a GCS inequality.

Proof

Consider the inequality with active variables being y and $x_i$, $i\in S$,

$$\begin{aligned} \sum _{i\in S} x_i \le Dy. \end{aligned}$$

(7)

The maximal activity of (7) over $M_I^{(0)}$ is $\overline{\alpha } = \sum _{i\in S} u_i$. Since $0< \tau < D$,

$$\begin{aligned} -(-D)(\eta -1)< \sum _{i\in S} u_i - 0 < -(-D)\eta . \end{aligned}$$

Choosing y to be the GCS variable, Proposition 3 gives the following GCS inequality

$$\begin{aligned} \sum _{i \in S}x_i - \tau y \le -(-D+\tau )(0+\eta -1), \end{aligned}$$

which is exactly the residual capacity inequality (6). $\square$

4 Separation algorithm for finding violated GCS inequalities

As there are usually many GCS inequalities for a mixed integer set, like other cutting planes, only some of them can be allowed to add into the problem. Therefore, we have to develop an efficient strategy for trying to generate the most effective ones. The basic thing is that, given any LP relaxation $x^*$, we attempt to find some GCS inequalities which cut off $x^*$. After some considerations about the importance of infinite bounds on variables for generating GCS inequalities, a mixed integer nonlinear programming model is formulated for the separation problem. By using the violated information, a separation algorithm is designed for solving the separation problem. It is proved that the separation algorithm is a polynomial time algorithm.

4.1 Variables bounds on generating GCS inequalities

As mentioned in Sect. 3, different GCS inequalities can be generated by choosing different active variables. In the following, we shall consider which variables must be active or not. In order to keep the validity of the inequality, we may adopt either of the following bound substitutions

$$\begin{aligned} y_i := x_i - l_i \quad \text{ and }\quad y_i := u_i - x_i. \end{aligned}$$

to disregard the term $a_ix_i$ by dropping $a_i y_i$ or $-a_iy_i$. A key observation is that those variables with infinite bounds play an important role in generating GCS inequalities.

Proposition 8

Consider the mixed integer set $M_I$ in (2) and any variable $x_i$.

• (1) If $a_i > 0$, $l_i \ne -\infty$, $u_i = \infty$ or $a_i <0$, $l_i = -\infty$, $u_i \ne \infty$, no GCS inequalities can be generated unless $x_i$ is an inactive variable;

• (2) If $a_i >0$, $l_i = -\infty$, $u_i \ne \infty$ or $a_i < 0$, $l_i \ne -\infty$, $u_i = \infty$, $x_i$ should be active in every GCS inequality;

• (3) If $l_i = -\infty$ and $u_i = \infty$, no GCS inequalities can be generated.

Proof

Consider the case that $a_i > 0$, $l_i \ne -\infty$, $u_i = \infty$. If $x_i$ is an active variable, then $\overline{\alpha } = \infty$, which implies that $\overline{\alpha } - b > (r+1)a_i$ for any r. Therefore, no GCS inequalities can be generated unless $x_i$ is an inactive variable. The proof is similar for the case that $a_i <0$, $l_i = -\infty$, $u_i \ne \infty$.

For the second part, we may only consider the case that $a_i >0$, $l_i = -\infty$, $u_i \ne \infty$. As $l_i = \infty$ and $a_i(x_i - u_i) \le 0$, in order to keep the validity of the inequality, $x_i$ should be active in every GCS inequality.

Combining the above, if $x_i$ is a free variable, the maximal activity $\overline{\alpha }$ must be $\infty$ and $x_i$ should be active in every GCS inequality. Thus, no GCS inequalities can be generated. $\square$

Due to Proposition 8, the remaining case is that $l_i \ne -\infty$ and $u_i \ne \infty$. In fact, the variable $x_i$ could be either active or inactive in this case. More exactly, $x_i$ may stay in the constraint as an active variable or become an inactive variable by dropping $a_i(x_i - l_i)$ if $a_i >0$ or $-a_i(u_i - x_i)$ if $a_i <0$.

Furthermore, by Propositions 5 and 6, the GCS inequality is invariant under bound substitutions. Therefore, in the remainder of this paper, we assume that for any variable $x_i$,

$$\begin{aligned} \begin{aligned}&l_i = 0, \, u_i< \infty , \ \ \text {if} \ a_i>0; \\&l_i = 0, \, u_i = \infty , \ \ \text {if} \ a_i<0. \end{aligned} \end{aligned}$$

(8)

Under the assumption (8), disregarding the term $a_i x_i$ with $a_i>0$ does not affect the right hand side b and the term $a_i x_i$ with $a_i < 0$ must be an active term.

4.2 An MINLP model for the separation problem

To begin with, we shall analyze the effect of disregarding the term $a_ix_i$ for any variable $x_i$ with $a_i>0$. On one hand, observe that the difference between the new maximal activity $\overline{\alpha }'$ and the right hand side decreases, since

$$\begin{aligned} \overline{\alpha }' - b = \overline{\alpha } - a_iu_i - b < \overline{\alpha } - b. \end{aligned}$$

This is beneficial to find a suitable r such that $ra_j< \overline{\alpha }- b < (r+1)a_j$. On the other hand, consider the current relaxation $x^*$ with the activity $t^* = a^T x^*$. After disregarding the term $a_i x_i$, the difference between the new activity $t'^*$ and the right hand side is decreasing as well, since we have

$$\begin{aligned} t'^* - b = t^* - a_i x_i^* - b \le t^* -b. \end{aligned}$$

This is not in accordance with our purpose, which aims to find a violated inequality. Therefore, it is difficult to choose those active terms directly.

As mentioned in Sect. 1, a linear time separation algorithm is proposed in [20] for the special mixed integer set $M_I^{(0)}$. With the help of the analysis of variables bounds in Proposition 8 and the invariant property of the GCS inequality under bound substitutions in Propositions 5 and 6, we are able to adapt the algorithm in [20] to develop a separation algorithm for finding GCS inequalities for the general mixed integer set $M_I$.

Assume that $M_I$ is the normalized mixed integer set satisfying (8) and denote $x^*$ to be the current relaxation point. Then by Proposition 8, we know that all variable $x_i$ should be active in every GCS inequality for $i\in K_2:=\{ i\in N: \ a_i < 0\}$. Fixing any GCS variable $x_j$ with $a_j>0$, we shall ask whether it is possible to choose an integer value of r and the index set of active variables, $S \subseteq K_1 := \{ i\in N: \ a_i > 0, \ i \ne j \}$, such that

$$\begin{aligned} a'_j x_j^* + \sum _{i \in S}a_i x_i^* +\sum _{ i \in K_2}a_i x_i^* > b', \end{aligned}$$

(9)

where

$$\begin{aligned} a'_{j} = \sum _{i \in S} a_i u_i + a_j u_j - b - r a_j \quad \text{ and }\quad b' = b-(a_j - a'_j)(u_j - r). \end{aligned}$$

This is a combinatorial optimization problem. By introducing binary variables, such a problem can be reformulated to look for suitable $z_i\in \{0, 1\}$ for $i\in K_1$ such that

$$\begin{aligned} a'_j x_j^* + \sum _{i \in K_1}a_i x_i^*z_i + \sum _{i\in K_2}a_ix_i^*> b', \end{aligned}$$

(10)

where

$$\begin{aligned} a'_{j} = \sum _{i \in K_1} a_i u_i z_i + a_j u_j - b - r a_j \quad \text{ and }\quad b' = b-(a_j - a'_j)(u_j - r). \end{aligned}$$

If a feasible solution z which satisfies (10) can be found, then a violated GCS inequality will be generated by Proposition 2.

It is easy to see that the relation (10) is equivalent to

$$\begin{aligned} \sum _{i \in K_1}{a_i( u_i - x^*_i )z_i}-\sum _{i\in K_2}a_ix_i^* < a'_j(r+1+x^*_j-u_j). \end{aligned}$$

(11)

To develop an efficient strategy for trying to generate the most effective ones, we formulate the following separation problem, which is a mixed integer nonlinear programming (MINLP) problem.

$$\begin{aligned} \xi = \underset{z,r,a'_j}{\min }&\quad \sum _{i \in K_1}a_i( u_i - x^*_i )z_i -\sum _{i \in K_2}a_ix_i^* - a'_j(r+1+x^*_j-u_j) \nonumber \\ \,&\text {s.t.} \quad \ \ a'_j = \sum _{i\in K_1} a_i u_i z_i + a_j u_j - b - ra_j \nonumber \\ \,&0< a'_j < a_j \nonumber \\ \,&0 \le r \le u_j -l_j -1, r \in \mathbb {Z} \nonumber \\ \,&z_i \in \{0,1\},\ i \in K_1. \end{aligned}$$

(12)

If the optimal value $\xi < 0$, the GCS inequality corresponding to an optimal solution $(z, r, a'_j)$ separates $x^*$. Otherwise, there exist no violated GCS inequalities while fixing variable $x_j$. It is not known to us yet whether the problem (12) can efficiently be solved. However, our purpose is not to find the optimal solution of (12) for all the cases but to solve (12) only when $\xi <0$. The violated information that $\xi <0$ is crucial and will help us to design a polynomial time algorithm to solve (12).

4.3 Separation algorithm

To develop an efficient algorithm, we shall make use of the violated information that $\xi <0$ to derive the relationship between r and the current value $x^*_j$ if the variable $x_j$ is fixed as the GCS variable.

Proposition 9

Consider variable $x_j$ with $j \in I$ and $a_j >0$. If $x_j^*\le u_j - r - 1$ or $x_j^*\ge u_j - r$, there are no GCS inequalities on variable $x_j$ that cuts off $x^*$.

Proof

Suppose that some GCS inequality that $a'^Tx\le b'$ is generated on variable $x_j$ with $a_j> 0$. If $x^*_j \le u_j - r -1$, it follows that

$$\begin{aligned} a'^Tx^* \le \overline{\alpha } - a_j u_j + a'_jx^*_j \le \overline{\alpha } - a_j u_j + a'_j(u_j -r -1 ) = b'. \end{aligned}$$

Therefore, no GCS inequalities on variable $x_j$ can be generated to cut off $x^*$. If $x_j^* \ge u_j - r$, it follows from $a'_j < a_j$ that

$$\begin{aligned} \begin{aligned} a'^T x^*- b'&= a^T x^* + (a'_j - a_j)x_j^* - b + (a_j - a'_j)(u_j - r) \\&= a^T x^* - b + (a_j - a'_j)(u_j - r - x^*_j ) \le a^T x^*-b\le 0. \end{aligned} \end{aligned}$$

Thus no violated GCS inequalities exist on variable $x_j$. $\square$

By Proposition 9, we can assume that $\lfloor x_j^* \rfloor = u_j - r - 1$. In this case, r can be regarded as a constant in problem (12). After the elimination of the variable $a'_j$, problem (12) can be translated into the following mixed integer linear programming problem:

$$\begin{aligned} \underset{z}{\text {min}}&\quad \sum _{i \in K_1}a_k( u_i - x^*_i - u_i f^*_j)z_i - \sum _{i\in K_2}a_ix_i^* + (b + r a_j - a_j u_j )f_j^* \nonumber \\ \text {s.t.}&\quad 0< \sum _{i\in K_1} a_i u_i z_i + a_j u_j - b -r a_j <a_j \nonumber \\ \,&z_i \in \{0,1\},\ i \in K_1 \nonumber \\ \,&r = u_j-1 - \lfloor x_j^*\rfloor , \ f_j^* = x_j^* - \lfloor x_j^* \rfloor . \end{aligned}$$

(13)

The direct solution of problem (13) is still hard to compute. To circumvent the difficulty, we provide two more propositions. Let T be the index set of variables with negative objective coefficients in problem (13), namely,

$$\begin{aligned} T:= \{ i \in K_1: u_i - x^*_i - u_i f^*_j <0 \}. \end{aligned}$$

(14)

Proposition 10

For a relaxation solution $x^*$ with $x^*_j \notin \mathbb {Z}$, $a_j >0$ and $j\in I$, if there exists a violated GCS inequality on $x_j$ given by some subset $C \subseteq K_1$ with

$$\begin{aligned} a'_j x_j^* + \sum _{i \in C}a_i x_i^* +\sum _{i\in K_2}a_i x_i^* > b', \end{aligned}$$

then there also exists a violated GCS inequality on $x_j$ given by some subset $S\subseteq T$.

Proof

Assume that there exists a violated GCS inequality given by some subset $C\subseteq K_1$. From the constraints of problem (13),

$$\begin{aligned} a'_j = \sum _{i\in C} a_i u_i + a_j u_j - b - ra_j. \end{aligned}$$

If $\sum _{i\in C \backslash T} a_i u_i < a'_j$, we have that

$$\begin{aligned} b+ ra_j -a_j u_j< \sum _{i\in C \cap T} a_i u_i \le \sum _{i\in C} a_i u_i < b+ (r+1)a_j -a_j u_j. \end{aligned}$$

Therefore, the set $S:=C \cap T$ is corresponding to a feasible point of problem (13) and its objective value does not exceed the one related to C.

In the case that $\sum _{i\in C \backslash T} a_i u_i \ge a'_j$, it follows that

$$\begin{aligned} \sum _{i\in C \cap T} a_i u_i \le b+ ra_j -a_j u_j. \end{aligned}$$

The objective value of problem (13) related to C is

$$\begin{aligned} \begin{aligned}&\sum _{i \in C}a_i( u_i - x^*_i - u_i f^*_j ) - \sum _{i\in K_2 }a_ix_i^* + ( b + r a_j - a_j u_j )f^*_j \\ \ge&\sum _{i \in C}a_i( u_i - x^*_i - u_i f^*_j ) + \sum _{i\in C \cap T} a_i u_i f_j^* -\sum _{i\in K_2 }a_ix_i^* \\ =&\sum _{i \in C\backslash T}a_i( u_i - x^*_i - u_i f^*_j ) + \sum _{i \in C \cap T}a_i(u_i - x^*_i) -\sum _{i\in K_2 }a_ix_i^* \\ \ge&\ 0, \end{aligned} \end{aligned}$$

which contradicts the violated assumption that $\xi <0$. $\square$

Proposition 11

If either

$$\begin{aligned} \sum _{i\in T} a_i u_i \le b + ra_j - a_j u_j \ \text {or} \ \sum _{i\in T} a_i u_i \ge b+(r+1)a_j - a_j u_j, \end{aligned}$$

then there exist no violated GCS inequalities on variable $x_j$.

Proof

The case that $\sum _{k\in T} a_i u_i \le b + ra_j - a_j u_j$ is straightforward due to the proof of Proposition 10. Now consider the case $\sum _{i\in T} a_i u_i \ge b+(r+1)a_j - a_j u_j$. Assume that there exists a subset $S\subseteq T$ which leads to a violated GCS inequality. The objective value of problem (13) for S is

$$\begin{aligned} \begin{aligned}&\sum _{i \in S}a_i( u_i - x^*_i - u_i f^*_j) + ( b + r a_j - a_j u_j )f_j^* - \sum _{i\in K_2 }a_ix_i^* \\ \ge&\sum _{i \in T}a_i( u_i - x^*_i - u_i f^*_j ) + ( b + r a_j - a_j u_j )f^*_j - \sum _{i\in K_2}a_ix_i^* \\ =&\sum _{i \in T}a_i( u_i - u_i f^*_j ) + \sum _{i \in T}a_i( -x_i^*) + ( b + r a_j - a_j u_j )f^*_j - \sum _{i\in K_2}a_ix_i^* \\ \ge&[b+(r+1)a_j - a_j u_j]( 1- f^*_j ) - b + a_j x^*_j + ( b + ra_j - a_j u_j )f_j^* \\ =&\ 0, \end{aligned} \end{aligned}$$

which contradicts the violated assumption that $\xi <0$. $\square$

Propositions 10 and 11 indicate that, if having fixed the GCS variable $x_j$ with $a_j>0$, only the set T [as defined in (14)] is required to be considered in generating the GCS inequalities. More exactly, if the following conditions hold,

$$\begin{aligned} b + ra_j - a_j u_j< \sum _{i\in T} a_i u_i < b+(r+1)a_j - a_j u_j \end{aligned}$$

(15)

and

$$\begin{aligned} \sum _{i \in T}a_i( u_i - x^*_i - u_i f^*_j ) - \sum _{i \in K_2}a_ix_i^* + (b + r a_j - a_j u_j )f^*_j < 0, \end{aligned}$$

(16)

then the most violated inequality based on variable $x_j$ given by T can be generated. Otherwise, we can claim that no GCS inequalities exist on variable $x_j$.

Now we are able to provide Algorithm 1, which can generate all the most violated GCS inequalities on integer variables with positive coefficients. A similar separation algorithm can be obtained for the case $a_j < 0$, $j \in I$ by Proposition 3.

Proposition 12

The separation problem (13) can be solved by Algorithm 1 in $\mathcal {O}(n|I|)$ operations, where n is the number of nonzero coefficients.

Proof

Notice that there are at most |I| integer variables with $x_j^* \notin \mathbb {Z}$. The work of Algorithm 1 in recovering the inequality to the original space and calculating (15) and (16) can be done in $\mathcal {O}(n)$ operations. Therefore, the separation problem (13) can be solved in $\mathcal {O}(n|I|)$ operations. $\square$

To end this section, we summarize two advantages of GCS inequalities. On one hand, the separation problem can efficiently be solved since the number of nonzero coefficients in one constraint is usually small in real problems. On the other hand, as the GCS inequality is generated by the original constraint, it probably does not contain too large or too small coefficient values. Therefore, these GCS inequalities are usually sparse and stable.

5 Numerical results

We evaluated the performance of GCS inequalities by implementing it as an additional separator in the open source MIP solver SCIP 3.2.1 [22] with the default LP solver SOPLEX 2.2.1 [26]. For convenience, the corresponding separator is called as the GCS separator. All numerical tests described in this section were implemented on a cluster of Intel Core i7-4790 3.60 GHz computer, with 8 MB cache and 8 GB RAM. The operating system is Ubuntu 16.04. According to [27], in order to have a fair comparison, we used the most infeasible branching strategy and disable restart presolving technique and all primal heuristics.

Instances from MIPLIB 3.0 [23], MIPLIB 2003 [24] and the benchmark set of MIPLIB 2010 [25] (denoted by MMM) were used for our numerical experiments. We excluded 3 infeasible instances named ash608gpia-3col, enlight14 and ns1766074, and one instance which runs out of memory at the root node in SCIP, namely mspp16. This leaves us 164 instances in the MMM test set.

In order to study the performance of the GCS separator more exhaustively, we try to ask the three questions as follows.

• (1) What effect does the GCS separator make individually?

• (2) Does the GCS separator improve the dual bound when invoking it along with other separators in a MIP solver?

• (3) What is the impact of the GCS separator on the overall running time?

If one expects the GCS separator to have some positive effects, the GCS separator must generate some efficient cuts for real application problems. On the other hand, since it can tighten the relaxation set, we want to know how tight it is after the addition of the GCS inequalities. That is the reason why we ask the first question. Since there are some other separators in MIP solvers, we want to know whether the GCS separator is covered by other separators or not. That is the motivation to ask the second question. Finally, by asking the third question, we want to know whether the separator is effective for solving MIP instances.

For the first question, we tested the individual performance of the GCS separator and compared it with some other separators. Since the separators affect one another, we disable all the other separators except the tested one. In order to describe the performance, we use the root gap closed [27] defined as follows:

$$\begin{aligned} 100\cdot \frac{\check{z}-z_{LP}}{z_{MIP}-z_{LP}}, \end{aligned}$$

where $\check{z}$ is the dual bound at the root node before branching, $z_{LP}$ is the value of LP relaxation after presolving and $z_{MIP}$ is the optimal (or best known) value of MIP.

Fig. 1

Gap closed by individual separators

Figure 1 shows the arithmetic mean of the gap closed by all separators in SCIP. For the MMM test set, the gap closed by the GCS separator is 15.90%, which is better than Implied Bounds, Knapsack Cover, Clique, MCF and Disjunctive separators but worse than MIR, GMI, Strong CG and Flow Cover separators. This indicates that the GCS separator has a modest effect in improving the dual bound on real data problems. Furthermore, among 164 instances in the MMM test set, it affects 105 instances, more than half of the instances.

For the second question, we tested the performance when invoking it with other separators. As before, the root gap closed is used to evaluate the performance. At this time, we did not disable other separators but compared the default setting as described above with the version turning on the GCS separator.

Table 1 Overall gap closed

As Table 1 shows, the average root gap closed increases by $0.30\%$ for all 164 instances if the GCS separator is called. For the affected 105 models, the gap closed is improved by $0.47\%$. Looking at the number of better gap closed instances, it is 39 while the worse cases is only 22. This shows that although the GCS is likely to be covered by other separators in most cases, there exist some cuts which are not generated by the other separators. This result will further be verified at the end of this section.

For the third question, we studied the time and nodes performances after calling the GCS separator in an MIP solver. We only considered those affected instances that can be solved in 3600 s by at least one of the two settings. This leaves us 40 instances.

Table 2 Time and nodes performances

Table 2 presents the time and nodes performances when adding the GCS separator comparing with the default setting as described above (One can also see Table 3 in “Appendix” for the details). In either case, all of the 40 instances are solved. Interestingly, we see from Table 2 that the geometric mean¹ of time and nodes is significantly improved. Furthermore, 8 instances are at least $10\%$ time faster if calling the GCS separator, while only 6 instances are at least $10\%$ time faster when turning the GCS separator off. This indicates that GCS separator has a positive effect for solving MIP.

To end this section, we illustrate one instance which is much improved by calling GCS separator. The name of such an instance is quet1, which was once studied in [28]. We found that the solution time decreases from 342.3 to 3.6 s by calling the GCS separator. Looking at its structure further, it contains the following type of constraints:

$$\begin{aligned} \sum _{i\in C} a_i x_i \le y_1 + q y_2, \end{aligned}$$

where $x_i \in \mathbb {B}$, $y_1, y_2 \in \mathbb {Z}^+$, $a_i > 0$, $i \in C$ and $q >1$. Moreover, $1<\frac{c_{y_2}}{c_{y_1}} < q$, where $c_{y_1}$ and $c_{y_1}$ are the objective coefficients of $y_1$ and $y_2$, respectively. Combining all these conditions, the solution of LP relaxation $(x^*, y^*)$ is usually such that $y^*_2 \notin \mathbb {Z}$. The GCS separator generates the following type of valid inequalities,

$$\begin{aligned} \sum _{i\in S} a_i x_i \le y_1 + q' y_2 + \gamma , \end{aligned}$$

where $S \subseteq C$, $0< q' < q$ and $\gamma$ is a constant, to separate $(x^*, y^*)$. To the best of our knowledge, these inequalities are hardly generated by the other separators in SCIP. By the addition of the GCS separator, the gap closed increases from $88.48\%$ to $95.78\%$ and hence leads to a significant improvement in the solution time.

6 Conclusion and future work

We have proposed the family of GCS inequalities by generalizing the idea of the coefficient strengthening method. By studying the invariant property of GCS inequalities, analyzing the variables bounds and using the violated information, we have provided a separation algorithm to find the violated inequalities, which leads to the GCS separator. Our computational results demonstrate that, although the generated GCS cuts are likely to be covered by those generated by some other separators in most cases, there also exist some GCS cuts that are not covered and the proposed GCS separator improves the performance for these instances on average.

There still exist some ideas to be explored to improve the efficiency of GCS cuts. For example, it appears important to aggregate some constraints and use the GCS separator on the aggregated constraint to generate cuts (see [2] for this idea). Comparing with dropping terms directly, the advantage of this technique is that it affects the difference between the current activity and the right hand side as small as possible. Another interesting topic is only to generate the GCS cuts which cannot be generated by other separators, especially by the MIR separator. In our numerical experiments, we observed that the MIR separator generates some identical inequalities as GCS separator generates for some instances including bell5 and bab5. It remains to be explored how to avoid these redundant works.

Appendix

See Table 3.

Table 3 Detail results of nodes and time performance