When Variables Mix: Gomory's Mixed-Integer Cuts

Image by Vicky Nguyen, retrieved from Unsplash

In Mixed-Integer Linear Optimization, it is common to encounter problems where discrete decisions (integer or binary variables) and continuous decisions (flow quantities, physical capacities…) coexist. When solving the continuous relaxation of a mixed-integer linear problem using the Simplex algorithm, integrality constraints are temporarily dropped. If the resulting solution is not integer-valued for the variables that require it, one must turn to algorithms such as Branch and Bound or Cutting-Plane Methods.

However, when attempting to directly apply Gomory’s fractional cut, originally designed for pure integer problems, we hit a fundamental mathematical roadblock.

When continuous variables are introduced

If a row in the Simplex tableau contains at least one non-basic variable $x_j$ that is continuous (\(x_j \geqslant 0\), with no integrality constraint), the rationale behind the pure fractional cut collapses for three essential reasons:

1. Loss of modular properties: A continuous variable $x_j$ does not jump from integer to integer; it can take any non-negative real value (such as \(x_j = 0.001\)). As a result, the sum is no longer bounded by discrete jumps modulo 1.
2. Continuous fraction absorption: A tiny variation in the continuous variable $x_j$ can change the left-hand-side value continuously, “absorbing” the fractional part \(f_s\) without forcing any integer variable to change its value.
3. Invalidity of fractional parts of coefficients: Decomposing the coefficient $\bar{y}_{ij}$ of a continuous variable into \([\bar{y}_{ij}] + f_{ij}\) lacks algebraic sense for bounding the problem, since \(f_{ij} x_j\) does not produce discrete values when \(x_j\) is continuous. If a pure fractional cut were forced upon continuous variables, it would cut off feasible solutions of the original problem, violating the fundamental condition of cut validity.

The following example illustrates this very issue.

\[\begin{align*} \min \quad & z = 3x_1 + 2x_2 + x_3 \\ \text{s.t.:} \quad & x_1 + 2x_2 - x_3 = 6 \\ & 2x_1 - x_2 + 2x_3 = 5 \\ & x_1, x_2, x_3 \geqslant 0 \\ & x_2 \text{ integer} \end{align*}\]

The final Simplex tableau for the continuous relaxation is:

\[\begin{array}{rc|rrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \\ & & x_1 & x_2 & x_3 & \\ \hline & z_j - c_j & 0 & 0 & -4/5 & 62/5 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 3/5 & 16/5 \\ \color{gray}{2} & x_2 & 0 & 1 & -4/5 & 7/5 \\ \hline \end{array}\]

which, upon introducing Gomory’s pure fractional cut

\[\frac{1}{5} x_3 \geqslant \frac{2}{5}\]

yields the tableau:

\[\begin{array}{rc|rrrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \color{gray}{0} & \\ & & x_1 & x_2 & x_3 & x_4^s & \\ \hline & z_j - c_j & 0 & 0 & 0 & -4 & 14 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 0 & 3 & 2 \\ \color{gray}{2} & x_2 & 0 & 1 & 0 & -4 & 3 \\ \color{gray}{1} & x_3 & 0 & 0 & 1 & -5 & 2 \\ \hline \end{array}\]

yielding the solution: \(\bar{\mathbf{x}} = (2,3,2,0)^\top\) with \(z^* = 14\), because the added cut forces $x_3 \geqslant 2$. However, the true optimal solution to the problem is: \(\mathbf{x}^* = (11/4, 2, 3/4, 0)^\top\) with \(z^* = 13\). Notice that $x_3$ in the true optimal solution takes a value smaller than $2$, directly contradicting the constraint imposed by Gomory’s pure fractional cut.

Justification and derivation of Gomory’s mixed-integer cut

To derive Gomory’s mixed-integer cut (Gomory, 1960), we first need to establish some notation. First, we partition the index set of variables $\mathcal{I}$ into continuous variables ($\mathcal{I}^1$) and integer variables ($\mathcal{I}^2$), allowing us to define the following sets:

• $$\mathcal{I}_f^1 (\bar{\mathbf{x}}) = \{s \in \mathcal{I}: f_s > 0, x_s \text{ continuous}\}$$
• $$\mathcal{I}_f^2 (\bar{\mathbf{x}}) = \{s \in \mathcal{I}: f_s > 0, x_s \text{ integer}\}$$
• $$\mathcal{J}_s^+ = \{j \in \mathcal{J}: y_{sj} \geqslant 0\}$$
• $$\mathcal{J}_s^- = \{j \in \mathcal{J}: y_{sj} \leqslant 0\}$$

If, after solving the continuous relaxation of a mixed-integer problem, we find that $\mathcal{I}_f^2 \neq \emptyset$, we must introduce a cut to achieve a solution that satisfies the integrality of those variables. Selecting the variable $x_s \in \mathcal{I}_f^2(\bar{\mathbf{x}})$, its row in the explicit Simplex system is:

\[x_s = [\bar{x}_s]+ f_s - \sum_{j \in \mathcal{J}} y_{sj} x_j\]

which is equivalent to:

\[\sum_{j \in \mathcal{J}} y_{sj} x_j = f_s + ([\bar{x}_s] - x_s)\]

At this point, we split the index set \(\mathcal{J} = \mathcal{J}_s^+ \cup \mathcal{J}_s^-\), obtaining:

\[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j= f_s + ([\bar{x}_s] - x_s)\]

We now want to formulate a valid cut that excludes the non-integer solution $\bar{x}_s$, considering two exhaustive cases:

• $x_s \geqslant [\bar{x}_s] + 1$: Since $x_s$ must be an integer, $[\bar{x}_s] - x_s$ must be a non-positive integer ($\leqslant -1$). Given that $0 < f_s < 1$, it follows that:

  \[f_s + ([\bar{x}_s] - x_s) \leqslant f_s - 1\]

  and therefore:

  \[\left. \begin{aligned} \sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j &\leqslant f_s - 1 \\ \sum_{j \in \mathcal{J}_s^+} y_{sj} x_j &\geqslant 0 \end{aligned} \right\} \Rightarrow \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \leqslant f_s - 1\]

  from which we deduce:

  \[\frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

  Adding the non-negative term associated with $\mathcal{J}_s^+$ yields the cut:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

• $x_s \leqslant [\bar{x}_s]$: Since $x_s$ must be an integer, we have \([\bar{x}_s] - x_s \geqslant 0\). Consequently, the equality implies:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \geqslant f_s\]

  By the definition of $\mathcal{J}_s^-$ and knowing $0 < f_s < 1$, we observe:

  \[\sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \leqslant 0 \leqslant \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j\]

  thus concluding that the associated valid cut is identical to the one obtained in the first case:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

Therefore, Gomory’s mixed-integer cut in both cases can be rewritten as:

\[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{1-f_s}\sum_{j \in \mathcal{J}_s^-} (-y_{sj}) x_j \geqslant f_s\]

Solving the previous example

In the continuous relaxation tableau, the cut associated with variable $x_2$ (since it took a non-integer value) is:

\[\frac{\frac{2}{5}}{1-\frac{2}{5}}\left(\frac{4}{5}\right) x_3 \geqslant \frac{2}{5} \equiv \frac{8}{15}x_3 \geqslant \frac{2}{5}\]

Inserting this cut into the tableau and applying the Dual Simplex algorithm yields the final tableau:

\[\begin{array}{rc|rrrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \color{gray}{0} & \\ & & x_1 & x_2 & x_3 & x_4^s & \\ \hline & z_j - c_j & 0 & 0 & 0 & -3/2 & 13 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 0 & 9/8 & 11/4 \\ \color{gray}{2} & x_2 & 0 & 1 & 0 & - 3/2 & 2 \\ \color{gray}{1} & x_3 & 0 & 0 & 1 & -15/8 & 3/4 \\ \hline \end{array}\]

yielding the optimal solution to the problem:

\[\mathbf{x}^* = (11/4, 2, 3/4)^\top \quad z^* = 13\]

---

Gomory’s mixed-integer cuts form one of the key cornerstones of modern commercial optimization solvers (such as Gurobi, CPLEX, or SCIP). Combining these cutting planes with the tree search of Branch & Bound gives birth to the Branch & Cut algorithm, capable of solving large-scale, complex industrial problems quickly and with mathematical rigor.

---

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.