Back to the on-screen lesson ·
Tightening a relaxation instead of splitting it, what makes an inequality valid, and why cuts go in at the root.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive a simple rounding cut, state the two conditions an inequality must meet to be a cut, and check validity by asking whether every integer solution satisfies it. You will also be able to say what a cut does to the bound and to the integer optimum, read a cut round in a solver log by its signature — the bound falls and the incumbent does not — and explain why cuts are added at the root before branching begins.
From lesson 22: the relaxation's value is a bound, and how far it is from the truth is a property of the formulation. From lesson 23: branch and bound closes that gap by splitting. This lesson is the other way to close it — change the formulation, mid-solve, by adding inequalities that were true all along.
The relaxation's feasible region is a polyhedron containing all the integer points and a lot of fractional territory besides. A cut is an inequality that:
Add it, re-solve, and the bound tightens while the integer optimum is untouched. Condition 1 is the whole of correctness: an inequality failing it is not a cut but a mistake, and it will quietly return a worse answer.
The simplest cut: rounding. If the left-hand side of $a^\top x \le b$ can only take integer values — because every coefficient and variable is an integer — then
$$a^\top x \le \lfloor b \rfloor$$
is valid. It removes every fractional point with $\lfloor b \rfloor < a^\top x \le b$ and no integer point at all. Gomory cuts are a systematic way of producing such rounding arguments from the simplex tableau, and they were the first cuts to be automated.
Why this is worth doing. The best possible formulation would have a relaxation whose every vertex is integral — then the relaxation is the integer problem, and one linear program solves it. That ideal polyhedron is the convex hull of the integer points. Describing it exactly usually needs exponentially many inequalities, so nobody builds it; cutting planes approximate it, adding the few inequalities that matter near the current solution.
Cuts and branching together. Modern solvers do both — branch and cut. Cuts at the root strengthen every node below; branching handles what cuts cannot reach. Neither alone is competitive.
Another way: picture
A polygon with a scatter of integer points inside it, and one fractional corner sticking out beyond them. Draw a straight line that leaves every dot on one side and puts that corner on the other. Shade off the corner. The dots are untouched and the region is smaller — that is a cut.
Another way: steps
To find a cut by hand:
Maximise $x + y$ over $2x + 2y \le 5$, $x, y \ge 0$ integer.
The relaxation gives $x + y = 2.5$, with value $2.5$ — fractional, so branch and bound would split here.
Instead, notice that $2x + 2y$ is even for every integer $x, y$, so it is certainly a whole number, and a whole number at most $5$... is at most $5$. That gains nothing. Divide the constraint by $2$ first: $x + y \le 2.5$, and now the left-hand side is an integer, so
$$x + y \le 2$$
is valid. The fractional point $x + y = 2.5$ violates it, so it is a cut.
Add it and re-solve: the relaxation now gives $2$, which is integral. The problem is finished without any branching at all, by one inequality that was true of every integer solution from the start and simply had not been written down.
Cutting off integer solutions. The failure mode that matters. The model still solves, reports optimal, and is wrong. Validity must be argued, not assumed.
Adding too many. Every cut makes every subsequent relaxation larger and slower. Solvers add cuts in rounds and stop when the bound stops moving, and "more cuts" is not a strategy.
Numerically nasty cuts. Cuts derived from a tableau can have coefficients of wildly different magnitudes, and accumulating them degrades the linear algebra. Solvers filter on this as well as on strength.
Expecting cuts to replace branching. Pure cutting-plane methods converge slowly and are not used alone. The combination is what works.
It looks like one and is handled like one, and the distinction is what keeps the method honest. A constraint changes which solutions are allowed. A cut changes nothing about which solutions are allowed — every integer solution satisfied it already — and only removes fractional territory that was never a real answer. That is why the integer optimum is provably unchanged and why the check in step 4 is the whole of correctness. Anything that fails it is a new constraint, and adding one mid-solve because it tightens the bound is how a search is made to converge quickly on the wrong answer.
The relaxation gives $x = 3.5$ with $0 \le x \le 7$ integer. Propose $x \le 4$.
Does it remove the fractional point? Yes.
Now the validity check: is $x = 5$ an integer solution of the model? If the model allows it, the proposed inequality cuts off a legitimate answer.
The check that decides it.
So $x \le 4$ is not valid here, and adding it would be a modelling error rather than a cut. Contrast the branching child $x \le 3$ in lesson 23: that also removes integer solutions, and it is legitimate because the sibling $x \ge 4$ keeps them. A cut has no sibling, and so must lose nothing on its own.
Branching splits; a cut must lose nothing.
Root relaxation: $140.0$. Then a line reading "Cuts: Gomory 12, Cover 5, MIR 3" and a new root bound of $133.6$.
Twenty inequalities added.
The incumbent has not moved — no new solution was found. Only the bound fell, by $6.4$.
The signature of a cut round.
That $6.4$ is inherited by every node in the tree that follows, so the pruning in step 3 of lesson 23's loop becomes more aggressive everywhere. A few seconds at the root buys minutes or hours below it, which is why the cut phase exists.
Paid once at the root, collected everywhere.
The left-hand side $3(x+y)$ is a multiple of $3$ for every integer $x, y$: it can be $0, 3, 6, 9, \ldots$
What values can the left-hand side take?
The largest multiple of $3$ that is at most $7$ is $6$. So $3x + 3y \le 6$ is satisfied by every integer solution — a valid cut.
And it is a real improvement: dividing through gives $x + y \le 2$, where the original only gave $x + y \le 2.33$. The fractional point $x + y = 2.33$ is removed and no integer point is. Note the argument used more than rounding — it used the multiple of 3 structure, which is where the better families of cuts all come from.
For integer $x, y \ge 0$ the constraint is $2x + 2y \le 11 . 5$. What can the right-hand side be tightened to?
Answer:
The relaxation returns $x = 6.5$ for an integer variable with $0 \le x \le 12$. Is $x \le 6$ a valid cut?
| Is removed by the proposed inequality | Must remain feasible | Incorrectly removes an integer solution | Preserve every integer-feasible solution | |
|---|---|---|---|---|
| $x=6.5$, the fractional relaxation solution | ||||
| $x=7$, a valid integer solution | ||||
| Proposed inequality $x \le 6$ | ||||
| Requirement for a valid cut |
A valid cut is added to a maximisation's relaxation. What happens to the bound and to the integer optimum?
Before a round of cuts the bound is $48$; after, it is $43$, and the incumbent is $41$. By how much did the cuts close the gap?
Answer:
For integer $x, y \ge 0$ the constraint is $2x + 2y \le 13 . 5$. What can the right-hand side be tightened to?
Answer:
A solver adds cuts at the root and only then starts branching. Why that order?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The relaxation returns $x = 4.5$ for an integer variable with $0 \le x \le 8$. Is $x \le 4$ a valid cut?
| Is removed by the proposed inequality | Must remain feasible | Incorrectly removes an integer solution | Preserve every integer-feasible solution | |
|---|---|---|---|---|
| $x=4.5$, the fractional relaxation solution | ||||
| $x=5$, a valid integer solution | ||||
| Proposed inequality $x \le 4$ | ||||
| Requirement for a valid cut |
You can derive and validate a cut, say what it does to the bound, and explain branch and cut. Next: the discrete problems that turn out to be easy after all.
9. Your turn: is $3x + 3y \le 7$ tightenable, for integer $x, y \ge 0$?, step 3