Back to the on-screen lesson ·
Tightening a relaxation instead of splitting a problem, and the matrices whose relaxations were never wrong.
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 say what makes an inequality a valid cut and compute the bound a cut leaves, write the node-arc incidence matrix of a small network, recognise which constraint matrices are totally unimodular and which are not, and give the argument that a totally unimodular matrix with an integral right-hand side has only integral vertices.
You can relax, branch and prune. This lesson is about making the relaxation better instead of the tree bigger — and about the problems where the relaxation was never the wrong answer at all.
A cut is an inequality satisfied by every integer-feasible point but not by the current relaxed answer. A matrix is totally unimodular when every square submatrix has determinant $0$, $1$ or $-1$. The integrality gap is the distance between the relaxation's value and the integer optimum, and for a totally unimodular problem it is zero.
Branching makes the tree bigger. The alternative is to make the relaxation smaller.
Cuts. A cut is an inequality that every integer plan satisfies and the current relaxed answer does not. Adding it removes no integer-feasible point, so the integer problem is unchanged, but the relaxation's region shrinks and its bound falls. A cut that removes a lattice point is not a cut but a bug, which is why cuts come from families with proofs attached — Gomory, cover, flow — rather than being invented per problem.
Problems that need neither. If $A$ is totally unimodular and $b$ is integral, every vertex of the feasible region is already integral, so the relaxation's answer is the integer answer. The proof is three lines: a vertex is a basic solution; its basis has determinant $\pm 1$; Cramer's rule then divides integers by $\pm 1$.
Network matrices are the standard example — one $+1$ and one $-1$ per column — and that covers flow, transportation, assignment and shortest paths. Knapsack and covering matrices are not, and that is the line between the easy problems and the hard ones.
Another way: steps
Another way: picture
The relaxed region drawn as a polygon with lattice points inside it. A cut is a straight line that slices off the corner the relaxation answered at, leaving every marked point on the near side. Add enough of them and the polygon shrinks onto the marked points themselves.
Entries of $0$, $1$ and $-1$ are taken as the definition of total unimodularity. They are necessary and nowhere near sufficient — the condition is about every square submatrix. The second error is inventing a cut that looks reasonable and removes a lattice point, which produces a confident wrong answer rather than an error.
Maximise $x$ subject to $2x \le 7$, $x$ a whole number. The relaxation gives $x = 3.5$.
A fractional bound.
Every whole number satisfying $2x \le 7$ satisfies $x \le 3$, so that is a valid cut.
No lattice point is lost.
The new relaxation gives $x = 3$, which is integral. No branching happened at all.
The bound fell to the answer.
Its constraint matrix is the node-arc incidence matrix of a bipartite network, which is totally unimodular.
A network matrix.
With integral supplies and demands, every vertex is integral, so the relaxation returns whole shipments and no branching is needed.
Select every problem whose LP relaxation already returns whole numbers, with no branching needed.
This task has no paper form; do it on a device.
A network has nodes $1$, $2$, $3$ and arcs $a$ from $1$ to $2$, $b$ from $2$ to $3$, and $c$ from $1$ to $3$. Write its node-arc incidence matrix, rows in node order and columns in arc order.
This task has no paper form; do it on a device.
Does the LP relaxation already give a whole-number solution: the constraint matrix of a general set-covering problem?
A relaxation maximising $x$ returns $x = 21/2$. Every integer-feasible plan satisfies $x \le 10$, so that inequality is added as a cut. What is the new relaxation's optimum?
Answer:
A relaxation maximising $x$ returns $x = 19/2$, and the cut $x \le 9$ is then added. Fill in the bound before and after.
| The bound | |
|---|---|
| Before the cut | |
| After the cut |
Build the proof that if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x : Ax = b,\ x \ge 0\}$ has whole-number coordinates.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A relaxation maximising $x$ returns $x = 11/2$. Every integer-feasible plan satisfies $x \le 5$, so that inequality is added as a cut. What is the new relaxation's optimum?
Answer:
You can use a cut to tighten a relaxation and recognise the problems whose relaxations are already integral. Say in your own words why a cut must never remove a whole-number plan.
7. Your turn: why is a transportation problem with whole supplies and demands easy?, step 2