The Cutting Plane Method for Integer Linear Programming

Author

Your Name

Published

January 30, 2025

Introduction

This lecture introduces the cutting plane method, an alternative to the dominant branch and bound technique for solving Integer Linear Programming (ILP) problems. Although branch and bound is the current state-of-the-art, the cutting plane method has regained attention, particularly through its integration into branch and cut algorithms. We will explore the foundational concepts of this method, including its historical context, core principles, and the generation of cutting planes, with a focus on Chvátal inequalities and Gomory cuts. We will examine how these cuts iteratively refine the feasible region of the linear programming relaxation, ultimately leading to an integer solution. Outline:

Motivation and Historical Context
Core Concepts of the Cutting Plane Method
Chvátal Inequalities
Gomory Cuts
The Cutting Plane Algorithm
Detailed Example: Production Planning

The Cutting Plane Method

Motivation and Historical Context

Early Challenges and Limitations

Proposed in the 1960s, the cutting plane method initially faced significant practical limitations. The computational demands, in terms of both numerical precision and processing power, were too high for the computers available at the time. Consequently, the method was largely of theoretical interest, with implementation challenges hindering its practical application.

Revival and Integration with Branch and Bound

The 1980s and 1990s witnessed a revival of the cutting plane method, driven by advancements in computer technology and theoretical insights that addressed some of the numerical issues. As computers became faster and more powerful, and as new theoretical developments emerged to tackle numerical instability, the method became more viable. Researchers began exploring the integration of cutting plane techniques with the branch and bound method, leading to the development of branch and cut algorithms. In this hybrid approach, cutting planes are used to strengthen the linear programming relaxation within the branch and bound framework. Adding valid inequalities as cuts reduces the feasible region, leading to tighter formulations and potentially more efficient branch and bound searches. This combined approach, branch and bound with cutting planes, is known as branch and cut, though we will not explore it in detail here.

Core Concepts

Problem Formulation in Standard Form

The cutting plane method is conveniently described when the ILP problem is in standard form: $$ \[\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}\]

$$ Here, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$. We define:

$P = \{x \in \mathbb{R}^n : Ax = b, x \geq 0\}$: The polyhedron defined by the constraints of the LP relaxation, representing the feasible region in the continuous space.
$X = P \cap \mathbb{Z}^n$: The set of integer solutions within $P$.
$P_I = \text{conv}(X)$: The convex hull of the integer solutions, which is the ideal polyhedron to optimize over for solving the integer program as a linear program.

LP Relaxation and Fractional Solutions

Similar to branch and bound, the cutting plane method begins by solving the Linear Programming (LP) relaxation of the integer problem. Let $x^*$ be the optimal solution to the LP relaxation. If $x^*$ is an integer vector ($x^* \in \mathbb{Z}^n$), it is also an optimal solution to the original ILP, and we are done. However, if $x^*$ contains fractional components, it is not feasible for the ILP. In this case, we need a way to "cut off" this fractional solution without removing any integer feasible solutions.

The Role of Valid Inequalities

If the optimal LP solution $x^*$ is fractional, then $x^* \notin P_I$. Thus, there must exist at least one valid inequality for $P_I$ that is violated by $x^*$.

A valid inequality for $P_I$ is a linear inequality $\alpha^T x \leq \beta$ such that $\alpha^T x \leq \beta$ holds for all $x \in P_I$.

For our fractional solution $x^*$, we have $\alpha^T x^* > \beta$. This inequality can "cut off" the fractional solution $x^*$ from the feasible region while preserving all integer solutions.

Geometric Interpretation of Cutting Planes

Geometrically, consider the polyhedron $P$ and its integer hull $P_I$. Let $x^*$ be an optimal vertex of $P$ obtained by solving the LP relaxation. If $x^*$ is fractional, it lies outside $P_I$. A cutting plane is a hyperplane that separates $x^*$ from $P_I$. 1 illustrates this. The outer polyhedron represents $P$, and the inner dashed polyhedron represents $P_I$. The point $x^*$ is an optimal vertex in $P$ but not in $P_I$. The red line represents a cutting plane that is valid for $P_I$ (all points in $P_I$ satisfy it) but is violated by $x^*$.

Geometric interpretation of a cutting plane separating a fractional optimal solution (x^*) from the integer hull (P_I).

Iterative Cutting Process

Adding Cuts to the Formulation

Starting with the initial LP relaxation $P = P_0$, if the optimal solution $x^{(0)}$ is fractional, we find a valid inequality (a cut) $\alpha^{(1)T} x \leq \beta^{(1)}$ that is valid for $P_I$ but violated by $x^{(0)}$. We add this cut to the formulation, creating a new polyhedron $P_1 = P_0 \cap \{x : \alpha^{(1)T} x \leq \beta^{(1)}\}$. This new polyhedron $P_1$ is a tighter relaxation of $P_I$ because $P_I \subseteq P_1 \subsetneq P_0$.

Progressive Reduction of the Feasible Region

We repeat this process iteratively. At iteration $k$, we have a polyhedron $P_k$. We solve the LP relaxation over $P_k$ to obtain an optimal solution $x^{(k)}$. If $x^{(k)}$ is integer, we have found the optimal integer solution and terminate. If $x^{(k)}$ is fractional, we find a new valid inequality $\alpha^{(k+1)T} x \leq \beta^{(k+1)}$ that is valid for $P_I$ but violated by $x^{(k)}$. We then form a new polyhedron $P_{k+1} = P_k \cap \{x : \alpha^{(k+1)T} x \leq \beta^{(k+1)}\}$. This generates a sequence of polyhedra $P_0 \supsetneq P_1 \supsetneq P_2 \supsetneq \dots \supseteq P_I$, progressively reducing the feasible region towards the integer hull $P_I$.

Convergence and Termination Criteria

The iterative process continues until we obtain an optimal solution $x^{(k)}$ that is integer. Since each cut removes a portion of the feasible region containing the current fractional optimal solution, and we are always adding valid inequalities, the sequence of optimal LP values is monotonically decreasing and bounded below by the optimal integer solution value. A key result, attributed to Chvátal, guarantees that for certain types of cuts, this process is finite, meaning that we will eventually reach an integer optimal solution in a finite number of iterations.

The Separation Problem

The crucial step in the cutting plane method is finding a valid inequality that separates the current fractional solution $x^{(k)}$ from the integer hull $P_I$. This is known as the separation problem.

Given a fractional point $x^{(k)}$, the separation problem is to find a valid inequality $\alpha^T x \leq \beta$ for $P_I$ such that $\alpha^T x^{(k)} > \beta$.

The efficiency of a cutting plane algorithm heavily depends on the ability to solve the separation problem effectively, i.e., to find "deep" cuts that significantly reduce the feasible region and lead to faster convergence.

Chvátal Inequalities

Characterizing Valid Inequalities for Integer Programs

Chvátal inequalities provide a systematic way to generate valid inequalities for integer programs. They are fundamental to understanding the structure of the integer hull $P_I$. A key result in integer programming theory states that all valid inequalities for $P_I$ can be derived using a process based on Chvátal inequalities.

Derivation of Chvátal Inequalities

Using Multipliers and Rounding Operations

Consider a system of linear equations in standard form $Ax = b$ defining a polyhedron $P$, where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$. Let $X = P \cap \mathbb{Z}^n$ be the set of integer points within $P$.

To derive a Chvátal inequality, we take a linear combination of the equations in $Ax = b$ with non-negative multipliers $u \in \mathbb{R}^m, u \geq 0$. Multiplying the system $Ax = b$ by $u^T$ from the left, we get $u^T A x = u^T b$. For any integer solution $x \in X$, this equation holds.

Now, consider the inequality $\sum_{j=1}^n (u^T A)_j x_j \leq u^T b$. Since we are interested in integer solutions $x \in \mathbb{Z}^n$, we can strengthen this inequality by rounding down the coefficients on the left-hand side. For each coefficient $(u^T A)_j$, we take the floor value $\lfloor (u^T A)_j \rfloor$. This gives us: \[\sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq u^T b\] Since the left-hand side is an integer for any $x \in \mathbb{Z}^n$, we can also round down the right-hand side without losing any integer solutions. This leads to the Chvátal inequality: \[\sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq \lfloor u^T b \rfloor\] This inequality is valid for all integer solutions $x \in X$.

The Chvátal Closure

Definition and Properties of the Closure

Let $P = \{x \in \mathbb{R}^n : Ax = b, x \geq 0\}$. The Chvátal closure of $P$, denoted by $C(P)$, is defined as the intersection of $P$ with all possible Chvátal inequalities derived from $Ax = b, x \geq 0$. Formally, \[C(P) = P \cap \{x \in \mathbb{R}^n : \sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq \lfloor u^T b \rfloor \text{ for all } u \geq 0 \}.\] A significant result by Chvátal is that $C(P)$ is also a polyhedron. This is a non-trivial result because there are infinitely many possible non-negative multiplier vectors $u$, potentially leading to infinitely many Chvátal inequalities. However, the set of all such inequalities defines a polyhedron.

Iterated Closures and Finite Convergence

We can iteratively apply the Chvátal closure operation. Let $P^{(0)} = P$, and define $P^{(k+1)} = C(P^{(k)})$ for $k \geq 0$. This generates a sequence of polyhedra $P^{(0)} \supseteq P^{(1)} \supseteq P^{(2)} \supseteq \dots \supseteq P_I$. Chvátal proved that for any polyhedron $P$ representing the LP relaxation of an integer program, there exists a finite integer $k$ such that $P^{(k)} = P_I$. This means that by repeatedly generating and adding Chvátal inequalities, we can eventually obtain the integer hull $P_I$. This theoretical result underpins the convergence of cutting plane methods.

Illustrative Example

Consider the system: $$ \[\begin{aligned} 2x_1 + 5x_2 + x_3 &= 30 \\ 4x_1 - 3x_2 + x_4 &= 6 \\ x_1, x_2, x_3, x_4 &\geq 0, \quad x_1, x_2, x_3, x_4 \in \mathbb{Z} \end{aligned}\]

\[ We want to derive a Chvátal inequality. Let's choose multipliers $u = (5/6, 11/12)^T \geq 0$. Multiplying the first equation by $5/6$ and the second by $11/12$ and summing them, we get: \]( + ) x_1 + ( + (-3)) x_2 + ( + ) x_3 + ( + ) x_4 = + \[ Simplifying the coefficients: \] x_1 + x_2 + x_3 + x_4 = 30.5\[ Now, we take the floor of each coefficient on the left side: \] x_1 + x_2 + x_3 + x_4 \[ \]5x_1 + 1x_2 + 0x_3 + 0x_4 \[ Since the left-hand side is an integer for integer values of $x_i$, we can take the floor of the right-hand side: \]5x_1 + x_2 $$ Thus, $5x_1 + x_2 \leq 30$ is a Chvátal inequality valid for integer solutions of the given system.

The process of generating Chvátal inequalities involves choosing multipliers and performing rounding operations.

Choosing multipliers $u$: In principle, there are infinitely many possible choices for the multiplier vector $u$. The effectiveness of the resulting inequality depends heavily on this choice. Finding good multipliers is a crucial aspect of the separation problem.
Rounding operations: Once the multipliers are chosen, the rounding operations are straightforward and can be done in linear time with respect to the number of variables, $O(n)$.
Finding all Chvátal inequalities: Finding all possible Chvátal inequalities is computationally intractable, as it would involve exploring an infinite space of multipliers.
Determining the Chvátal closure: Determining the complete Chvátal closure is also computationally challenging. However, in practice, we often generate a subset of Chvátal inequalities that are considered effective.

Gomory Cuts

Gomory Cuts from the Simplex Tableau

Expressing the System with Respect to the Optimal Basis

Gomory cuts are a specific type of cutting plane that can be derived from the optimal simplex tableau of the LP relaxation. Suppose we have solved the LP relaxation and obtained an optimal basis $B$. We can express the system of equations in terms of basic and non-basic variables. Let $N$ be the set of indices of non-basic variables. For each basic variable $x_{B_i}$, the simplex tableau provides an equation of the form: \[x_{B_i} + \sum_{j \in N} \bar{a}_{ij} x_j = \bar{b}_i\] where $\bar{a}_{ij}$ are the entries in the tableau under non-basic variable $x_j$ in the row corresponding to basic variable $x_{B_i}$, and $\bar{b}_i$ is the value of the basic variable $x_{B_i}$ in the current solution. The $\bar{a}_{ij}$ values represent the coefficients of the non-basic variables in the expression for the basic variable $x_{B_i}$, and $\bar{b}_i$ represents the value of $x_{B_i}$ in the current basic feasible solution.

Integer Form of Gomory Cuts

If the optimal LP solution is fractional, there must be at least one basic variable $x_{B_l}$ that takes a fractional value $\bar{b}_l$. Consider the equation for this basic variable: \[x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j = \bar{b}_l\] Since we require integer solutions, for any integer solution $x$, the left-hand side $x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j$ must be an integer. Therefore, it must be less than or equal to the floor of the right-hand side. This gives us the integer form of the Gomory cut: \[x_{B_l} + \sum_{j \in N} \lfloor \bar{a}_{lj} \rfloor x_j \leq \lfloor \bar{b}_l \rfloor\] Rearranging terms to isolate non-basic variables on one side, we get the Gomory integer cut as: \[\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}\]

Fractional Form of Gomory Cuts

Notation for Fractional Parts

Let $\{ z \} = z - \lfloor z \rfloor$ denote the fractional part of a real number $z$. For example, $\{ 3.2 \} = 0.2$, $\{ 8.9 \} = 0.9$, and $\{ 5 \} = 0$. Note that $0 \leq \{ z \} < 1$.

Derivation of Fractional Cuts

Consider again the equation from the simplex tableau for a basic variable $x_{B_l}$ with a fractional value $\bar{b}_l$: \[x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j = \bar{b}_l\] We can rewrite each coefficient and the right-hand side as the sum of their integer and fractional parts: \[x_{B_l} + \sum_{j \in N} (\lfloor \bar{a}_{lj} \rfloor + \{ \bar{a}_{lj} \}) x_j = \lfloor \bar{b}_l \rfloor + \{ \bar{b}_l \}\] Rearranging the terms, the Gomory fractional cut is given by: \[\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}\]

Properties and Violation by the Current LP Solution

The Gomory fractional cut is a valid inequality for the integer program. It is violated by the current LP solution $x^*$ because for the current basic feasible solution, $x_j = 0$ for all non-basic variables $j \in N$. Thus, for $x^*$, the left-hand side of the Gomory cut is $\sum_{j \in N} \{ \bar{a}_{lj} \} \cdot 0 = 0$. However, the right-hand side is $\{ \bar{b}_l \} > 0$ because we chose a basic variable $x_{B_l}$ with a fractional value $\bar{b}_l$. Therefore, $0 \geq \{ \bar{b}_l \}$ is false, meaning the current LP solution violates the Gomory fractional cut.

The process of generating Gomory cuts involves the following steps:

Solving the LP relaxation: This is the most computationally expensive part, typically done using the simplex method or interior-point methods. The complexity depends on the specific algorithm used but is generally polynomial in the size of the problem.
Identifying a fractional basic variable: This involves examining the values of the basic variables in the optimal LP solution, which takes $O(m)$ time, where $m$ is the number of basic variables (and constraints).
Extracting the relevant row from the simplex tableau: This takes $O(n)$ time, where $n$ is the number of variables (both basic and non-basic).
Computing the fractional parts: This involves computing the fractional part of each coefficient in the selected row, which takes $O(n)$ time.
Constructing the Gomory cut: This involves combining the fractional parts to form the inequality, which takes $O(n)$ time.

Overall, the complexity of generating a single Gomory cut is dominated by the complexity of solving the LP relaxation. Once the LP solution is obtained, generating a Gomory cut takes linear time with respect to the number of variables.

The Cutting Plane Algorithm

Algorithm Overview

Iterative Process of Adding Cuts

The cutting plane algorithm iteratively refines the LP relaxation by adding Gomory cuts. The general algorithm is as follows:

Start with the LP relaxation of the integer program. Let $P_0$ be the feasible region of the LP relaxation. Set $k = 0$. Solve the LP relaxation over $P_k$ to obtain an optimal solution $x^{(k)}$. If $x^{(k)}$ is integer, then $x^{(k)}$ is an optimal solution to the integer program. Terminate. Else, select a basic variable $x_{B_l}$ in the optimal LP solution that has a fractional value $\bar{b}_l$. Generate a Gomory cut (either integer or fractional form) from the row corresponding to $x_{B_l}$ in the simplex tableau. Let the cut be $\alpha^{(k+1)T} x \leq \beta^{(k+1)}$. Add the Gomory cut to the formulation: $P_{k+1} = P_k \cap \{x : \alpha^{(k+1)T} x \leq \beta^{(k+1)}\}$. Increment $k = k+1$.

Termination Condition: Integer Solution

The algorithm terminates when an optimal solution to the LP relaxation is found to be integer. At this point, since we have only added valid inequalities, this integer solution is guaranteed to be an optimal solution to the original integer programming problem.

Maintaining Standard Form

Adding Slack or Surplus Variables for Cuts

When we add a Gomory cut, which is typically in the form of an inequality, we need to convert it back into equation form to maintain the standard form required for the simplex method.

If a cut is of the form $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}$, we introduce a surplus variable $s_{k+1} \geq 0$ and rewrite the cut as $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j - s_{k+1} = \{ \bar{b}_l \}$. If a cut is of the form $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \leq \{ \bar{b}_l \}$, we introduce a slack variable $s_{k+1} \geq 0$ and rewrite the cut as $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j + s_{k+1} = \{ \bar{b}_l \}$. In either case, we add a new equation and a new variable to the system, and proceed to solve the new LP relaxation.

Detailed Example: Production Planning

Problem Description and Formulation

Consider a company that produces two products, A and B. Producing one unit of product A requires 2 hours of labor, and one unit of product B requires 5 hours of labor. A total of 30 labor hours are available. Each unit of product A creates 4 units of a byproduct C, while each unit of product B consumes 3 units of byproduct C. Excess production of C can be stored, but warehouse capacity for C is limited to 6 units. The profit from selling one unit of product A or B is the same, and the goal is to maximize total profit.

Let $x_1$ be the number of units of product A and $x_2$ be the number of units of product B to produce. Let $x_3$ represent the total profit. The problem can be formulated as follows: $$ \[\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 \leq 30 &\quad \text{(Labor hours constraint)} \\ & 4x_1 - 3x_2 \leq 6 &\quad \text{(Byproduct C storage constraint)} \\ & x_3 = x_1 + x_2 &\quad \text{(Profit definition)} \\ & x_1, x_2 \geq 0, x_3 \geq 0, x_1, x_2, x_3 \in \mathbb{Z} \end{aligned}\] \[ To convert to standard form, we rewrite the objective and constraints: \] \[\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 + x_4 = 30 \\ & 4x_1 - 3x_2 + x_5 = 6 \\ & x_1 + x_2 - x_3 = 0 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0, \quad x_1, x_2, x_3, x_4, x_5 \in \mathbb{Z} \end{aligned}\]

$$ Here, $x_4$ and $x_5$ are slack variables.

Initial LP Relaxation and Solution

Solving the LP relaxation of this problem using the simplex method, we obtain the optimal solution: \[x^{(0)} = \left(x_1, x_2, x_3, x_4, x_5\right) = \left(\frac{60}{13}, \frac{54}{13}, \frac{114}{13}, 0, 0\right) \approx (4.62, 4.15, 8.77, 0, 0)\] The objective value is $x_3 = \frac{114}{13} \approx 8.77$. This solution is fractional, so we need to generate a Gomory cut.

Generating the First Gomory Cut

We choose to generate a cut from the row corresponding to $x_3$ because its fractional part is the largest among $x_1, x_2, x_3$. The fractional part of $x_1 = 60/13$ is $8/13$, of $x_2 = 54/13$ is $2/13$, and of $x_3 = 114/13$ is $10/13$. The basic variables in the optimal solution are $x_1, x_2, x_3$, and non-basic are $x_4, x_5$. Expressing the system with respect to the basis $\{x_1, x_2, x_3\}$, the row for $x_3$ in the simplex tableau (after basis transformation, details omitted for brevity, as indicated in the transcription) is given as: \[x_3 + \frac{7}{26} x_4 + \frac{3}{26} x_5 = \frac{114}{13}\] The Gomory fractional cut is derived from this row using the non-basic variables $x_4$ and $x_5$: \[\{ \frac{7}{26} \} x_4 + \{ \frac{3}{26} \} x_5 \geq \{ \frac{114}{13} \}\] \[\frac{7}{26} x_4 + \frac{3}{26} x_5 \geq \frac{10}{13}\] Multiplying by 26 to clear denominators: \[7x_\[ 7x_4 + 3x_5 \geq 20\] Substituting back $x_4 = 30 - 2x_1 - 5x_2$ and $x_5 = 6 - 4x_1 + 3x_2$: \[7(30 - 2x_1 - 5x_2) + 3(6 - 4x_1 + 3x_2) \geq 20\] \[210 - 14x_1 - 35x_2 + 18 - 12x_1 + 9x_2 \geq 20\] \[228 - 26x_1 - 26x_2 \geq 20\] \[26x_1 + 26x_2 \leq 208\] \[x_1 + x_2 \leq 8\] This is the first Gomory cut.

Adding the Cut and Solving the New LP

We add the cut $x_1 + x_2 \leq 8$ to the LP relaxation. In standard form, we add a slack variable $x_6 \geq 0$: \[x_1 + x_2 + x_6 = 8\] The new LP problem is: $$ \[\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 + x_4 = 30 \\ & 4x_1 - 3x_2 + x_5 = 6 \\ & x_1 + x_2 - x_3 = 0 \\ & x_1 + x_2 + x_6 = 8 \\ & x_1, x_2, x_3, x_4, x_5, x_6 \geq 0 \end{aligned}\]

\[ Solving this new LP relaxation, we obtain the new optimal solution: \]x^{(1)} = (x_1, x_2, x_3, x_4, x_5, x_6) = (, , 8, , 0, 0) (4.29, 3.71, 8, 2.86, 0, 0)$$ The objective value is now $x_3 = 8$. This solution is still fractional because $x_1 = 30/7$, $x_2 = 26/7$, and $x_4 = 20/7$ are fractional.

Generating the Second Gomory Cut

We choose to generate a cut from the row corresponding to $x_4$. The basic variables are now $\{x_1, x_2, x_3, x_4\}$ and non-basic are $\{x_5, x_6\}$. The row for $x_4$ in the simplex tableau (after basis transformation for the new LP, again omitting details) is: \[x_4 + \frac{3}{7} x_5 - \frac{26}{7} x_6 = \frac{20}{7}\] The Gomory fractional cut is: \[\{ \frac{3}{7} \} x_5 + \{ -\frac{26}{7} \} x_6 \geq \{ \frac{20}{7} \}\] \[\frac{3}{7} x_5 + \{ -4 + \frac{2}{7} \} x_6 \geq \frac{6}{7}\] \[\frac{3}{7} x_5 + \frac{2}{7} x_6 \geq \frac{6}{7}\] Multiplying by 7 to clear denominators: \[3x_5 + 2x_6 \geq 6\] Substituting back $x_5 = 6 - 4x_1 + 3x_2$ and $x_6 = 8 - x_1 - x_2$: \[3(6 - 4x_1 + 3x_2) + 2(8 - x_1 - x_2) \geq 6\] \[18 - 12x_1 + 9x_2 + 16 - 2x_1 - 2x_2 \geq 6\] \[34 - 14x_1 + 7x_2 \geq 6\] \[14x_1 - 7x_2 \leq 28\] \[2x_1 - x_2 \leq 4\] This is the second Gomory cut.

Reaching the Optimal Integer Solution

We add the second cut $2x_1 - x_2 \leq 4$ to the formulation. In standard form, we add a slack variable $x_7 \geq 0$: \[2x_1 - x_2 + x_7 = 4\] Solving the LP relaxation with both cuts added, we obtain the optimal solution: \[x^{(2)} = \left(x_1, x_2, x_3, x_4, x_5, x_6, x_7\right) = \left(4, 4, 8, 2, 2, 0, 0\right)\] The objective value is $x_3 = 8$. Now, all variables are integer. Thus, we have found the optimal integer solution. The optimal production plan is to produce 4 units of product A and 4 units of product B, resulting in a maximum profit of 8.

In this example, we solved three LP relaxations: the initial relaxation and two subsequent relaxations after adding each Gomory cut. Each LP relaxation required solving a system of linear equations, which is the main computational cost. The number of LP relaxations needed depends on the specific problem and the effectiveness of the generated cuts.

Conclusion

In this lecture, we explored the cutting plane method as a technique for solving integer linear programming (ILP) problems. We discussed its historical context, its core concepts, and the generation of Gomory cuts. The cutting plane method iteratively refines the feasible region of the LP relaxation by adding valid inequalities that cut off fractional solutions. We examined Chvátal inequalities and Gomory cuts as specific types of valid inequalities used in this method. Through a detailed production planning example, we demonstrated the step-by-step process of generating Gomory cuts and adding them to the LP relaxation until an integer optimal solution is obtained.

**Key Takeaways:**

The cutting plane method provides an alternative to branch and bound for solving ILPs.
Gomory cuts are derived from the simplex tableau and are guaranteed to cut off the current fractional LP solution.
Iteratively adding cuts leads to a tighter relaxation and eventually to an integer optimal solution.
The method relies on solving a sequence of LP relaxations, with the formulation growing at each step as cuts are added.

**Further Topics to Consider:**

Different types of cutting planes beyond Gomory cuts (e.g., Mixed Integer Rounding cuts, Lift-and-Project cuts).
Strategies for selecting which cut to add at each iteration (e.g., selecting cuts based on the magnitude of the fractional part, or using heuristics to estimate the strength of a cut).
Convergence properties and efficiency of cutting plane methods, including theoretical results on finite convergence and practical considerations for implementation.
Integration of cutting planes with branch and bound to create hybrid branch and cut algorithms, which are currently the most effective methods for solving general ILPs.

This lecture provides a foundational understanding of the cutting plane method, setting the stage for more advanced topics in integer programming and optimization.

--- title: "The Cutting Plane Method for Integer Linear Programming" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture introduces the cutting plane method, an alternative to the dominant branch and bound technique for solving Integer Linear Programming (ILP) problems. Although branch and bound is the current state-of-the-art, the cutting plane method has regained attention, particularly through its integration into branch and cut algorithms. We will explore the foundational concepts of this method, including its historical context, core principles, and the generation of cutting planes, with a focus on Chvátal inequalities and Gomory cuts. We will examine how these cuts iteratively refine the feasible region of the linear programming relaxation, ultimately leading to an integer solution. **Outline:** - Motivation and Historical Context - Core Concepts of the Cutting Plane Method - Chvátal Inequalities - Gomory Cuts - The Cutting Plane Algorithm - Detailed Example: Production Planning # The Cutting Plane Method ## Motivation and Historical Context ### Early Challenges and Limitations Proposed in the 1960s, the cutting plane method initially faced significant practical limitations. The computational demands, in terms of both numerical precision and processing power, were too high for the computers available at the time. Consequently, the method was largely of theoretical interest, with implementation challenges hindering its practical application. ### Revival and Integration with Branch and Bound The 1980s and 1990s witnessed a revival of the cutting plane method, driven by advancements in computer technology and theoretical insights that addressed some of the numerical issues. As computers became faster and more powerful, and as new theoretical developments emerged to tackle numerical instability, the method became more viable. Researchers began exploring the integration of cutting plane techniques with the branch and bound method, leading to the development of *branch and cut* algorithms. In this hybrid approach, cutting planes are used to strengthen the linear programming relaxation within the branch and bound framework. Adding valid inequalities as cuts reduces the feasible region, leading to tighter formulations and potentially more efficient branch and bound searches. This combined approach, branch and bound with cutting planes, is known as branch and cut, though we will not explore it in detail here. ## Core Concepts ### Problem Formulation in Standard Form The cutting plane method is conveniently described when the ILP problem is in standard form: $$\begin{aligned} \max & \quad c^T x \\ \text{s.t.} & \quad Ax = b \\ & \quad x \geq 0 \\ & \quad x \in \mathbb{Z}^n \end{aligned}$$ Here, $c \in \mathbb{R}^n$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$. We define: - $P = \{x \in \mathbb{R}^n : Ax = b, x \geq 0\}$: The polyhedron defined by the constraints of the LP relaxation, representing the feasible region in the continuous space. - $X = P \cap \mathbb{Z}^n$: The set of integer solutions within $P$. - $P_I = \text{conv}(X)$: The convex hull of the integer solutions, which is the ideal polyhedron to optimize over for solving the integer program as a linear program. ### LP Relaxation and Fractional Solutions Similar to branch and bound, the cutting plane method begins by solving the Linear Programming (LP) relaxation of the integer problem. Let $x^*$ be the optimal solution to the LP relaxation. If $x^*$ is an integer vector ($x^* \in \mathbb{Z}^n$), it is also an optimal solution to the original ILP, and we are done. However, if $x^*$ contains fractional components, it is not feasible for the ILP. In this case, we need a way to \"cut off\" this fractional solution without removing any integer feasible solutions. ### The Role of Valid Inequalities If the optimal LP solution $x^*$ is fractional, then $x^* \notin P_I$. Thus, there must exist at least one valid inequality for $P_I$ that is violated by $x^*$. ::: tcolorbox A *valid inequality* for $P_I$ is a linear inequality $\alpha^T x \leq \beta$ such that $\alpha^T x \leq \beta$ holds for all $x \in P_I$. ::: For our fractional solution $x^*$, we have $\alpha^T x^* > \beta$. This inequality can \"cut off\" the fractional solution $x^*$ from the feasible region while preserving all integer solutions. ### Geometric Interpretation of Cutting Planes Geometrically, consider the polyhedron $P$ and its integer hull $P_I$. Let $x^*$ be an optimal vertex of $P$ obtained by solving the LP relaxation. If $x^*$ is fractional, it lies outside $P_I$. A cutting plane is a hyperplane that separates $x^*$ from $P_I$. [1](#fig:cutting_plane_geometric){reference-type="ref+Label" reference="fig:cutting_plane_geometric"} illustrates this. The outer polyhedron represents $P$, and the inner dashed polyhedron represents $P_I$. The point $x^*$ is an optimal vertex in $P$ but not in $P_I$. The red line represents a cutting plane that is valid for $P_I$ (all points in $P_I$ satisfy it) but is violated by $x^*$. <figure id="fig:cutting_plane_geometric"> <figcaption>Geometric interpretation of a cutting plane separating a fractional optimal solution <span class="math inline">$x^*$</span> from the integer hull <span class="math inline">$P_I$</span>.</figcaption> </figure> ## Iterative Cutting Process ### Adding Cuts to the Formulation Starting with the initial LP relaxation $P = P_0$, if the optimal solution $x^{(0)}$ is fractional, we find a valid inequality (a cut) $\alpha^{(1)T} x \leq \beta^{(1)}$ that is valid for $P_I$ but violated by $x^{(0)}$. We add this cut to the formulation, creating a new polyhedron $P_1 = P_0 \cap \{x : \alpha^{(1)T} x \leq \beta^{(1)}\}$. This new polyhedron $P_1$ is a tighter relaxation of $P_I$ because $P_I \subseteq P_1 \subsetneq P_0$. ### Progressive Reduction of the Feasible Region We repeat this process iteratively. At iteration $k$, we have a polyhedron $P_k$. We solve the LP relaxation over $P_k$ to obtain an optimal solution $x^{(k)}$. If $x^{(k)}$ is integer, we have found the optimal integer solution and terminate. If $x^{(k)}$ is fractional, we find a new valid inequality $\alpha^{(k+1)T} x \leq \beta^{(k+1)}$ that is valid for $P_I$ but violated by $x^{(k)}$. We then form a new polyhedron $P_{k+1} = P_k \cap \{x : \alpha^{(k+1)T} x \leq \beta^{(k+1)}\}$. This generates a sequence of polyhedra $P_0 \supsetneq P_1 \supsetneq P_2 \supsetneq \dots \supseteq P_I$, progressively reducing the feasible region towards the integer hull $P_I$. ### Convergence and Termination Criteria The iterative process continues until we obtain an optimal solution $x^{(k)}$ that is integer. Since each cut removes a portion of the feasible region containing the current fractional optimal solution, and we are always adding valid inequalities, the sequence of optimal LP values is monotonically decreasing and bounded below by the optimal integer solution value. A key result, attributed to Chvátal, guarantees that for certain types of cuts, this process is finite, meaning that we will eventually reach an integer optimal solution in a finite number of iterations. ### The Separation Problem The crucial step in the cutting plane method is finding a valid inequality that separates the current fractional solution $x^{(k)}$ from the integer hull $P_I$. This is known as the *separation problem*. ::: tcolorbox Given a fractional point $x^{(k)}$, the separation problem is to find a valid inequality $\alpha^T x \leq \beta$ for $P_I$ such that $\alpha^T x^{(k)} > \beta$. ::: The efficiency of a cutting plane algorithm heavily depends on the ability to solve the separation problem effectively, i.e., to find \"deep\" cuts that significantly reduce the feasible region and lead to faster convergence. # Chvátal Inequalities ## Characterizing Valid Inequalities for Integer Programs Chvátal inequalities provide a systematic way to generate valid inequalities for integer programs. They are fundamental to understanding the structure of the integer hull $P_I$. A key result in integer programming theory states that all valid inequalities for $P_I$ can be derived using a process based on Chvátal inequalities. ## Derivation of Chvátal Inequalities ### Using Multipliers and Rounding Operations Consider a system of linear equations in standard form $Ax = b$ defining a polyhedron $P$, where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$. Let $X = P \cap \mathbb{Z}^n$ be the set of integer points within $P$. To derive a Chvátal inequality, we take a linear combination of the equations in $Ax = b$ with non-negative multipliers $u \in \mathbb{R}^m, u \geq 0$. Multiplying the system $Ax = b$ by $u^T$ from the left, we get $u^T A x = u^T b$. For any integer solution $x \in X$, this equation holds. Now, consider the inequality $\sum_{j=1}^n (u^T A)_j x_j \leq u^T b$. Since we are interested in integer solutions $x \in \mathbb{Z}^n$, we can strengthen this inequality by rounding down the coefficients on the left-hand side. For each coefficient $(u^T A)_j$, we take the floor value $\lfloor (u^T A)_j \rfloor$. This gives us: $$\sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq u^T b$$ Since the left-hand side is an integer for any $x \in \mathbb{Z}^n$, we can also round down the right-hand side without losing any integer solutions. This leads to the Chvátal inequality: $$\sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq \lfloor u^T b \rfloor$$ This inequality is valid for all integer solutions $x \in X$. ## The Chvátal Closure ### Definition and Properties of the Closure Let $P = \{x \in \mathbb{R}^n : Ax = b, x \geq 0\}$. The *Chvátal closure* of $P$, denoted by $C(P)$, is defined as the intersection of $P$ with all possible Chvátal inequalities derived from $Ax = b, x \geq 0$. Formally, $$C(P) = P \cap \{x \in \mathbb{R}^n : \sum_{j=1}^n \lfloor (u^T A)_j \rfloor x_j \leq \lfloor u^T b \rfloor \text{ for all } u \geq 0 \}.$$ A significant result by Chvátal is that $C(P)$ is also a polyhedron. This is a non-trivial result because there are infinitely many possible non-negative multiplier vectors $u$, potentially leading to infinitely many Chvátal inequalities. However, the set of all such inequalities defines a polyhedron. ### Iterated Closures and Finite Convergence We can iteratively apply the Chvátal closure operation. Let $P^{(0)} = P$, and define $P^{(k+1)} = C(P^{(k)})$ for $k \geq 0$. This generates a sequence of polyhedra $P^{(0)} \supseteq P^{(1)} \supseteq P^{(2)} \supseteq \dots \supseteq P_I$. Chvátal proved that for any polyhedron $P$ representing the LP relaxation of an integer program, there exists a finite integer $k$ such that $P^{(k)} = P_I$. This means that by repeatedly generating and adding Chvátal inequalities, we can eventually obtain the integer hull $P_I$. This theoretical result underpins the convergence of cutting plane methods. ## Illustrative Example Consider the system: $$\begin{aligned} 2x_1 + 5x_2 + x_3 &= 30 \\ 4x_1 - 3x_2 + x_4 &= 6 \\ x_1, x_2, x_3, x_4 &\geq 0, \quad x_1, x_2, x_3, x_4 \in \mathbb{Z} \end{aligned}$$ We want to derive a Chvátal inequality. Let's choose multipliers $u = (5/6, 11/12)^T \geq 0$. Multiplying the first equation by $5/6$ and the second by $11/12$ and summing them, we get: $$\left(\frac{5}{6} \cdot 2 + \frac{11}{12} \cdot 4\right) x_1 + \left(\frac{5}{6} \cdot 5 + \frac{11}{12} \cdot (-3)\right) x_2 + \left(\frac{5}{6} \cdot 1 + \frac{11}{12} \cdot 0\right) x_3 + \left(\frac{5}{6} \cdot 0 + \frac{11}{12} \cdot 1\right) x_4 = \frac{5}{6} \cdot 30 + \frac{11}{12} \cdot 6$$ Simplifying the coefficients: $$\frac{16}{3} x_1 + \frac{17}{12} x_2 + \frac{5}{6} x_3 + \frac{11}{12} x_4 = 30.5$$ Now, we take the floor of each coefficient on the left side: $$\lfloor \frac{16}{3} \rfloor x_1 + \lfloor \frac{17}{12} \rfloor x_2 + \lfloor \frac{5}{6} \rfloor x_3 + \lfloor \frac{11}{12} \rfloor x_4 \leq 30.5$$ $$5x_1 + 1x_2 + 0x_3 + 0x_4 \leq 30.5$$ Since the left-hand side is an integer for integer values of $x_i$, we can take the floor of the right-hand side: $$5x_1 + x_2 \leq 30$$ Thus, $5x_1 + x_2 \leq 30$ is a Chvátal inequality valid for integer solutions of the given system. ::: tcolorbox The process of generating Chvátal inequalities involves choosing multipliers and performing rounding operations. - Choosing multipliers $u$: In principle, there are infinitely many possible choices for the multiplier vector $u$. The effectiveness of the resulting inequality depends heavily on this choice. Finding good multipliers is a crucial aspect of the separation problem. - Rounding operations: Once the multipliers are chosen, the rounding operations are straightforward and can be done in linear time with respect to the number of variables, $O(n)$. - Finding all Chvátal inequalities: Finding all possible Chvátal inequalities is computationally intractable, as it would involve exploring an infinite space of multipliers. - Determining the Chvátal closure: Determining the complete Chvátal closure is also computationally challenging. However, in practice, we often generate a subset of Chvátal inequalities that are considered effective. ::: # Gomory Cuts ## Gomory Cuts from the Simplex Tableau ### Expressing the System with Respect to the Optimal Basis Gomory cuts are a specific type of cutting plane that can be derived from the optimal simplex tableau of the LP relaxation. Suppose we have solved the LP relaxation and obtained an optimal basis $B$. We can express the system of equations in terms of basic and non-basic variables. Let $N$ be the set of indices of non-basic variables. For each basic variable $x_{B_i}$, the simplex tableau provides an equation of the form: $$x_{B_i} + \sum_{j \in N} \bar{a}_{ij} x_j = \bar{b}_i$$ where $\bar{a}_{ij}$ are the entries in the tableau under non-basic variable $x_j$ in the row corresponding to basic variable $x_{B_i}$, and $\bar{b}_i$ is the value of the basic variable $x_{B_i}$ in the current solution. The $\bar{a}_{ij}$ values represent the coefficients of the non-basic variables in the expression for the basic variable $x_{B_i}$, and $\bar{b}_i$ represents the value of $x_{B_i}$ in the current basic feasible solution. ## Integer Form of Gomory Cuts If the optimal LP solution is fractional, there must be at least one basic variable $x_{B_l}$ that takes a fractional value $\bar{b}_l$. Consider the equation for this basic variable: $$x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j = \bar{b}_l$$ Since we require integer solutions, for any integer solution $x$, the left-hand side $x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j$ must be an integer. Therefore, it must be less than or equal to the floor of the right-hand side. This gives us the integer form of the Gomory cut: $$x_{B_l} + \sum_{j \in N} \lfloor \bar{a}_{lj} \rfloor x_j \leq \lfloor \bar{b}_l \rfloor$$ Rearranging terms to isolate non-basic variables on one side, we get the Gomory integer cut as: $$\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}$$ ## Fractional Form of Gomory Cuts ### Notation for Fractional Parts ::: tcolorbox Let $\{ z \} = z - \lfloor z \rfloor$ denote the fractional part of a real number $z$. For example, $\{ 3.2 \} = 0.2$, $\{ 8.9 \} = 0.9$, and $\{ 5 \} = 0$. Note that $0 \leq \{ z \} < 1$. ::: ### Derivation of Fractional Cuts Consider again the equation from the simplex tableau for a basic variable $x_{B_l}$ with a fractional value $\bar{b}_l$: $$x_{B_l} + \sum_{j \in N} \bar{a}_{lj} x_j = \bar{b}_l$$ We can rewrite each coefficient and the right-hand side as the sum of their integer and fractional parts: $$x_{B_l} + \sum_{j \in N} (\lfloor \bar{a}_{lj} \rfloor + \{ \bar{a}_{lj} \}) x_j = \lfloor \bar{b}_l \rfloor + \{ \bar{b}_l \}$$ Rearranging the terms, the Gomory fractional cut is given by: $$\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}$$ ### Properties and Violation by the Current LP Solution The Gomory fractional cut is a valid inequality for the integer program. It is violated by the current LP solution $x^*$ because for the current basic feasible solution, $x_j = 0$ for all non-basic variables $j \in N$. Thus, for $x^*$, the left-hand side of the Gomory cut is $\sum_{j \in N} \{ \bar{a}_{lj} \} \cdot 0 = 0$. However, the right-hand side is $\{ \bar{b}_l \} > 0$ because we chose a basic variable $x_{B_l}$ with a fractional value $\bar{b}_l$. Therefore, $0 \geq \{ \bar{b}_l \}$ is false, meaning the current LP solution violates the Gomory fractional cut. ::: tcolorbox The process of generating Gomory cuts involves the following steps: - Solving the LP relaxation: This is the most computationally expensive part, typically done using the simplex method or interior-point methods. The complexity depends on the specific algorithm used but is generally polynomial in the size of the problem. - Identifying a fractional basic variable: This involves examining the values of the basic variables in the optimal LP solution, which takes $O(m)$ time, where $m$ is the number of basic variables (and constraints). - Extracting the relevant row from the simplex tableau: This takes $O(n)$ time, where $n$ is the number of variables (both basic and non-basic). - Computing the fractional parts: This involves computing the fractional part of each coefficient in the selected row, which takes $O(n)$ time. - Constructing the Gomory cut: This involves combining the fractional parts to form the inequality, which takes $O(n)$ time. Overall, the complexity of generating a single Gomory cut is dominated by the complexity of solving the LP relaxation. Once the LP solution is obtained, generating a Gomory cut takes linear time with respect to the number of variables. ::: # The Cutting Plane Algorithm ## Algorithm Overview ### Iterative Process of Adding Cuts The cutting plane algorithm iteratively refines the LP relaxation by adding Gomory cuts. The general algorithm is as follows: :::: tcolorbox ::: algorithmic Start with the LP relaxation of the integer program. Let $P_0$ be the feasible region of the LP relaxation. Set $k = 0$. Solve the LP relaxation over $P_k$ to obtain an optimal solution $x^{(k)}$. If $x^{(k)}$ is integer, then $x^{(k)}$ is an optimal solution to the integer program. Terminate. Else, select a basic variable $x_{B_l}$ in the optimal LP solution that has a fractional value $\bar{b}_l$. Generate a Gomory cut (either integer or fractional form) from the row corresponding to $x_{B_l}$ in the simplex tableau. Let the cut be $\alpha^{(k+1)T} x \leq \beta^{(k+1)}$. Add the Gomory cut to the formulation: $P_{k+1} = P_k \cap \{x : \alpha^{(k+1)T} x \leq \beta^{(k+1)}\}$. Increment $k = k+1$. ::: :::: ### Termination Condition: Integer Solution The algorithm terminates when an optimal solution to the LP relaxation is found to be integer. At this point, since we have only added valid inequalities, this integer solution is guaranteed to be an optimal solution to the original integer programming problem. ## Maintaining Standard Form ### Adding Slack or Surplus Variables for Cuts When we add a Gomory cut, which is typically in the form of an inequality, we need to convert it back into equation form to maintain the standard form required for the simplex method. If a cut is of the form $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \geq \{ \bar{b}_l \}$, we introduce a surplus variable $s_{k+1} \geq 0$ and rewrite the cut as $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j - s_{k+1} = \{ \bar{b}_l \}$. If a cut is of the form $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j \leq \{ \bar{b}_l \}$, we introduce a slack variable $s_{k+1} \geq 0$ and rewrite the cut as $\sum_{j \in N} \{ \bar{a}_{lj} \} x_j + s_{k+1} = \{ \bar{b}_l \}$. In either case, we add a new equation and a new variable to the system, and proceed to solve the new LP relaxation. ## Detailed Example: Production Planning ### Problem Description and Formulation Consider a company that produces two products, A and B. Producing one unit of product A requires 2 hours of labor, and one unit of product B requires 5 hours of labor. A total of 30 labor hours are available. Each unit of product A creates 4 units of a byproduct C, while each unit of product B consumes 3 units of byproduct C. Excess production of C can be stored, but warehouse capacity for C is limited to 6 units. The profit from selling one unit of product A or B is the same, and the goal is to maximize total profit. Let $x_1$ be the number of units of product A and $x_2$ be the number of units of product B to produce. Let $x_3$ represent the total profit. The problem can be formulated as follows: $$\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 \leq 30 &\quad \text{(Labor hours constraint)} \\ & 4x_1 - 3x_2 \leq 6 &\quad \text{(Byproduct C storage constraint)} \\ & x_3 = x_1 + x_2 &\quad \text{(Profit definition)} \\ & x_1, x_2 \geq 0, x_3 \geq 0, x_1, x_2, x_3 \in \mathbb{Z} \end{aligned}$$ To convert to standard form, we rewrite the objective and constraints: $$\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 + x_4 = 30 \\ & 4x_1 - 3x_2 + x_5 = 6 \\ & x_1 + x_2 - x_3 = 0 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0, \quad x_1, x_2, x_3, x_4, x_5 \in \mathbb{Z} \end{aligned}$$ Here, $x_4$ and $x_5$ are slack variables. ### Initial LP Relaxation and Solution Solving the LP relaxation of this problem using the simplex method, we obtain the optimal solution: $$x^{(0)} = \left(x_1, x_2, x_3, x_4, x_5\right) = \left(\frac{60}{13}, \frac{54}{13}, \frac{114}{13}, 0, 0\right) \approx (4.62, 4.15, 8.77, 0, 0)$$ The objective value is $x_3 = \frac{114}{13} \approx 8.77$. This solution is fractional, so we need to generate a Gomory cut. ### Generating the First Gomory Cut We choose to generate a cut from the row corresponding to $x_3$ because its fractional part is the largest among $x_1, x_2, x_3$. The fractional part of $x_1 = 60/13$ is $8/13$, of $x_2 = 54/13$ is $2/13$, and of $x_3 = 114/13$ is $10/13$. The basic variables in the optimal solution are $x_1, x_2, x_3$, and non-basic are $x_4, x_5$. Expressing the system with respect to the basis $\{x_1, x_2, x_3\}$, the row for $x_3$ in the simplex tableau (after basis transformation, details omitted for brevity, as indicated in the transcription) is given as: $$x_3 + \frac{7}{26} x_4 + \frac{3}{26} x_5 = \frac{114}{13}$$ The Gomory fractional cut is derived from this row using the non-basic variables $x_4$ and $x_5$: $$\{ \frac{7}{26} \} x_4 + \{ \frac{3}{26} \} x_5 \geq \{ \frac{114}{13} \}$$ $$\frac{7}{26} x_4 + \frac{3}{26} x_5 \geq \frac{10}{13}$$ Multiplying by 26 to clear denominators: $$7x_\[ 7x_4 + 3x_5 \geq 20$$ Substituting back $x_4 = 30 - 2x_1 - 5x_2$ and $x_5 = 6 - 4x_1 + 3x_2$: $$7(30 - 2x_1 - 5x_2) + 3(6 - 4x_1 + 3x_2) \geq 20$$ $$210 - 14x_1 - 35x_2 + 18 - 12x_1 + 9x_2 \geq 20$$ $$228 - 26x_1 - 26x_2 \geq 20$$ $$26x_1 + 26x_2 \leq 208$$ $$x_1 + x_2 \leq 8$$ This is the first Gomory cut. ### Adding the Cut and Solving the New LP We add the cut $x_1 + x_2 \leq 8$ to the LP relaxation. In standard form, we add a slack variable $x_6 \geq 0$: $$x_1 + x_2 + x_6 = 8$$ The new LP problem is: $$\begin{aligned} \max \quad & x_3 \\ \text{s.t.} \quad & 2x_1 + 5x_2 + x_4 = 30 \\ & 4x_1 - 3x_2 + x_5 = 6 \\ & x_1 + x_2 - x_3 = 0 \\ & x_1 + x_2 + x_6 = 8 \\ & x_1, x_2, x_3, x_4, x_5, x_6 \geq 0 \end{aligned}$$ Solving this new LP relaxation, we obtain the new optimal solution: $$x^{(1)} = \left(x_1, x_2, x_3, x_4, x_5, x_6\right) = \left(\frac{30}{7}, \frac{26}{7}, 8, \frac{20}{7}, 0, 0\right) \approx (4.29, 3.71, 8, 2.86, 0, 0)$$ The objective value is now $x_3 = 8$. This solution is still fractional because $x_1 = 30/7$, $x_2 = 26/7$, and $x_4 = 20/7$ are fractional. ### Generating the Second Gomory Cut We choose to generate a cut from the row corresponding to $x_4$. The basic variables are now $\{x_1, x_2, x_3, x_4\}$ and non-basic are $\{x_5, x_6\}$. The row for $x_4$ in the simplex tableau (after basis transformation for the new LP, again omitting details) is: $$x_4 + \frac{3}{7} x_5 - \frac{26}{7} x_6 = \frac{20}{7}$$ The Gomory fractional cut is: $$\{ \frac{3}{7} \} x_5 + \{ -\frac{26}{7} \} x_6 \geq \{ \frac{20}{7} \}$$ $$\frac{3}{7} x_5 + \{ -4 + \frac{2}{7} \} x_6 \geq \frac{6}{7}$$ $$\frac{3}{7} x_5 + \frac{2}{7} x_6 \geq \frac{6}{7}$$ Multiplying by 7 to clear denominators: $$3x_5 + 2x_6 \geq 6$$ Substituting back $x_5 = 6 - 4x_1 + 3x_2$ and $x_6 = 8 - x_1 - x_2$: $$3(6 - 4x_1 + 3x_2) + 2(8 - x_1 - x_2) \geq 6$$ $$18 - 12x_1 + 9x_2 + 16 - 2x_1 - 2x_2 \geq 6$$ $$34 - 14x_1 + 7x_2 \geq 6$$ $$14x_1 - 7x_2 \leq 28$$ $$2x_1 - x_2 \leq 4$$ This is the second Gomory cut. ### Reaching the Optimal Integer Solution We add the second cut $2x_1 - x_2 \leq 4$ to the formulation. In standard form, we add a slack variable $x_7 \geq 0$: $$2x_1 - x_2 + x_7 = 4$$ Solving the LP relaxation with both cuts added, we obtain the optimal solution: $$x^{(2)} = \left(x_1, x_2, x_3, x_4, x_5, x_6, x_7\right) = \left(4, 4, 8, 2, 2, 0, 0\right)$$ The objective value is $x_3 = 8$. Now, all variables are integer. Thus, we have found the optimal integer solution. The optimal production plan is to produce 4 units of product A and 4 units of product B, resulting in a maximum profit of 8. ::: tcolorbox In this example, we solved three LP relaxations: the initial relaxation and two subsequent relaxations after adding each Gomory cut. Each LP relaxation required solving a system of linear equations, which is the main computational cost. The number of LP relaxations needed depends on the specific problem and the effectiveness of the generated cuts. ::: # Conclusion In this lecture, we explored the cutting plane method as a technique for solving integer linear programming (ILP) problems. We discussed its historical context, its core concepts, and the generation of Gomory cuts. The cutting plane method iteratively refines the feasible region of the LP relaxation by adding valid inequalities that cut off fractional solutions. We examined Chvátal inequalities and Gomory cuts as specific types of valid inequalities used in this method. Through a detailed production planning example, we demonstrated the step-by-step process of generating Gomory cuts and adding them to the LP relaxation until an integer optimal solution is obtained. \*\*Key Takeaways:\*\* - The cutting plane method provides an alternative to branch and bound for solving ILPs. - Gomory cuts are derived from the simplex tableau and are guaranteed to cut off the current fractional LP solution. - Iteratively adding cuts leads to a tighter relaxation and eventually to an integer optimal solution. - The method relies on solving a sequence of LP relaxations, with the formulation growing at each step as cuts are added. \*\*Further Topics to Consider:\*\* - Different types of cutting planes beyond Gomory cuts (e.g., Mixed Integer Rounding cuts, Lift-and-Project cuts). - Strategies for selecting which cut to add at each iteration (e.g., selecting cuts based on the magnitude of the fractional part, or using heuristics to estimate the strength of a cut). - Convergence properties and efficiency of cutting plane methods, including theoretical results on finite convergence and practical considerations for implementation. - Integration of cutting planes with branch and bound to create hybrid branch and cut algorithms, which are currently the most effective methods for solving general ILPs. This lecture provides a foundational understanding of the cutting plane method, setting the stage for more advanced topics in integer programming and optimization.