Section 8.2 Cutting-Plane Method
We continue our journey through integer optimization, and examine a second method to solve these problems which is geometrically oriented.
Exploration 8.2.1.
Define two additional inequalities such that the following are true:
No inequality eliminates any feasible integer solution of the original problem.
No boundary hyperplane is parallel to the objective function plane.
With the additional inequalities, the optimal solution to the linear relaxation is the optimal integer solution previously found to
Exploration 8.1.1.
The boundary for these additional inequalities are reffered to as cutting hyperplanes. We wish to determine how to find such cutting hyperplanes.
Activity 8.2.2.
In this activity, we motivate the math behind the cutting-plane method.
Let \(x_1^*, \ldots, x_m^*, \ldots, x_{m+n}^*\) be a feasible solution of the relaxation of a canonical integer maximization problem, where the \(x_i\) are basic (slack) variables and the \(x_j\) are non-basic variables.
We consider the constraint
\begin{equation*}
x_i+\sum_j a_{ij}x_j=b_i.
\end{equation*}
|
\(\cdots\) |
\(x_j\) |
\(\cdots\) |
\(-1\) |
|
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
\(=-?\) |
|
\(\cdots\) |
\(a_{ij}\) |
\(\cdots\) |
\(b_i\) |
\(=-x_i\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(\vdots\) |
\(=-?\) |
|
\(\cdots\) |
\(\cdots\) |
\(\cdots\) |
\(?\) |
\(=f\) |
(a)
Explain why the above equality is equivalent to
\begin{equation*}
x_i+\sum_j \lfloor a_{ij} \rfloor x_j - \lfloor b_i\rfloor =(b_i - \lfloor b_i \rfloor) - \sum_j (a_{ij} - \lfloor a_{ij} \rfloor)x_j
\end{equation*}
(b)
Show that for any feasible integeral solution of the left hand side off the equality in (2) is an integer.
(c)
Show that the right hand side of the equation in (2) is strictly less than 1 for any feasible solution.
(d)
For any integral solution, what is a non-negative integer upper bound for \((b_i - \lfloor b_i \rfloor) - \sum_j (a_{ij} - \lfloor a_{ij} \rfloor)x_j\text{?}\)
(e)
Show that
\begin{equation*}
\sum_j (\lfloor a_{ij} \rfloor - a_{ij})x_j \leq (\lfloor b_i \rfloor - b_i)
\end{equation*}
for any feasible integral solution to the relaxation of the integer optimization problem.
We call the hyperplane \(\sum_j (\lfloor a_{ij} \rfloor - a_{ij})x_j = (\lfloor b_i \rfloor - b_i)\) a cutting-plane.
(f)
Show that if \(b_i\) is non-integral, then by adding this constraint, the solution \(x_1^*, \ldots, x_m^*, \ldots, x_{m+n}^*\) is no longer feasible.
Activity 8.2.3.
We now apply this idea to an integer problem.
Consider the integer optimization problem:
\begin{align*}
\textbf{Maximize: } f(x_1, x_2) \amp = -x_1+5x_2\\
\textbf{Subject to: } 3x_1+2x_2 \amp \leq 12\\
-3x_1+2x_2 \amp \leq 70\\
x_1, x_2 \amp \geq 0\\
x_1, x_2 \text{are integers.} \amp
\end{align*}
(a)
Solve the relaxation of this integer problem, and verify that this solution is not integral.
|
\(t_1\) |
\(t_2\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(b)
Take the second row
\(x_2=b_2-a_{21}x_1-a_{22}x_2\) and follow the procedure in
Activity 8.2.2 to generate a new constraint
\(a_{31}t_1+a_{32}t_2\leq b_3\text{:}\)
|
\(t_1\) |
\(t_2\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_3\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(c)
Using the fact that \(t_1=12-3x_1-2x_2, t_2=7+3x_1-2x_2\text{,}\) describe this cutting-plane \(a_{31}t_1+a_{32}t_2=b_3\) in terms of \(x_1, x_2\text{.}\)
(d)
Pivot of the entry
\(a_{31}\) and verify that the resulting basic solution is optimal and non-integral.
|
\(t_3\) |
\(t_2\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_1\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(e)
There is only one valid choice of row to generate a new constraint. Follow the procedure in
Activity 8.2.2 to generate a new constraint
\(a_{41}t_3+a_{42}t_2=b_4\)
|
\(t_3\) |
\(t_2\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_1\) |
|
\(a_{41}\) |
\(a_{42}\) |
\(b_4\) |
\(=-t_4\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(f)
Using the fact that \(t_3=-\frac{3}{4}+\frac{1}{4}t_1+\frac{1}{4}t_2\text{,}\) express this new cutting-plane \(a_{41}t_3+a_{42}t_2=b_4\) in terms of \(x_1, x_2\text{.}\)
(g)
Pivot on the entry
\(a_{42}\) and verify that the resulting basic solution is optimal and non-integral.
|
\(t_3\) |
\(t_4\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_1\) |
|
\(a_{41}\) |
\(a_{42}\) |
\(b_4\) |
\(=-t_2\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(h)
Use either the
\(t_1\) or
\(t_2\) row to generate a new constraint
\(a_{51}t_3+a_{52}t_4\leq b_5\text{.}\)
|
\(t_3\) |
\(t_4\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_1\) |
|
\(a_{41}\) |
\(a_{42}\) |
\(b_4\) |
\(=-t_2\) |
|
\(a_{51}\) |
\(a_{52}\) |
\(b_5\) |
\(=-t_5\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(i)
Using the fact that \(t_4=-\frac{1}{3}+\frac{2}{3}s_3+\frac{2}{3}t_2\text{,}\) express this new cutting-plane \(a_{51}t_3+a_{52}t_4=b_5\) in terms of \(x_1, x_2\text{.}\)
(j)
Pivot on the
\(a_{52}\) entry and verify that the resulting basic solution is optimal
and integral!
|
\(t_3\) |
\(t_5\) |
\(-1\) |
|
|
\(a_{11}\) |
\(a_{12}\) |
\(b_1\) |
\(=-x_1\) |
|
\(a_{21}\) |
\(a_{22}\) |
\(b_2\) |
\(=-x_2\) |
|
\(a_{31}\) |
\(a_{32}\) |
\(b_3\) |
\(=-t_1\) |
|
\(a_{41}\) |
\(a_{42}\) |
\(b_4\) |
\(=-t_2\) |
|
\(a_{51}\) |
\(a_{52}\) |
\(b_5\) |
\(=-t_3\) |
|
\(c_1\) |
\(c_2\) |
\(d\) |
\(=f\) |
(k)
Enter the coefficients for the objective function and the three cutting-planes in order that you found them, and drag the objective plane onto the optimal solution to the integer problem.
Definition 8.2.4. Gomory Cutting-Plane Algorithm.
The Gomory Cutting-Plane Algorithm for an optimization problem is as follows:
INITIALIZE: Begin with a canonical maximization integer optimization problem.
Solve the relaxation of the integer problem. If all the resulting \(b_i\) are integral STOP: you have found an optimal integral solution.
Select a \(b_i\) that is non integral and for that row, construct the additional bound: \(\sum_j (\lfloor a_{ij} \rfloor - a_{ij})x_j \leq (\lfloor b_i \rfloor - b_i)\text{.}\)
GOTO 2.
