The lines the optimum lies under

What a constraint is worth changed one right-hand side of a linear program and watched the optimum respond, and found it piecewise linear, with each piece’s slope equal to a dual variable. When one of the two numbers is missing mapped out what happens at the edges of that — where one side of the theorem stops having an optimum at all. Put together, they suggest looking at the optimum as a function of the whole right-hand side, and asking what the dual is in relation to that function.

The answer is a single picture. Every solution of the dual is a straight line lying above the optimum, and the optimum is the lowest of those lines. The dual is not a second program that happens to reach the same number; it is the collection of planks that the optimum rests against, one of which touches it at every point.

One line per dual solution #

The argument is weak duality read with the right-hand side left free. The program is to maximise $c^\top x$ subject to $Ax \le b$ and $x \ge 0$; write $v(b)$ for its optimum at resources $b$. A dual solution is any $y \ge 0$ with $A^\top y \ge c$, and that condition does not mention $b$ at all. So a single dual solution works for every right-hand side at once, and for every $b$ weak duality gives

$$v(b) \;\le\; b^\top y.$$

As a function of $b$, the right side is linear. So each dual solution is a plank — a straight line in the figure, a plane when both right-hand sides vary — lying on or above the optimum everywhere. Strong duality then says that at every $b$ some plank touches: the lowest value of $b^\top y$ over dual solutions equals $v(b)$. And since a linear function is lowest at a vertex, only the finitely many vertices of the dual region are needed:

$$v(b) \;=\; \min_{y \text{ a dual vertex}} \; b^\top y.$$

The figure checks that identity at eighty-one values of $b_1$, exactly. The dual region here has three vertices, so there are three lines; the orange curve runs along the lowest of them, and its two corners, at $b_1 = 5$ and $b_1 = 30$, are where the lowest line changes. On the first stretch the lowest line is $y = (2, 0)$, which says that the second constraint is worth nothing there; on the last it is $y = (0, 3)$, which says the first constraint has stopped mattering; in between both have prices, $\tfrac45$ and $\tfrac35$.

The formula has two consequences that were visible in the earlier sweep and are explained here. The optimum is concave, because the lowest of a family of lines always bends downwards — and concavity has a direct meaning: a mixture of two resource bundles is worth at least the same mixture of their values, since mixing the two optimal plans is a feasible plan for the mixed bundle. And the slopes are the prices, because along each piece the optimum is one of the lines, and a line’s slope in $b_1$ is its $y_1$.

The wedges on which a basis survives #

With both right-hand sides free, the planks are planes over the $(b_1, b_2)$ square and the optimum is a roof made of the lowest of them. Colour each point of the square by which plane is lowest there.

The regions are wedges from the origin, and that is forced. Doubling every resource doubles every plank’s value, so it cannot change which plank is lowest; the whole picture is unchanged by scaling, and the boundaries must be rays. Economically it says that the pattern of an optimal plan — which constraints are tight, which products are made — depends on the proportions of the resources and not on their scale. Double the supply of everything and the same things are made, twice over.

The one-variable sweep in the first figure is a horizontal line across this square, at $b_2 = 10$, and its two corners are where that line crosses the two boundary rays. Every corner in any one-variable sweep is a crossing of this kind. And the prices of a price for every person and task, which were found for one particular assignment problem, are the planks for that problem: each is valid across a whole wedge of possible supplies, and changes only when the proportions cross a boundary.

Diminishing returns, from the shape alone #

The roof’s concavity has a reading that economists state as a law and that here is a theorem. Fix every resource but one and add that one a unit at a time. The optimum rises, but by less and less: the slope of each piece is a price, the pieces bend downward, and so each extra unit of the resource is worth no more than the one before. In the first figure the first resource is worth $2$ a unit up to $b_1 = 5$, then $\tfrac45$ a unit up to $30$, then nothing at all.

Nothing about the particular program forced that; the lowest of any family of lines bends the same way. It is a line under every point turned upside down — a concave function is exactly one lying below a line at every point, touching it there — and the planks are those lines, supplied by the dual. Diminishing returns in a linear model are not an assumption about the world; they are the shape of a minimum of linear functions. A model in which a resource becomes more valuable as it becomes more plentiful cannot be a linear program, and the whole-number staircase, which does have stretches where a unit is worth more than the unit before, is the first place that kind of increasing return appears.

At a corner, a fan of prices #

On a wedge the price of each resource is one number. On the boundary between two wedges it is not.

At $b_1 = 5$ two dual vertices tie, and so does every point on the segment between them: all of them are dual solutions, all give the same value at the corner, and all their lines lie on or above the optimum everywhere else. The dual optimum is no longer a point but a segment, and the lines through the corner form a fan.

What that means for the price is concrete. Adding a unit of the first resource at $b_1 = 5$ raises the optimum at the rate of the right-hand piece, $\tfrac45$. Removing a unit lowers it at the rate of the left-hand piece, $2$. The resource is worth more to lose than to gain, and any number in between is a defensible price — which is why a supplier and a buyer negotiating at a corner have a range to argue over rather than a single answer. The segment of dual solutions is what analysts call the subdifferential of the optimum, and its appearance at a corner is exactly what the degenerate vertices of what a constraint is worth predicted: a corner of the roof is a degenerate vertex of the program.

The same fan is the definition of a supporting line in the function seen from its tangents, where a convex function is recovered from all its tangent lines. Here the optimum is concave rather than convex, the tangents lie above rather than below, and the dual is the Legendre-style description of the optimum by its planks. At a smooth point there is one plank; at a corner there is a fan.

Whole numbers, and a gap no line can see #

Now insist that the variables be whole numbers. The feasible region is the same polygon, but only its lattice points are allowed.

The fractional optimum sits at a corner with coordinates $\tfrac{14}5$ and $\tfrac95$, value $\tfrac{78}{5} = 15.6$. The best whole-number point is $(2, 2)$ with value $14$. Any dual solution still gives a valid bound — weak duality never used fractions — but it bounds the fractional corner as well, so the best it can do is $15.6$. The dual can certify that 14 is within 1.6 of optimal; it cannot certify that 14 is optimal.

Swept across a range of resources, the difference becomes a picture of the whole problem.

The whole-number optimum is a staircase: it changes only when enough resource has accumulated to allow one more whole unit of something, and then it jumps. A staircase is not concave, so it cannot be the lowest of any family of lines, and every family of lines lying above it lies above its smallest concave cover. The gap between the staircase and the orange roof is exactly the part of the whole-number problem that linear duality cannot price. Where the steps touch the roof, a dual solution certifies the whole-number answer; everywhere else the certificate is only approximate.

This is the same gap that where the corners stop being whole found in matchings when an odd cycle appears. There the question was whether the polygon’s corners are lattice points; here it is what the dual can see when they are not. Both say the same thing from two sides: when the corners of the feasible region are whole — as they are for assignments and network flows — the staircase coincides with the roof at every whole-number resource level, and duality is exact. When they are not, it is a bound.

The knapsack, where the gap has a shape #

The simplest whole-number problem is a knapsack: a handful of items, each with a weight and a value, and a limit on the total weight. Every subset of items is a point, and the whole problem is visible at once.

The best packing within a limit is the highest dot to the left of it — the green staircase. The dual here relaxes only the weight limit: charge a price $\lambda$ per unit of weight, let the packer choose any subset to maximise value minus charge, and add back $\lambda$ times the limit. Each price gives a line, and the best price gives the lowest line above all the dots, read at the limit. Those lines together trace the orange curve, which is the upper hull of the sixteen dots.

At a limit of $10$ the hull passes at $16$ while the best packing is $14$. The hull’s value there is a mixture: the packing of items 1 and 3 (weight 8, value 13) and a fraction of item 2 on top, which is exactly what a greedy packer would do if items could be cut — take the best value per unit weight first, and cut the next item to fill the space. The Lagrangian dual of the knapsack is the fractional knapsack, and the gap of 2 is how much it costs that items cannot be cut. Where the dots lie on their own upper hull, the gap closes; where the hull has to bridge between two dots, it opens, and its size is exactly how far the dots fall short of lying on a concave curve.

What replaces the lines #

The gap is not a failure of duality in principle, only of linear duality. If the planks are allowed to be something other than straight lines, a dual that closes the gap exists.

The right class turns out to be functions built from linear ones by rounding down. A plank like $b_1 y_1 + b_2 y_2$ becomes, after rounding, something like $\lfloor \tfrac12 b_1 \rfloor + \lfloor \tfrac13 (b_1 + b_2) \rfloor$ — a staircase itself, able to follow the staircase optimum down into its steps. The theory, developed by Ralph Gomory, Robert Jeroslow and others in the 1960s and 1970s, says that for whole-number programs with whole-number data a dual made of such rounded functions always meets the optimum exactly: the whole-number optimum is itself one of them, and strong duality is restored.

The program of the lattice-point figure shows how the rounding works. Take the two constraints with weights $\tfrac15$ and $\tfrac25$ and add: $x_1 + 2x_2 \le 6.4$. Every whole-number point satisfies it, and for whole numbers the left side is whole, so the right side can be rounded down: $x_1 + 2x_2 \le 6$. That new constraint cuts off the fractional corner $(\tfrac{14}5, \tfrac95)$, where the left side is $6.4$, and leaves every lattice point. The new fractional optimum is $15$, at $(3, \tfrac32)$. Round once more — a quarter of each of the first and third constraints gives $x_1 + x_2 \le 4.5$, rounded to $4$ — and the fractional optimum drops to $14$, at $(2, 2)$: the whole-number answer, certified. Two roundings closed a gap no straight plank could. These rounded combinations are Chvátal–Gomory cuts, and the theorem behind them, from Václav Chvátal in 1973, is that finitely many rounds always reach the whole-number optimum.

The price is that the dual is no longer a linear program. Its variables are functions rather than numbers, finding the right rounded plank is as hard as the original problem, and the elegance of a finite list of vertices is gone. That is the general shape of the difference between linear and whole-number optimisation: the same theorem holds, and the certificate it promises can be as hard to find as the answer.

What the pictures cannot show #

More than two resources. The roof is drawn over one right-hand side and then over two. With many constraints it is a concave surface over a space of many dimensions, made of as many planar pieces as the dual region has vertices — potentially an enormous number — and the wedges become cones with many faces. The picture of the lowest plank survives; nothing here can draw it.

How the gap behaves for large problems. The gaps drawn are small — 1.6, 3.5, 2 — because the problems are tiny. For many whole-number problems the ratio between the fractional and whole-number optima can be bounded, and those bounds are what approximation algorithms rest on; for others it can grow without limit. A two-variable picture cannot show which case a problem is in.

The fractional point’s meaning. The figures mark the fractional optimum $(\tfrac{14}5, \tfrac95)$ as a dot on the polygon, and it is a perfectly good point. What it means — fourteen-fifths of a product, a fraction of an item in a knapsack — is exactly the question the whole-number requirement exists to refuse, and a drawing that shows it cheerfully in the same colours as the whole-number points is making it look more legitimate than it is.

Still open: how far below the roof the shortest tour lies #

The most studied instance of this gap is the travelling salesman problem. For a salesman visiting cities with ordinary distances, there is a standard linear relaxation — the subtour relaxation, from Dantzig, Fulkerson and Johnson’s work of 1954 — whose optimum is a lower bound on the shortest tour, in the same way the orange roof is an upper bound on the staircase. The ratio between the true shortest tour and that bound is the problem’s integrality gap.

It is known to be at most $\tfrac32$, a bound established in 1980 and only very slightly improved since. It is known to be at least $\tfrac43$, from a family of examples. Whether the true worst case is exactly $\tfrac43$ has been conjectured for decades and is open. A proof would say that the linear planks come within a third of the whole-number answer for every possible arrangement of cities; it would also, very likely, give a better way of finding short tours, since every improvement so far in the bound has come with one.

A roof and a staircase #

The optimum of a linear program, as its resources vary, is the lowest of finitely many planks, one for each vertex of the dual. That makes it concave, makes its slopes into prices, divides the resources into wedges on which one plan’s pattern survives, and turns the corners between wedges into fans of equally valid prices.

Require whole numbers and the roof stays up while the optimum falls into a staircase beneath it. Every plank still bounds the staircase, and none can reach into its steps. The dual is exact wherever the region’s corners are whole, and a bound everywhere else — and replacing its straight planks by rounded ones restores the exactness at the cost of everything that made it easy.