Where the corners stop being whole

Four rungs of this ladder rest on a single sentence: the corners of the relaxed assignment problem are whole assignments. It makes an apparently combinatorial search into a linear program, it makes the duality exact, it makes the certificate tight, and it makes the lottery exist. Four different-looking achievements, and one property underneath all of them.

A property doing that much work is worth testing to destruction, and the test is short. It is also worth doing deliberately rather than waiting to meet it: a property that has never been seen to fail is one whose scope nobody knows. Take the same problem on a graph that is not bipartite — people who can be paired with each other rather than with tasks — and everything collapses.

The half on every edge #

Three people, each willing to be paired with each of the others, and the requirement that nobody is in two pairs.

A whole matching uses one edge and leaves somebody out; there is no way to pair three people, since pairs come in twos and three is odd. So the best whole answer is worth one.

The relaxation allows fractions. Put a half on every edge: each vertex carries a half twice, totalling one, so the constraints hold. The value is one and a half.

And that point is a corner. It is not the midpoint of two other feasible points, because moving along any edge of the triangle forces a compensating move that breaks a vertex constraint — the perturbation argument that works in the bipartite case needs an even cycle to alternate signs around, and a triangle is odd.

Trying it makes the failure concrete. Add $\varepsilon$ to the first edge; the two vertices it joins are now over their limit, so $\varepsilon$ must come off the other edge at each of them; but those are the second and third edges, and each of them now needs compensating at its far end — which is the first edge again, from which $\varepsilon$ has already been added rather than removed. Going round the triangle returns with the wrong sign, and it returns with the right sign on any even cycle. That is the whole distinction, executed.

So the relaxation’s optimum is one and a half, the true optimum is one, and the gap is real rather than an artefact of a bad formulation.

Why bipartite is the dividing line #

The previous rung’s proof finds a cycle of fractional entries and perturbs alternately around it. That argument works exactly when every cycle has even length, and a graph has only even cycles precisely when it is bipartite — which is the standard characterisation, and is the same condition that decides two-colourability.

So the chain of implications is:

Bipartite ⟹ every cycle even ⟹ the alternating perturbation closes up ⟹ no fractional corner ⟹ the relaxation is exact ⟹ the problem is a linear program.

Each arrow is short and the composite is the whole reason the assignment problem behaves. Break the first and every subsequent one fails.

The matrix formulation says the same thing. The constraint matrix of the assignment problem is totally unimodular: every square submatrix has determinant $0$, $1$ or $-1$. A totally unimodular system with whole right-hand sides has whole corners, by Cramer’s rule — the coordinates are ratios of determinants and the denominators are $\pm 1$. The incidence matrix of a graph is totally unimodular exactly when the graph is bipartite, and an odd cycle produces a submatrix of determinant $2$, which is where the halves come from.

The half in the hero figure is that determinant, showing up as a coordinate.

It is worth checking the determinant claim on the smallest case, because “an odd cycle produces a submatrix of determinant two” is otherwise a sentence to be taken on trust.

The triangle’s vertex-edge incidence matrix is three by three: each row a vertex, each column an edge, with a one where the vertex is an end of the edge. Rows and columns can be ordered so that the matrix has ones in positions $(1,1), (1,3), (2,1), (2,2), (3,2), (3,3)$ and zeros elsewhere.

Expanding along the first row gives $1 \times (1 \cdot 1 - 0 \cdot 1) - 0 + 1 \times (0 \cdot 1 - 1 \cdot 1)$, which is $1 - (-1) = 2$.

Determinant two, and by Cramer’s rule the solution of a system with that matrix has halves in it. A four-cycle’s incidence matrix, by the same expansion, has determinant zero — the rows are dependent, since alternate vertices cover every edge twice — and a system with a singular submatrix has no corner there at all. That is the arithmetic behind “even cycles are harmless”.

What the gap costs #

The consequences of a fractional corner are worth separating, because they are of three different kinds.

The relaxation stops being an answer. In the bipartite case, solving the linear program is solving the combinatorial problem, and the combinatorial problem never has to be faced. Here the program gives a number that is too good and a solution that means nothing, so an extra step — rounding, branching, cutting — is needed, and the cost of that step is the problem’s real difficulty. Everything that makes integer programming a subject rather than a special case of linear programming lives in it.

The duality gap opens. The certificate of the previous rung certifies the relaxation’s optimum, which is now strictly above the true one. So a set of prices no longer proves anything about whole matchings, and the elegant checkability is gone.

And the lottery interpretation fails. The fractional point is not a mixture of whole matchings — no mixture of things worth one is worth one and a half — so “a half on every edge” is not a lottery over anything, and cannot be read as “each pair happens half the time”. The first rung’s reading of a fractional solution as an average is available only when the corners are whole, which is the interpretive cost of losing integrality and is the one people most often forget to pay.

What is done about it #

The repair is due to Edmonds and it is one of the founding results of combinatorial optimisation.

Add, for every odd set $S$ of vertices, the inequality that the edges inside $S$ carry at most $(|S|-1)/2$ in total. For the triangle that says the three edges carry at most one, which the half-on-everything point violates.

With those added, the corners are whole again. That is Edmonds’ matching polytope theorem of 1965, and it gives a complete linear description of the matching problem on any graph.

The obvious objection is that there are exponentially many odd sets. The answer is the one this subject is built on: an exponential family of constraints is usable if a violated one can be found quickly given a candidate point, and for these it can — by a minimum-odd-cut computation. The number of constraints does not decide tractability; the difficulty of separation does.

That observation, and Edmonds’ matching algorithm which realises it combinatorially, is where the modern boundary between easy and hard optimisation problems was first drawn — and it is also where the phrase “good algorithm”, meaning polynomial time, was introduced.

The paper is worth knowing about for its framing as much as its content. Edmonds argues explicitly that “finitely many steps” is not a useful standard, since a search over all matchings is finite and useless, and proposes polynomial time as the line. That proposal is now so completely absorbed that it is hard to see it as a choice; it was one, it was made in a paper about matching, and the reason it was made there is that matching is the first problem where a clever algorithm and a brute-force one differ by more than anybody could ignore.

Setting the two figures against each other is the whole rung in two pictures. On the bipartite side a fractional table is an average of whole ones, so it means something; on the non-bipartite side a fractional point is worth more than any whole one, so it is not an average of anything and means nothing. The same arithmetic object — numbers between nought and one satisfying the constraints — has an interpretation in one case and none in the other, and which case obtains is decided by the parity of the cycles.

Where the boundary actually is #

It is tempting to conclude that bipartite means easy and everything else is hard, and that is wrong in both directions.

Non-bipartite matching is easy, despite the fractional corners, because Edmonds’ algorithm exists. So a broken relaxation does not imply a hard problem; it implies that the easy method has to be found some other way, and in this case the way took thirty years longer than the bipartite case’s.

And problems that look bipartite can be hard. Three-dimensional assignment — people, tasks and time slots, with one of each in every triple — has the same shape of constraints one dimension up and is NP-complete. Its relaxation’s corners are fractional and no repair is known, which is what being NP-complete means in practice. The two-dimensional case being easy and the three-dimensional case being hard is the same jump in dimension that breaks Pick’s theorem, and in both cases nothing in the two-dimensional statement warns of it.

So integrality of the relaxation is a sufficient condition for easiness and not a necessary one. It is the cleanest sufficient condition anybody has, which is why it is worth checking first, and a problem failing it is a problem needing more thought rather than a problem known to be hard.

The asymmetry between the two directions is worth keeping. Establishing integrality proves a problem easy, in one step, with an algorithm attached. Establishing that a relaxation has fractional corners proves nothing whatever about difficulty — it rules out one particular method and leaves every other open. A positive result about a relaxation is a theorem; a negative one is an observation.

What it costs to be at the boundary #

A model choice can cross it invisibly. Adding a constraint to an assignment problem — a person may not take two tasks in the same category, a pair of tasks must go together, a budget must be respected — usually breaks total unimodularity, and nothing about the constraint announces that. The model’s difficulty changes character and the formulation looks the same.

Checking unimodularity is not obvious. Testing whether a matrix is totally unimodular can be done in polynomial time — by Seymour’s decomposition theorem, which says every such matrix is built from network matrices and two small exceptions — and the algorithm is elaborate enough that in practice people recognise the standard cases and guess about the rest.

Rounding has no general theory. Given a fractional solution, turning it into a whole one is problem-specific: sometimes a threshold works, sometimes randomised rounding, sometimes nothing simple does. The absence of a general method is why each integrality gap has to be established separately.

And a fractional answer is not a warning anybody sees. A solver returns a number; whether the number came from a whole corner has to be checked. A great many practical formulations are solved as linear programs, rounded, and shipped, with the rounding’s cost never measured.

The gap, measured #

A relaxation that is not exact is still useful if the gap is small, and measuring it is standard practice — so it is worth knowing how large the gap here can be.

For matching on a general graph, the relaxation’s optimum is at most $3/2$ times the true one, and the triangle achieves the bound: one and a half against one. That is a worst-case ratio, it is tight, and it is small enough that the relaxation is a useful bound even where it is not an answer.

Compare that with problems where the gap is unbounded. For the travelling salesman with general distances the natural relaxation can be arbitrarily far from the truth; with distances obeying the triangle inequality the ratio is conjectured to be $4/3$ and known to be at most $3/2$, and pinning it down is a well-known open problem.

A bounded integrality gap is itself a valuable property, quite separate from exactness. It converts the relaxation from an answer into a guarantee: solve the linear program, round somehow, and the result is within a known factor. That is the standard route to an approximation algorithm, and the factor in the guarantee is usually the integrality gap.

So the boundary this rung is about has three levels rather than two: relaxations that are exact, relaxations with a small bounded gap, and relaxations with no useful bound at all. The assignment problem is in the first, general matching in the second, and a great deal of practical optimisation in the third.

What the pictures cannot show #

Total unimodularity is a property of a matrix and no figure carries a matrix. The determinant of two computed in the prose is the whole cause of the halves, and it lives in an object none of the pictures shows. The hero shows a graph and a table of corners, and the arithmetic connecting them is prose.

The corner enumeration is exhaustive at three and five edges and impossible in general. A graph with thirty edges has a relaxation in thirty dimensions whose corners cannot be listed, and the claim that some of them are fractional is a theorem rather than a search — which is the ordinary relationship between a figure that exhausts a small case and a statement about every case.

Nothing indicates which corner a solver would return. A linear program over this region has an optimum at a corner, and which corner depends on the objective; for the objective “maximise the total” it is the fractional one, and for most other objectives it is not. The figure lists the corners without saying that the fractional one is the one that matters, which is a fact about the objective rather than about the region.

And the repair is not drawn at all. Edmonds’ odd-set inequalities are a family with one member per odd subset, and the smallest instance where they do something is the triangle, where there is exactly one and it says the obvious thing. A picture of the repaired polytope would be a picture of the same triangle with one fewer corner.

Where the ladder goes next #

This rung closes the ladder’s first pass: the lottery exhibited, the corners identified, the certificate built, the non-uniqueness measured, and the boundary located here.

Named here as debts. Edmonds’ blossom algorithm, which solves non-bipartite matching combinatorially and is the constructive half of the theorem quoted above. And Seymour’s decomposition, which decides total unimodularity and is the reason the property is testable at all.

Sideways, the bipartite condition is Hall’s setting, the flow formulation whose integrality is the same fact is max-flow min-cut, and the odd cycle that breaks everything is the obstruction to two-colouring.

What is worth carrying away #

A structural property that several results depend on is worth breaking on purpose, to find out which of them were really about it.

Integrality carries this whole ladder, and removing it removes the exact relaxation, the tight certificate and the lottery reading all at once — which shows that those three were one property wearing three costumes rather than three separate achievements.

The habit worth taking is to find the smallest instance where a property fails. Here it is a triangle with a half on every edge, it fits in one figure, and it identifies the responsible feature — an odd cycle — exactly. A counterexample that small is worth more than a general theorem about when the property holds.