Example 7.4 ended with a small scandal. A problem that takes \(25739\) nodes of branch-and-bound at \(n=15\) was solved at the root by one extra inequality, obtained by dividing the constraint by two and rounding. The cargo problem has the same feature: Example 5.1 showed that the single inequality \(x_1+x_2\le 4\) turns its relaxation into one whose optimum is the integer optimum. In both cases the inequality was produced by insight. Can it be produced by a procedure?
This chapter gives three answers. A general rounding rule converts any nonnegative combination of constraints into a new valid inequality. A special case of the rule, read off from the final simplex tableau, always cuts off the current fractional solution. And for constraints with combinatorial structure, knapsack rows and subtours, there are families of strong inequalities, too numerous to list, from which a violated member can be found by solving an auxiliary optimization problem. That auxiliary problem, separation, is what makes exponentially large formulations usable.
8.1 Valid inequalities and cuts
Definition 8.1 (valid inequality, cut). Let \(X\subseteq\mathbb Z^n\) . An inequality \(\alpha^{\top}x\le\beta\) is valid for \(X\) if every point of \(X\) satisfies it. Given a point \(\bar x\notin X\) , a valid inequality with \(\alpha^{\top}\bar x>\beta\) is a cut, or cutting plane, that separates \(\bar x\) from \(X\) .
Adding a valid inequality to a formulation yields another formulation of the same set, at least as strong, by Proposition 5.2. Adding a cut that separates the relaxation’s optimal solution \(\bar x\) yields a strictly stronger one in which \(\bar x\) is no longer available. The cutting-plane method repeats this: solve the relaxation; if its optimal solution is integral, stop, by Proposition 1.3; otherwise find a cut that separates it, add the cut, and solve again. Each round lowers the upper bound or at least removes the point that attained it.
Two things can go wrong, and the rest of the chapter is organized around avoiding them. An inequality may fail to be valid, in which case the method silently discards feasible solutions and may return a wrong answer. Or valid cuts may be too shallow, in which case the bound creeps down without ever reaching \(z^\star\) .
8.2 Rounding: Chvátal–Gomory cuts
Proposition 8.2 (Chvátal–Gomory rounding). Let \(X=\{x\in\mathbb Z^n:Ax\le b,\ x\ge 0\}\) and let \(\mu\ge 0\) be a vector of multipliers, one for each row of \(A\) . Then the inequality
is valid for \(X\) , where \(A_j\) denotes the \(j\) -th column of \(A\) .
Proof. Three steps, each using one property of \(X\) . First, since \(\mu\ge 0\) , multiplying the rows of \(Ax\le b\) by the multipliers and adding gives the valid inequality \(\sum_j(\mu^{\top}A_j)x_j\le\mu^{\top}b\) . Second, since \(x\ge 0\) , lowering each coefficient to its floor can only lower the left side, so \(\sum_j\lfloor\mu^{\top}A_j\rfloor x_j\le\mu^{\top}b\) is valid. Third, since \(x\) is an integer vector and the coefficients are now integers, the left side is an integer, and an integer that is at most \(\mu^{\top}b\) is at most \(\lfloor\mu^{\top}b\rfloor\) .
The first two steps produce inequalities valid for the whole relaxation; they cut off nothing. Only the third step uses integrality, and it is where fractional points are lost.
Example 8.1: The hull of the cargo set in two rounding steps
The cargo constraints are \(x_1+2x_2\le 8\) and \(3x_1+2x_2\le 11\) .
Take \(\mu=(\tfrac14,\tfrac14)\) . The combination is \(x_1+x_2\le\tfrac{19}4\) . Its coefficients are already integers, and rounding the right side gives
Take \(\mu=(0,\tfrac13)\) . The combination is \(x_1+\tfrac23x_2\le\tfrac{11}3\) ; flooring the coefficients gives \(x_1+0\cdot x_2\le\tfrac{11}3\) , and rounding the right side gives \(x_1\le 3\) .
These are exactly the two inequalities that, with nonnegativity, describe the convex hull of the cargo set in Example 5.1. The first separates the relaxation optimum \((3/2,13/4)\) , where \(x_1+x_2=4.75\) , and the second separates the vertex \((11/3,0)\) . Two applications of Proposition 8.2 have produced the ideal formulation.
The same rule explains the family of Example 7.4: the multiplier \(\tfrac12\) applied to \(2\sum_jx_j\le n\) gives \(\sum_jx_j\le\lfloor n/2\rfloor=(n-1)/2\) for odd \(n\) . And for the triangle of Example 6.3, adding the three node constraints \(x_e+x_f\le 1\) with multipliers \(\tfrac12\) gives \(x_1+x_2+x_3\le\lfloor\tfrac32\rfloor=1\) , which cuts off the fractional vertex \((\tfrac12,\tfrac12,\tfrac12)\) . The same argument applied to any odd set of \(2k+1\) nodes in any graph shows that a matching contains at most \(k\) edges inside the set; these odd-set inequalities, added to the node constraints, describe the convex hull of matchings in graphs that are not bipartite, a theorem of Edmonds.
Common mistake. Rounding without the hypotheses. Each step of the proof needs something: nonnegative multipliers, nonnegative variables, integer variables. Rounding the right side of \(3x_1+2x_2\le 11\) after dividing by \(2\) , to get “\(1.5x_1+x_2\le 5\) ”, is not justified, because the left side is not an integer for integer \(x\) ; and the result is invalid, since the optimal plan \((3,1)\) gives \(1.5\cdot 3+1=5.5\) . Flooring coefficients of variables that can be negative is simply wrong: with \(x_2\) free, \(x_1+\tfrac23x_2\le\tfrac{11}3\) does not imply \(x_1\le\tfrac{11}3\) . Before using a cut, check it against the proof, and when possible against a list of feasible points.
Proposition 8.2 leaves open which multipliers to use. There are infinitely many, most give useless inequalities, and the ones that worked above were chosen with the answer in view. The simplex method supplies a choice automatically.
8.3 Gomory’s cut from the simplex tableau
Write the relaxation with slack variables, so that all constraints are equations \(Ax+s=b\) with \((x,s)\ge 0\) . When \(A\) and \(b\) are integral, the slacks of an integer solution are integers too, so all variables of the enlarged system are nonnegative integers. Solving the relaxation by the simplex method of Continuous Optimization ends with an optimal basis and the final tableau, which expresses each basic variable in terms of the nonbasic ones. A row of the tableau reads
where \(x_{B_i}\) is the basic variable of that row, \(N\) is the set of nonbasic variables, all equal to zero at the current solution, and \(\bar b_i\) is the current value of \(x_{B_i}\) . Write \(f_{ij}=\bar a_{ij}-\lfloor\bar a_{ij}\rfloor\) and \(f_{i0}=\bar b_i-\lfloor\bar b_i\rfloor\) for the fractional parts, which lie in \([0,1)\) .
Proposition 8.3 (Gomory’s fractional cut). Suppose all variables are required to be nonnegative integers and \(\bar b_i\) is not an integer. Then
is satisfied by every feasible integer solution and violated by the current basic solution.
Proof. Let \(x\) be a feasible integer solution. Because \(x_j\ge 0\) and \(\lfloor\bar a_{ij}\rfloor\le\bar a_{ij}\) , the tableau row gives
The left side is an integer, so it is at most \(\lfloor\bar b_i\rfloor\) . Subtracting this inequality from the tableau row, which is an equation, gives \(\sum_{j\in N}f_{ij}x_j\ge f_{i0}\) . At the current basic solution every nonbasic variable is zero, so the left side is \(0\) , while \(f_{i0}>0\) .
The proof repeats the last two steps of the proof of Proposition 8.2, flooring coefficients of nonnegative variables and then rounding the right side, on one row of the tableau. The first step is different. A tableau row is a combination of the original equations with multipliers taken from a row of the inverse of the basis matrix, and these may be negative, so Proposition 8.2 does not apply literally; but the original constraints are equations once slacks are added, and an equation may be multiplied by a number of either sign. In that sense a Gomory cut is a rounding cut whose multipliers the simplex method supplies. Its advantage is the last sentence of the statement: whatever fractional vertex the simplex method stops at, a cut that removes it is available at no cost.
To continue, give the cut its own slack variable \(g\ge 0\) , writing it as \(\sum_{j\in N}f_{ij}x_j-g=f_{i0}\) . For integer solutions \(g\) is again an integer, because it equals \(\lfloor\bar b_i\rfloor-x_{B_i}-\sum_{j\in N}\lfloor\bar a_{ij}\rfloor x_j\) . So the enlarged problem is of the same kind and the process can be repeated.
Example 8.2: Two Gomory cuts solve the cargo problem
With slacks \(s_1,s_2\) the cargo constraints are \(x_1+2x_2+s_1=8\) and \(3x_1+2x_2+s_2=11\) . At the relaxation optimum the basic variables are \(x_1\) and \(x_2\) , and multiplying the system by the inverse of the basis matrix, computed in Example 6.1, gives the final tableau
First cut. In the row of \(x_1\) the fractional parts are \(f=\tfrac12\) for \(s_1\) , since \(-\tfrac12-\lfloor-\tfrac12\rfloor=-\tfrac12+1\) , and \(\tfrac12\) for \(s_2\) , and \(f_0=\tfrac12\) . The cut is \(\tfrac12s_1+\tfrac12s_2\ge\tfrac12\) , that is, \(s_1+s_2\ge 1\) . Substituting \(s_1=8-x_1-2x_2\) and \(s_2=11-3x_1-2x_2\) gives \(19-4x_1-4x_2\ge 1\) , or
The point \((3/2,13/4)\) has \(x_1+x_2=4.75\) and is cut off. Solving the relaxation again gives \(\bar x=(2,5/2)\) with value \(20\) .
Second cut. Let \(g_1=\tfrac12s_1+\tfrac12s_2-\tfrac12\) be the slack of the first cut. The new final tableau has the rows
The row of \(x_2\) has a fractional right side. Its fractional parts are \(0\) for \(s_2\) and \(\tfrac12\) for \(g_1\) , with \(f_0=\tfrac12\) , so the cut is \(\tfrac12g_1\ge\tfrac12\) , that is, \(g_1\ge 1\) . In the original variables \(g_1=\tfrac12(19-4x_1-4x_2)-\tfrac12=9-2x_1-2x_2\) , so the cut reads
Solving once more gives \(\bar x=(3,1)\) with value \(19\) , an integer point. By Proposition 1.3 it is optimal.
The bounds went \(20.5\) , \(20\) , \(19\) . The first Gomory cut was weaker than the cut \(x_1+x_2\le 4\) that Example 8.1 obtained in one step; the tableau chose valid multipliers, not the best ones. The intermediate point \((2,5/2)\) is the solution of node 2 of the branch-and-bound tree of Example 7.1, which is no accident: both methods are exploring the same polygon, one by slicing off a corner, the other by splitting it in two.
Theorem 8.4 (finite convergence of Gomory’s method). Consider an integer program whose data, including the objective coefficients, are integers and whose relaxation is bounded. The cutting-plane method with Gomory fractional cuts terminates after finitely many cuts with an integer optimal solution or a proof of infeasibility, provided the linear programs are solved by the lexicographic dual simplex method and each cut is generated from the first row with a fractional right side, the objective row being counted as the first row.
We do not prove this theorem of Gomory. Its importance is conceptual: integer programming can in principle be reduced to a finite sequence of linear programs. In practice the pure method is slow, since cuts become shallower and numerically delicate as they accumulate. What works is the combination anticipated in Chapter 7: a few rounds of cuts at the root and at selected nodes to raise the bound, then branching.
8.4 Cover inequalities for knapsack rows
General-purpose cuts ignore structure. Many models contain rows of the knapsack form \(\sum_jw_jx_j\le W\) with binary variables, and for these a stronger family is available.
Definition 8.5 (cover). For a knapsack constraint \(\sum_{j=1}^{n}w_jx_j\le W\) with positive weights and \(x\in\{0,1\}^n\) , a set \(C\) of items is a cover if \(\sum_{j\in C}w_j>W\) . A cover is minimal if removing any one item from it leaves a set that is not a cover.
Proposition 8.6 (cover inequality). If \(C\) is a cover, then
is valid for the knapsack set. If, moreover, \(E(C)\) consists of \(C\) together with every item whose weight is at least the largest weight in \(C\) , then the extended cover inequality \(\sum_{j\in E(C)}x_j\le\lvert C\rvert-1\) is also valid.
Proof. If a binary \(x\) had \(x_j=1\) for all \(j\in C\) , its weight would be at least \(\sum_{j\in C}w_j>W\) . So at least one item of \(C\) is absent, which is the first inequality. For the second, suppose a binary \(x\) selects at least \(\lvert C\rvert\) items of \(E(C)\) . Then the selected items of \(E(C)\setminus C\) are at least as numerous as the unselected items of \(C\) . Exchange each unselected item of \(C\) for a distinct selected item of \(E(C)\setminus C\) . No exchange increases the weight, since every item of \(E(C)\setminus C\) weighs at least as much as any item of \(C\) . The result selects all of \(C\) and weighs at most as much as \(x\) , so the weight of \(x\) is at least \(\sum_{j\in C}w_j>W\) and \(x\) is infeasible.
A cover inequality from a cover that is not minimal is implied by one from a minimal cover inside it, so only minimal covers matter. Even so there can be exponentially many of them. The question in a cutting-plane method is never “what are all the covers” but “is there one whose inequality the current point violates”.
Proposition 8.7 (separating cover inequalities). Let \(0\le\bar x\le 1\) . Some cover inequality is violated by \(\bar x\) if and only if the optimal value of
is less than \(1\) , and then the items with \(z_j=1\) form a violated cover. Here the weights and the capacity \(W\) are assumed to be integers, so that a weight exceeding \(W\) is a weight of at least \(W+1\) .
Proof. With \(z\) the indicator vector of a set \(C\) , the constraint says that \(C\) is a cover. The cover inequality is violated exactly when \(\sum_{j\in C}\bar x_j>\lvert C\rvert-1\) , that is, when \(\sum_{j\in C}(1-\bar x_j)<1\) , and the left side is the objective.
The separation problem is itself a knapsack problem, which sounds circular. It is not: it concerns a single row, it can be solved by the dynamic programming of Chapter 9 or simply heuristically, and a heuristic is acceptable here because failing to find a cut costs only strength, never correctness.
Example 8.3: Two cover cuts replace thirteen nodes
Return to the knapsack of Example 7.2, with weights \((11,12,8,7)\) , profits \((23,24,15,13)\) , and capacity \(26\) . The relaxation’s solution is \(\bar x=(1,1,\tfrac38,0)\) with value \(52.625\) .
Separation. The quantities \(1-\bar x_j\) are \(0,0,\tfrac58,1\) . A cover needs weight at least \(27\) . Items 1 and 2, which cost nothing in the separation objective, weigh \(23\) ; adding item 3 reaches \(31\) at cost \(\tfrac58<1\) . So \(C=\{1,2,3\}\) is a violated cover: \(\bar x_1+\bar x_2+\bar x_3=2.375>2\) .
First cut. Add \(x_1+x_2+x_3\le 2\) . The relaxation’s solution becomes \((1,1,0,\tfrac37)\) , with value \(47+13\cdot\tfrac37\approx 52.57\) .
Separation again. Now \(1-\bar x_j\) is \(0,0,1,\tfrac47\) . Items 1, 2, and 4 weigh \(30\) and cost \(\tfrac47<1\) : the cover \(C=\{1,2,4\}\) is violated, since \(1+1+\tfrac37>2\) .
Second cut. Add \(x_1+x_2+x_4\le 2\) . The relaxation’s solution is now \((1,0,1,1)\) with value \(51\) . It is integral, so it is optimal.
Two cuts and three linear programs did the work of the thirteen-node tree. The cuts also say something intelligible: items 1 and 2 are the two most attractive, and each cut states that once both are taken there is room for neither item 3 nor item 4. Forced to choose, the relaxation gives up item 2. The minimal covers of this row are \(\{1,2,3\}\) , \(\{1,2,4\}\) , and \(\{2,3,4\}\) ; the third was never needed.
8.5 Separation when the family is exponential
The subtour elimination constraints of Section 5.5 number about \(2^n\) , and Example 5.5 showed that they can raise a bound from \(8\) to \(24\) . They are usable because of the following fact.
Proposition 8.8 (separating subtour constraints by minimum cuts). Let \(\bar x\ge 0\) be indexed by the arcs of the complete directed graph on \(n\) cities and satisfy the constraints that one unit leaves and one unit enters each city. Regard \(\bar x_{ij}\) as the capacity of arc \((i,j)\) . Then \(\bar x\) violates some subtour constraint \(x(\delta^+(S))\ge 1\) , with \(S\) a nonempty proper subset of the cities, if and only if for some city \(k\ne 1\) the minimum capacity of a cut separating city \(1\) from city \(k\) is less than \(1\) ; and such a cut, or its complement, is a violated set \(S\) .
Proof. If \(S\) is a violated set, replace it by its complement if necessary so that \(1\in S\) ; this does not change the capacity, because summing the degree equations over \(S\) shows that the capacity leaving \(S\) equals the capacity entering it, which is the capacity leaving the complement. Then for any \(k\notin S\) the set \(S\) is a cut separating \(1\) from \(k\) of capacity less than \(1\) . Conversely, a cut of capacity less than \(1\) separating \(1\) from \(k\) is a set \(S\) with \(1\in S\) , \(k\notin S\) , and \(\bar x(\delta^+(S))<1\) .
By the max-flow min-cut theorem each of the \(n-1\) minimum cuts is found by a maximum-flow computation, so the separation problem for an exponential family is solved in polynomial time by the algorithm of Chapter 3. Sets with one city or \(n-1\) cities never appear, since the degree equations give them capacity exactly \(1\) .
Example 8.4: Three cuts out of fifty
Take the six cities of Example 5.5, numbered \(1,2,3\) in the left cluster and \(4,5,6\) in the right. Start with the assignment constraints only.
Round 1. The relaxation’s solution is the pair of triangles, with value \(8\) . No arc joins the clusters, so the minimum cut between city \(1\) and city \(4\) has capacity \(0\) , attained by \(S=\{1,2,3\}\) . Add \(x(\delta^+(\{1,2,3\}))\ge 1\) .
Round 2. The value jumps to \(24\) . One optimal solution of the new relaxation uses the arcs \(1\to 3\) , \(3\to 6\) , \(6\to 2\) , \(2\to 1\) together with the two-city subtour \(4\to 5\) , \(5\to 4\) . It satisfies the added constraint, since the arc \(3\to 6\) leaves the left cluster, and it costs \(1+10+10+1+1+1=24\) . The cut around \(S=\{4,5\}\) has capacity \(0\) . Add \(x(\delta^+(\{4,5\}))\ge 1\) .
Round 3. The value is still \(24\) . One optimal solution uses \(1\to 3\) , \(3\to 1\) and \(2\to 6\) , \(6\to 5\) , \(5\to 4\) , \(4\to 2\) . The cut around \(S=\{1,3\}\) has capacity \(0\) . Add \(x(\delta^+(\{1,3\}))\ge 1\) .
Round 4. The tour \(1\to 3\to 6\to 5\to 4\to 2\to 1\) , of length \(1+10+2+1+9+1=24\) , is optimal for the relaxation; every cut has capacity at least \(1\) , so no subtour constraint is violated, and the solution is integral. It is an optimal tour.
Three of the fifty subtour constraints were generated. After the first, the bound already equalled the length of the best tour; the other two were needed only to make the relaxation’s solution itself a tour. The exact solutions met in rounds 2 and 3 depend on which optimal vertex the linear programming code returns, but the bounds do not.
The same idea reaches far beyond tours. A theorem of Grötschel, Lovász, and Schrijver states, roughly, that one can optimize a linear function over a polyhedron in polynomial time if and only if one can solve its separation problem in polynomial time. A formulation therefore does not have to be small to be tractable; it has to have a separation routine.
8.6 How good can a cut be?
Not all valid inequalities are equally useful. The strongest are those that hold with equality on a face of the convex hull of full dimension minus one; they are called facet-defining, and an ideal formulation consists of exactly such inequalities. In Example 8.1 both rounded inequalities were facet-defining for the cargo hull; in Example 8.2 the first Gomory cut was not, and touched the hull nowhere.
Rounding can be iterated. Let \(P_0\) be a formulation, and let \(P_1\) be obtained by adding to it every inequality that Proposition 8.2 can produce from \(P_0\) ; then form \(P_2\) from \(P_1\) in the same way, and so on. A theorem of Chvátal says that for a bounded rational formulation this sequence reaches the convex hull of the integer points after finitely many steps. The number of steps needed is the Chvátal rank of the formulation. The cargo formulation has rank one, by Example 8.1. For hard problems the rank can grow with the size of the instance, which is one way of expressing that no simple description of the hull exists.
Cutting planes and branching are complementary. Cuts change the formulation and so improve every node at once, but each cut helps less than the one before. Branching always makes progress in the sense of Theorem 7.3, but multiplies the number of subproblems. Branch-and-cut uses cuts while they are effective and branches when they stall; with separation routines for problem-specific families it is the method by which travelling salesman instances with tens of thousands of cities have been solved to proven optimality. Both ingredients are, at bottom, ways of producing the pair of matching bounds demanded by Proposition 1.3.
Exercises
-
For the integer program with constraints \(2x_1+x_2\le 7\) , \(x_1+2x_2\le 7\) , \(x\ge 0\) integer, derive the Chvátal–Gomory inequality with multipliers \(\mu=(\tfrac13,\tfrac13)\) , show that it separates the relaxation optimum for the objective \(4x_1+3x_2\) , and solve the relaxation with the cut added.
Solution
Multiply each constraint by \(\tfrac13\) and add: \(\tfrac13(2x_1+x_2)+\tfrac13(x_1+2x_2)\le\tfrac73+\tfrac73\) , that is,
\[ x_1+x_2\le\tfrac{14}{3}. \]The coefficients are integers, so flooring them changes nothing, and since \(x_1+x_2\) is an integer at integer points the right side can be rounded down: \(x_1+x_2\le 4\) . This is valid by Proposition 8.2.
The relaxation optimum for \(4x_1+3x_2\) is \((7/3,7/3)\) , found in Exercise 7.1, where \(x_1+x_2=14/3>4\) . So the inequality separates it.
With the cut added, the relaxation maximizes \(4x_1+3x_2\) subject to \(2x_1+x_2\le 7\) , \(x_1+2x_2\le 7\) , \(x_1+x_2\le 4\) , \(x\ge 0\) . On the line \(x_1+x_2=4\) the objective is \(12+x_1\) , so \(x_1\) should be as large as the other constraints allow: \(2x_1+(4-x_1)\le 7\) gives \(x_1\le 3\) . The solution is \((3,1)\) with value \(15\) . It satisfies \(x_1+2x_2=5\le 7\) , and it is integral, so by Proposition 1.3 it is optimal for the integer program: \(z^\star=15\) , in agreement with the five-node tree of Exercise 7.1. One cut replaced the tree.
-
Derive by Proposition 8.2 a valid inequality for \(\{x\in\mathbb Z^2:5x_1+3x_2\le 17,\ x\ge 0\}\) from the multiplier \(\tfrac15\) and another from the multiplier \(\tfrac13\) , and check both against the list of feasible integer points with \(x_2=0\) and with \(x_1=0\) .
Solution
Multiplier \(\tfrac15\) . The scaled constraint is \(x_1+\tfrac35x_2\le\tfrac{17}5\) . Flooring the coefficients gives \(x_1+0\cdot x_2\le\tfrac{17}5\) , valid because \(x_2\ge 0\) , and rounding the right side gives \(x_1\le 3\) .
Multiplier \(\tfrac13\) . The scaled constraint is \(\tfrac53x_1+x_2\le\tfrac{17}3\) . Flooring gives \(x_1+x_2\le\tfrac{17}3\) , and rounding gives \(x_1+x_2\le 5\) .
Check. With \(x_2=0\) the original constraint is \(5x_1\le 17\) , so the feasible points are \(x_1=0,1,2,3\) : all satisfy \(x_1\le 3\) , with equality at \((3,0)\) , and all satisfy \(x_1+x_2\le 5\) . With \(x_1=0\) it is \(3x_2\le 17\) , so \(x_2=0,\dots,5\) : all satisfy \(x_1+x_2\le 5\) , with equality at \((0,5)\) . Both inequalities are attained, so neither right side could be lowered further. The first cuts off the fractional vertex \((17/5,0)\) of the relaxation and the second cuts off \((0,17/3)\) . A point such as \((1,4)\) , with \(5+12=17\) , is feasible and lies on \(x_1+x_2=5\) , so the second inequality touches the integer hull at two points and is one of its edges.
-
The final tableau of the relaxation of “maximize \(4x_1+3x_2\) subject to \(2x_1+x_2+s_1=7\) , \(x_1+2x_2+s_2=7\) ” has the rows \(x_1+\tfrac23s_1-\tfrac13s_2=\tfrac73\) and \(x_2-\tfrac13s_1+\tfrac23s_2=\tfrac73\) . Derive the Gomory cut from the first row, express it in the variables \(x_1,x_2\) , and verify that it removes \((\tfrac73,\tfrac73)\) and no feasible integer point.
Solution
In the first row the coefficient of \(s_1\) is \(\tfrac23\) , with fractional part \(\tfrac23\) . The coefficient of \(s_2\) is \(-\tfrac13\) , with floor \(-1\) and fractional part \(-\tfrac13+1=\tfrac23\) . The right side \(\tfrac73\) has fractional part \(\tfrac13\) . By Proposition 8.3 the cut is
\[ \tfrac23s_1+\tfrac23s_2\ge\tfrac13,\qquad\text{that is,}\qquad s_1+s_2\ge\tfrac12 . \]Substituting \(s_1=7-2x_1-x_2\) and \(s_2=7-x_1-2x_2\) gives \(14-3x_1-3x_2\ge\tfrac12\) , or \(x_1+x_2\le\tfrac92\) .
At \((\tfrac73,\tfrac73)\) the left side is \(\tfrac{14}3\approx 4.67>4.5\) , so the point is removed; equivalently both slacks are zero there and \(0\ge\tfrac12\) fails. For a feasible integer point, \(s_1+s_2=14-3(x_1+x_2)\) is an integer, and it is at least \(2\) because the largest value of \(x_1+x_2\) over feasible integer points is \(4\) , attained at \((3,1)\) , \((2,2)\) , and \((1,3)\) . So every feasible integer point satisfies the cut with room to spare.
The Gomory cut \(x_1+x_2\le 4.5\) is weaker than the rounded inequality \(x_1+x_2\le 4\) of Exercise 8.1. A second Gomory cut, from the next tableau, produces \(x_1+x_2\le 4\) , exactly as in Example 8.2.
-
Prove that the slack variable \(g\) of a Gomory cut takes an integer value at every feasible integer solution, using the tableau row from which the cut was derived.
Solution
The cut was derived from the row \(x_{B_i}+\sum_{j\in N}\bar a_{ij}x_j=\bar b_i\) and reads \(\sum_{j\in N}f_{ij}x_j-g=f_{i0}\) with \(g\ge 0\) . Solve for \(g\) and substitute \(f_{ij}=\bar a_{ij}-\lfloor\bar a_{ij}\rfloor\) and \(f_{i0}=\bar b_i-\lfloor\bar b_i\rfloor\) :
\[ g=\sum_{j\in N}\bar a_{ij}x_j-\sum_{j\in N}\lfloor\bar a_{ij}\rfloor x_j-\bar b_i+\lfloor\bar b_i\rfloor . \]By the tableau row, \(\sum_{j\in N}\bar a_{ij}x_j-\bar b_i=-x_{B_i}\) . Hence
\[ g=\lfloor\bar b_i\rfloor-x_{B_i}-\sum_{j\in N}\lfloor\bar a_{ij}\rfloor x_j . \]At a feasible integer solution every variable on the right is an integer and every coefficient is an integer, so \(g\) is an integer. It is nonnegative because the cut is valid.
This is what allows the method to continue: after the cut is added, the enlarged system again has only nonnegative integer variables, so Proposition 8.3 applies to its tableau rows, including rows in which \(g\) appears. In Example 8.2 the second cut was generated from a row containing \(g_1\) , and the formula above gives \(g_1=1-x_1+s_1\) there, an integer.
-
For the knapsack constraint \(5x_1+6x_2+7x_3+9x_4\le 15\) with binary variables, list all minimal covers and their cover inequalities, and for the cover \(\{1,2,3\}\) write the extended cover inequality.
Solution
The weights are \(5,6,7,9\) and the capacity is \(15\) .
Pairs. The sums are \(11\) , \(12\) , \(14\) , \(13\) , \(15\) , \(16\) . Only \(\{3,4\}\) , with \(7+9=16\) , exceeds \(15\) . It is minimal, since single items are not covers.
Triples. \(\{1,2,3\}\) has weight \(18\) ; removing any item leaves \(13\) , \(12\) , or \(11\) , so it is minimal. \(\{1,2,4\}\) has weight \(20\) ; removing an item leaves \(15\) , \(14\) , or \(11\) , none exceeding \(15\) , so it is minimal. \(\{1,3,4\}\) and \(\{2,3,4\}\) contain the cover \(\{3,4\}\) and are not minimal. The set of all four items is not minimal either.
The minimal covers and their inequalities are
\[ x_3+x_4\le 1,\qquad x_1+x_2+x_3\le 2,\qquad x_1+x_2+x_4\le 2 . \]For \(C=\{1,2,3\}\) the largest weight in \(C\) is \(7\) , and item 4 weighs \(9\ge 7\) , so \(E(C)=\{1,2,3,4\}\) and the extended cover inequality is \(x_1+x_2+x_3+x_4\le 2\) . It is valid because the three lightest items already weigh \(18>15\) , so no three items fit. It implies both triple inequalities above and is strictly stronger than either.
-
The point \(\bar x=(1,\tfrac12,\tfrac12,\tfrac13)\) satisfies the constraint of Exercise 5. Use Proposition 8.7 to find a violated cover inequality or show that none exists, and then test the extended cover inequality of Exercise 5 at \(\bar x\) .
Solution
The values \(1-\bar x_j\) are \(0\) , \(\tfrac12\) , \(\tfrac12\) , \(\tfrac23\) . By Proposition 8.7 a cover inequality is violated exactly when some cover \(C\) has \(\sum_{j\in C}(1-\bar x_j)<1\) . It is enough to test minimal covers, since enlarging a cover only adds nonnegative terms.
For \(\{3,4\}\) the sum is \(\tfrac12+\tfrac23=\tfrac76\) . For \(\{1,2,3\}\) it is \(0+\tfrac12+\tfrac12=1\) . For \(\{1,2,4\}\) it is \(0+\tfrac12+\tfrac23=\tfrac76\) . None is less than \(1\) , so the separation problem has optimal value \(1\) and no cover inequality is violated. The inequality \(x_1+x_2+x_3\le 2\) holds with equality at \(\bar x\) .
The extended cover inequality \(x_1+x_2+x_3+x_4\le 2\) is another matter: at \(\bar x\) its left side is \(1+\tfrac12+\tfrac12+\tfrac13=\tfrac73>2\) . It is violated. So \(\bar x\) , which has weight \(5+3+3.5+3=14.5\) and satisfies the knapsack constraint and every cover inequality, is nevertheless cut off by a stronger valid inequality. Separation over one family of cuts finding nothing does not mean the point is in the integer hull.
-
Explain what is wrong with this derivation for the cargo problem and exhibit a feasible integer point that the result cuts off: “From \(3x_1+2x_2\le 11\) , divide by \(3\) and round down to get \(x_1\le 3\) ; from \(x_1+2x_2\le 8\) , divide by \(2\) and round down to get \(x_2\le 4\) ; adding gives \(x_1+x_2\le 7\) , and dividing by \(2\) and rounding the right side down gives \(x_1+x_2\le 3\) .”
Solution
The first two steps are legitimate applications of Proposition 8.2. From \(3x_1+2x_2\le 11\) with multiplier \(\tfrac13\) : \(x_1+\tfrac23x_2\le\tfrac{11}3\) , floor the coefficient of \(x_2\) to \(0\) , round the right side, \(x_1\le 3\) . From \(x_1+2x_2\le 8\) with multiplier \(\tfrac12\) : \(\tfrac12x_1+x_2\le 4\) , floor the coefficient of \(x_1\) to \(0\) , \(x_2\le 4\) . Adding gives the valid inequality \(x_1+x_2\le 7\) .
The error is in the last step. Dividing \(x_1+x_2\le 7\) by \(2\) gives \(\tfrac12x_1+\tfrac12x_2\le\tfrac72\) . Proposition 8.2 allows the right side to be rounded only after the coefficients on the left have been floored, because the rounding relies on the left side being an integer. Flooring the coefficients \(\tfrac12\) gives \(0\le 3\) , a true and useless statement. The derivation instead kept the left side \(x_1+x_2\) of the undivided inequality and paired it with the rounded right side of the divided one.
The result \(x_1+x_2\le 3\) is invalid: the feasible plans \((3,1)\) , \((2,2)\) , \((1,3)\) , and \((0,4)\) all have \(x_1+x_2=4\) . In particular it cuts off the optimal plan \((3,1)\) . A solver given this “cut” would report the best plan with at most three pallets, which is \((3,0)\) with profit \(15\) , in place of the true optimum \(19\) . An invalid cut does not announce itself; the answer is simply wrong.
-
Show that for the five-cycle the odd-set inequality \(x(E)\le 2\) on the set of all five nodes is a Chvátal–Gomory inequality of the node constraints, and that it separates the vertex found in Exercise 6.14.
Hint
Each edge of the five-cycle appears in the node constraints of its two endpoints. Add the five node constraints with multipliers \(\tfrac12\) : every edge receives coefficient \(1\) and the right side is \(\tfrac52\) , which rounds down to \(2\) . At the point with every \(x_e=\tfrac12\) the left side is \(\tfrac52>2\) .
-
Prove that if \(C\) is a cover that is not minimal, its cover inequality is implied by the cover inequality of a minimal cover contained in \(C\) together with the bounds \(x_j\le 1\) .
Solution
Let \(C\) be a cover that is not minimal. Remove items from \(C\) one at a time, keeping the set a cover, until no further item can be removed; this ends with a minimal cover \(C'\subseteq C\) , with \(k=\lvert C\rvert-\lvert C'\rvert\ge 1\) items removed.
Suppose \(x\) satisfies the cover inequality of \(C'\) and the bounds \(x_j\le 1\) . Then
\[ \sum_{j\in C}x_j=\sum_{j\in C'}x_j+\sum_{j\in C\setminus C'}x_j\le(\lvert C'\rvert-1)+k=\lvert C\rvert-1 , \]using the cover inequality of \(C'\) for the first sum and \(x_j\le 1\) for each of the \(k\) items in the second. That is the cover inequality of \(C\) .
So the inequality of \(C\) is a consequence of the inequality of \(C'\) and the bounds, for all points of the relaxation and not only for integer points. Adding it to a formulation that already contains the minimal cover inequalities changes nothing. This is why separation routines look only for minimal covers, and why Exercise 8.6 tested only those.
-
A fractional solution on five cities has \(\bar x_{12}=\bar x_{21}=1\) and \(\bar x_{34}=\bar x_{45}=\bar x_{53}=1\) , with all other arcs zero. Verify the degree equations, find a violated subtour constraint by inspecting cuts, and state the constraint to be added.
Answer
Each city has exactly one arc out and one arc in with value \(1\) , so the degree equations hold. The solution consists of the subtours \(1,2,1\) and \(3,4,5,3\) . For \(S=\{1,2\}\) no arc with positive value leaves \(S\) , so \(\bar x(\delta^+(S))=0<1\) . Add \(x(\delta^+(\{1,2\}))\ge 1\) , that is, \(x_{13}+x_{14}+x_{15}+x_{23}+x_{24}+x_{25}\ge 1\) .
-
A solution on four cities has \(\bar x_{12}=\bar x_{23}=\bar x_{34}=\bar x_{41}=\tfrac12\) and \(\bar x_{21}=\bar x_{32}=\bar x_{43}=\bar x_{14}=\tfrac12\) . Show that it satisfies the degree equations and every subtour constraint, although it is not a tour, and explain why no valid inequality whatever can separate it from the set of tours.
Hint
Each city has two outgoing arcs of value \(\tfrac12\) and two incoming ones. For a two-city set such as \(\{1,2\}\) the leaving arcs are \(2\to 3\) and \(1\to 4\) , total \(1\) ; for \(\{1,3\}\) all four outgoing arcs leave, total \(2\) . The point is the midpoint of the tour \(1,2,3,4\) and its reversal. A valid inequality holds at both tours, hence at their average, so nothing valid can cut the point off: it lies in the convex hull of tours.
-
In Example 8.3 the first cut alone lowered the bound from \(52.625\) to about \(52.57\) . Explain, by reference to the branch-and-bound tree of Example 7.2, why this is the same number as the bound of the node \(x_3=0\) , and what the cut \(x_1+x_2+x_3\le 2\) and the branch \(x_3=0\) have in common at the relaxation’s solution.
Hint
With the cut, a solution with \(x_1=x_2=1\) must have \(x_3=0\) ; the relaxation prefers to keep items 1 and 2, the best two ratios, and so behaves exactly as if \(x_3\) were fixed at zero. Both the cut and the branch exclude the fractional value \(x_3=\tfrac38\) while leaving \((1,1,0,\cdot)\) available, and both give the bound \(47+13\cdot\tfrac37\) .
-
Apply the cutting-plane method with cover inequalities to the knapsack problem with profits \((16,15,12,5)\) , weights \((4,5,6,3)\) , and capacity \(10\) of Exercise 7.4: find the relaxation’s solution, a violated cover, and the new relaxation solution, continuing until the solution is integral or no cover inequality is violated.
Solution
The items are in ratio order. The relaxation’s solution is \((1,1,\tfrac16,0)\) with value \(16+15+2=33\) .
Round 1. The values \(1-\bar x_j\) are \(0,0,\tfrac56,1\) , and a cover needs weight at least \(11\) . The set \(\{2,3\}\) weighs \(5+6=11\) and costs \(\tfrac56<1\) : violated, since \(\bar x_2+\bar x_3=\tfrac76>1\) . Add \(x_2+x_3\le 1\) . The new solution is \((1,1,0,\tfrac13)\) with value \(31+\tfrac53\approx 32.67\) .
Round 2. Now \(1-\bar x_j\) is \(0,0,1,\tfrac23\) . The set \(\{1,2,4\}\) weighs \(12\) and costs \(\tfrac23<1\) : violated. Add \(x_1+x_2+x_4\le 2\) . The new solution is \((1,\tfrac34,\tfrac14,\tfrac14)\) , with weight \(4+3.75+1.5+0.75=10\) and value \(16+11.25+3+1.25=31.5\) ; both cuts hold with equality.
Round 3. Now \(1-\bar x_j\) is \(0,\tfrac14,\tfrac34,\tfrac34\) . The minimal covers are \(\{2,3\}\) , \(\{1,2,4\}\) , and \(\{1,3,4\}\) , with costs \(1\) , \(1\) , and \(\tfrac32\) . None is below \(1\) , so no cover inequality is violated and the method stops with a fractional solution.
The bound has nevertheless done its work: the objective is integral, so \(z^\star\le\lfloor 31.5\rfloor=31\) , and items 1 and 2 give a feasible solution worth \(31\) . The optimum is \(31\) . Cover cuts alone did not make the relaxation integral here; cover cuts together with rounding the bound proved optimality, where the tree of Exercise 7.4 needed seven nodes.
-
Give a valid inequality for the cargo set that is not facet-defining and one that is, and for each say at how many feasible integer points it holds with equality.
Answer
Not facet-defining: \(x_1+x_2\le 4.5\) , valid and attained with equality at no feasible integer point; or \(x_1+2x_2\le 8\) , attained only at \((0,4)\) . Facet-defining: \(x_1+x_2\le 4\) , attained at the four points \((3,1)\) , \((2,2)\) , \((1,3)\) , \((0,4)\) ; and \(x_1\le 3\) , attained at \((3,0)\) and \((3,1)\) . In the plane a facet is an edge of the hull, so it must contain at least two of the integer points.
-
Using Proposition 8.8 and Theorem 3.8, give a polynomial bound on the number of elementary steps needed to decide whether a point \(\bar x\) on \(n\) cities violates some subtour constraint.
Hint
The complete directed graph has \(m=n(n-1)\) arcs. Proposition 8.8 needs \(n-1\) maximum-flow computations, each costing \(O(nm^2)=O(n^5)\) steps by Theorem 3.8. The total is \(O(n^6)\) , a polynomial, although the family has about \(2^n\) members.
-
In Example 5.3 with \(M=40\) the relaxation’s solution is \(x=0.75\) , \(y=30\) , \(w=0\) . Show that \(y\le 30x\) is a valid inequality for the mixed-integer feasible set, that it separates this point, and that adding it raises the bound to the optimal value; then say in what sense tightening a constant is a cutting plane.
Solution
Validity. The feasible set consists of \((x,y,w)\) with \(x\in\{0,1\}\) , \(y+w=30\) , \(y\le 40x\) , \(y,w\ge 0\) . If \(x=0\) then \(y\le 0\) , so \(y=0=30x\) . If \(x=1\) then \(y=30-w\le 30=30x\) , because \(w\ge 0\) . So \(y\le 30x\) holds at every feasible point.
Separation. At the relaxation’s solution, \(y=30\) and \(30x=22.5\) , so \(30>22.5\) and the inequality is violated.
Effect. With \(y\le 30x\) added, a unit made in the relaxation costs at least \(2+100/30\approx 5.33\) , more than the purchase price \(5\) , so the relaxation buys everything: \(x=0\) , \(y=0\) , \(w=30\) , with cost \(150\) . That is the integer optimum, as Example 5.3 found for \(M=30\) .
Interpretation. Replacing the constant \(40\) by \(30\) is the same as adding the inequality \(y\le 30x\) , which is valid for the mixed-integer set and violated by the fractional solution: by Definition 8.1 it is a cut. It is not a Chvátal–Gomory cut, since \(y\) is continuous and the rounding argument does not apply; its validity came from combining the equation \(y+w=30\) with the two possible values of \(x\) . Solvers perform this kind of bound tightening automatically before the search starts.
-
For the family of Example 7.4, compare the number of branch-and-bound nodes at \(n=15\) with the number of cutting-plane rounds needed, and state which proposition of this chapter produces the cut.
Answer
At \(n=15\) branch-and-bound evaluated \(25739\) nodes. The cutting-plane method needs one round: Proposition 8.2 with multiplier \(\tfrac12\) gives \(\sum_jx_j\le 7\) , after which the relaxation has the integral optimal solution with seven variables equal to one and value \(14=z^\star\) .
-
Explain why failing to find a violated cut with a heuristic separation routine cannot make a branch-and-cut algorithm return a wrong answer, whereas adding an invalid inequality can, referring to Proposition 7.2.
Hint
Proposition 7.2 remains true for any relaxation of a node: if no cut is found, the node keeps a weaker but still valid bound, and the node is divided instead. An invalid inequality makes a node’s “relaxation” exclude feasible points, so a node may be declared infeasible or pruned by bound while containing the optimum, and Proposition 7.2 no longer applies.