Polytopes and Integrality

The question

A small agency has three workers, A, B and C, and three jobs, P, Q and R. Each worker takes at most one job and each job needs at most one worker. The value of each allowed assignment is known:

The best assignment is easy to find by hand. The interesting part is what happens when you hand the problem to a linear-programming solver. Give every allowed pair a variable $x_e$, meaning "how much of worker $u$ goes to job $v$", and ask for

$$max\sum _e{w}_e{x}_e\text{s.t.}\sum _{e\ni v}{x}_e\le 1\text{ for every worker and job }v,x\ge 0.$$

Nothing in this LP says that $x_e$ must be 0 or 1. Will the solver ever hand back half a worker? For this problem, never. For a problem that looks almost the same, it will. This module explains both answers, and on the way what the simplex method does and how long it can take.

You need module 15's LPs in the form $maxc·x$, $Ax\le b$, $x\ge 0$ and its tableau simplex, and module 11's matchings. Everything else is built here.

Rounding, and enumerating

Two obvious ways to get whole numbers out of a fractional solver both waste something.

Round the answer. Take three people $u,v,w$, any two of whom may be paired, each pair worth 1. The LP's best point turns out to be $\frac{1}{2}$ on all three pairs, with value $3/2$. Rounding every $\frac{1}{2}$ up puts every person in two pairs, which is infeasible. Rounding down gives nothing, value 0, while one real pair is worth 1.

Enumerate. List every matching, or branch on every fractional variable (branch and bound). Three workers and three jobs have at most $3!=6$ full assignments, but $n$ and $n$ have $n!$, and branching can double the work with each variable.

from fractions import Fraction as F
import itertools, math

HOOK = [("A", "P", 5), ("A", "Q", 8), ("B", "P", 7), ("B", "Q", 6),
        ("B", "R", 3), ("C", "Q", 4), ("C", "R", 6)]

def best_matching(edges):
    """The oracle: skip the first edge, or take it and drop every edge touching it."""
    if not edges:
        return 0
    (u, v, w), rest = edges[0], edges[1:]
    return max(best_matching(rest),
               w + best_matching([e for e in rest if not {u, v} & {e[0], e[1]}]))

assert best_matching(HOOK) == 21            # A-Q 8, B-P 7, C-R 6
assert math.factorial(10) == 3628800        # full assignments of 10 workers to 10 jobs

The waste is that neither approach uses what the LP already knows. For the hook, the solver's answer is already whole, and the reason is geometric.

Corners are basic feasible solutions

The feasible region $P=\{x:Ax\le b,x\ge 0\}$ is an intersection of half-spaces, a convex polyhedron; when it is bounded it is a polytope. A feasible point $x$ is a vertex (a corner) if it is not the midpoint of two different feasible points. Module 15 used, without proof, that an LP with an optimum has an optimal vertex. Here is the algebraic description of vertices that makes that usable.

Call a constraint tight at $x$ if it holds with equality: a row with $a_i·x=b_i$, or a bound with $x_j=0$.

Proof. If the tight constraints have rank less than $n$, some direction $d\ne 0$ is orthogonal to all of them. Moving to $x\pm \epsilon d$ keeps every tight constraint tight, and for a small enough $\epsilon >0$ it keeps every slack constraint slack, so both points are feasible and $x$ is their midpoint: not a vertex. Conversely, suppose $x=(y+z)/2$ with $y\ne z$ feasible. If $a·x=\beta$ is tight, then $a·y\le \beta$ and $a·z\le \beta$ average to $\beta$, so both are equalities. So $d=y-z\ne 0$ satisfies $a·d=0$ for every tight constraint, and their rank is less than $n$. $◻$

After adding a slack variable to each row, "rank $n$ among the tight constraints" says the same thing as "the non-zero variables have linearly independent columns", which is module 15's basic feasible solution: the point a simplex tableau stands on. Three consequences follow. A vertex is the unique solution of $n$ tight constraints, so by Cramer's rule its coordinates are ratios of determinants of submatrices of $[Ab]$. There are at most $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$ vertices, one per choice of $n$ tight constraints out of $m+n$. And that bound is the naive algorithm: try every choice.

Take the LP we will call L: maximize $x+3y$ subject to $x\le 4$, $x+y\le 6$, $-x+y\le 3$, $y\le 4$ and $x,y\ge 0$. It has $m+n=6$ constraints, so $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ pairs of lines to try:

ROWS = [(1, 0, 4), (1, 1, 6), (-1, 1, 3), (0, 1, 4), (-1, 0, 0), (0, -1, 0)]  # a*x + b*y <= r

def corners(rows):
    """Every intersection of two constraint lines that satisfies all the constraints."""
    solved, found = 0, set()
    for (a, b, r), (c, d, s) in itertools.combinations(rows, 2):
        det = a * d - b * c
        if det == 0:
            continue                          # parallel lines never meet
        solved += 1
        x, y = F(r * d - b * s, det), F(a * s - c * r, det)      # Cramer's rule
        if all(p * x + q * y <= t for p, q, t in rows):
            found.add((x, y))
    return solved, sorted(found)

solved, L_corners = corners(ROWS)
assert math.comb(6, 2) == 15 and solved == 13
assert L_corners == [(0, 0), (0, 3), (1, 4), (2, 4), (4, 0), (4, 2)]
assert max(x + 3 * y for x, y in L_corners) == 14          # at (2, 4)

Thirteen of the 15 pairs meet (two pairs are parallel), and only 6 of those 13 points are feasible. In $n$ dimensions the number of candidate systems grows like $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$, which is exponential in $n$. The simplex method looks at far fewer.

The simplex method walks from corner to corner

A simplex tableau always represents a basic feasible solution, so by the theorem the method only ever stands on vertices. A pivot swaps one tight constraint for another: the entering column leaves its bound, and the leaving row becomes tight. Geometrically, it slides along an edge of the polytope to an adjacent vertex, and the objective never goes down. At a degenerate vertex, where more than $n$ constraints are tight, a pivot can swap constraints without moving at all.

The pivot rule chooses the entering column among those with a negative reduced cost. Bland's rule takes the smallest index; it never cycles, which is why the course's toolkit uses it. Dantzig's rule takes the most negative reduced cost, the steepest improvement per unit. Here is a minimal tableau simplex that records every vertex it stands on (for $b\ge 0$, so the origin is a starting vertex, and for bounded LPs):

def walk(c, A, b, rule="bland"):
    """Tableau simplex for max c.x, Ax <= b, x >= 0 with b >= 0. Returns the vertices visited."""
    m, n = len(A), len(c)
    T = [[F(v) for v in A[i]] + [F(int(i == k)) for k in range(m)] + [F(b[i])] for i in range(m)]
    T.append([F(-v) for v in c] + [F(0)] * (m + 1))           # the objective row
    B = [n + i for i in range(m)]                               # the slacks start basic
    def point():
        x = [F(0)] * (n + m)
        for i, j in enumerate(B):
            x[j] = T[i][-1]
        return tuple(x[:n])
    path = [point()]
    while True:
        neg = [j for j in range(n + m) if T[-1][j] < 0]
        if not neg:
            return path
        s = neg[0] if rule == "bland" else min(neg, key=lambda j: (T[-1][j], j))
        r = min((i for i in range(m) if T[i][s] > 0), key=lambda i: (T[i][-1] / T[i][s], B[i]))
        T[r] = [v / T[r][s] for v in T[r]]
        for i in range(m + 1):
            if i != r:
                T[i] = [a - T[i][s] * p for a, p in zip(T[i], T[r])]
        B[r] = s
        path.append(point())

cL, AL, bL = [1, 3], [[1, 0], [1, 1], [-1, 1], [0, 1]], [4, 6, 3, 4]
assert walk(cL, AL, bL) == [(0, 0), (4, 0), (4, 2), (2, 4)]
assert walk(cL, AL, bL, "dantzig") == [(0, 0), (0, 3), (1, 4), (2, 4)]
assert all(p in L_corners for p in walk(cL, AL, bL) + walk(cL, AL, bL, "dantzig"))

Both walks visit 4 of L's 6 corners. Bland's rule enters $x$ first because it has the smaller index, and so it goes the long way along the bottom. Dantzig's rule enters $y$, whose coefficient 3 is larger, and climbs the left side. On L the two cost the same.

How long can the walk be?

Klee and Minty (1972) squashed an $n$-dimensional cube so that the objective increases along a path through all $2^n$ corners, and Dantzig's rule follows that path. One version is

$$max\sum _{j<n}{2}^{n-1-j}{x}_j\text{s.t.}\sum _{j<i}{2}^{i-j+1}{x}_j+x_i\le 5^{i+1}(i=0,\dots ,n-1),x\ge 0.$$

In two dimensions it is $max2x_0+x_1$ with $x_0\le 5$ and $4x_0+x_1\le 25$:

def klee_minty(n):
    c = [2 ** (n - 1 - j) for j in range(n)]
    A = [[2 ** (i - j + 1) if j < i else int(i == j) for j in range(n)] for i in range(n)]
    return c, A, [5 ** (i + 1) for i in range(n)]

assert walk(*klee_minty(2), "dantzig") == [(0, 0), (5, 0), (5, 5), (0, 25)]
path3 = walk(*klee_minty(3), "dantzig")
assert path3 == [(0, 0, 0), (5, 0, 0), (5, 5, 0), (0, 25, 0),
                 (0, 25, 25), (5, 5, 65), (5, 0, 85), (0, 0, 125)]
assert [4 * a + 2 * b + c for a, b, c in path3] == [0, 20, 30, 50, 75, 95, 105, 125]

In three dimensions the walk visits all 8 corners of the squashed cube, and the objective rises at every step: 0, 20, 30, 50, 75, 95, 105, 125. The pattern is recursive. The walk solves the $(n-1)$-dimensional cube on the "floor" $x_{n-1}=0$, steps up once, then walks the floor's cube backwards on the "ceiling". So $P(n)=2P(n-1)+1$ pivots, which gives $2^n-1$. That recursion is Klee and Minty's theorem for their construction. For this particular family the course verifies the count by running it, as the next section shows.

Other rules do not escape. Exponential examples are known for Bland's rule and many other common pivot rules, and whether any pivot rule needs only polynomially many pivots is open.

LPs are still solvable in polynomial time, by methods that do not walk along edges. The ellipsoid method (Khachiyan, 1979) and interior-point methods (Karmarkar, 1984) run in time polynomial in the number of bits needed to write the input down. Both are stated here without proof. An interior-point method moves through the inside of the polytope and may end at a non-vertex point of the optimal face; a final "crossover" step moves to a vertex. In practice simplex is usually fast. Spielman and Teng (2004) proved that its expected number of pivots is polynomial once the input is perturbed slightly at random (smoothed analysis). Production solvers offer both kinds of method.

Measure the claim

Pivots of the walk above on the Klee–Minty family, under both rules:

dantzig = [len(walk(*klee_minty(n), "dantzig")) - 1 for n in range(1, 9)]
bland = [len(walk(*klee_minty(n), "bland")) - 1 for n in range(1, 9)]
assert dantzig == [2 ** n - 1 for n in range(1, 9)]
assert bland == [1, 3, 5, 9, 15, 25, 41, 67]
assert all(bland[k] == bland[k - 1] + bland[k - 2] + 1 for k in range(2, 8))
assert all(walk(*klee_minty(n), r)[-1][-1] == 5 ** n for n in range(1, 9) for r in ("bland", "dantzig"))

Dantzig's count is exactly $2^n-1$ on every cube measured. Bland's count is smaller, but each entry is the sum of the previous two plus one, so on these instances it grows by a factor of about 1.6 per dimension: still exponential, just with a smaller base. These are measurements on one family, $n\le 8$. They illustrate the theorems but do not prove them.

When the corners are whole numbers

Back to the question. Run the same walk on the hook's matching LP:

def matching_lp(vertices, edges):
    A = [[int(v in (e[0], e[1])) for e in edges] for v in vertices]
    return [e[2] for e in edges], A, [1] * len(vertices)

hook_path = walk(*matching_lp(["A", "B", "C", "P", "Q", "R"], HOOK))
assert len(hook_path) - 1 == 9
assert all(v in (0, 1) for point in hook_path for v in point)     # every corner visited is 0/1
assert hook_path[-1] == (0, 1, 1, 0, 0, 0, 1)                      # A-Q, B-P, C-R
assert sum(e[2] * v for e, v in zip(HOOK, hook_path[-1])) == 21 == best_matching(HOOK)

Nine pivots, and every corner it stands on, not just the last one, is a 0/1 vector: a matching. That is no accident of this instance.

Theorem (bipartite matching polytope). If the graph is bipartite, every vertex of $\{x\ge 0:{\sum }_{e\ni v}{x}_e\le 1\text{ for all }v\}$ is a 0/1 vector.

The proof shows that any feasible point with a fractional edge is a midpoint, so it cannot be a vertex. Take the point with $\frac{1}{2}$ on A–P, A–Q, B–P, B–Q and 1 on C–R. It is feasible, and its weight is $(5+8+7+6)/2+6=19$. Its fractional edges form the cycle A–P–B–Q–A. Put $d=+1$ on A–P and B–Q and $d=-1$ on A–Q and B–P, alternating around the cycle. Every vertex of the cycle meets one $+1$ edge and one $-1$ edge, so its load does not change under $x\pm \epsilon d$:

X = [F(1, 2), F(1, 2), F(1, 2), F(1, 2), 0, 0, 1]     # edge order as in HOOK
d = [1, -1, -1, 1, 0, 0, 0]                            # alternate around A-P-B-Q-A

def load(edges, x):
    total = {}
    for (u, v, _), xe in zip(edges, x):
        total[u] = total.get(u, 0) + xe
        total[v] = total.get(v, 0) + xe
    return total

def weight(edges, x):
    return sum(e[2] * xe for e, xe in zip(edges, x))

up = [a + F(1, 2) * b for a, b in zip(X, d)]
down = [a - F(1, 2) * b for a, b in zip(X, d)]
assert load(HOOK, X) == load(HOOK, up) == load(HOOK, down)       # every load unchanged
assert (up, down) == ([1, 0, 0, 1, 0, 0, 1], [0, 1, 1, 0, 0, 0, 1])
assert (weight(HOOK, X), weight(HOOK, up), weight(HOOK, down)) == (19, 17, 21)

Proof in full. Let $x$ be feasible with at least one fractional edge, and let $F$ be the set of fractional edges.

• $F$ contains a cycle. The graph is bipartite, so the cycle is even, and signs $+1,-1,+1,\dots$ around it close up consistently. Every vertex on the cycle meets one edge of each sign, so its load is unchanged. Take $\epsilon ={min}_{e}min(x_e,1-x_e)>0$ over the cycle's edges. Then both $x\pm \epsilon d$ stay in $[0,1]$ on every edge and keep every load, so both are feasible.
• $F$ is a forest. Take a longest path in it. Its interior vertices are balanced as before. An end vertex meets exactly one fractional edge, since otherwise the path could be extended (or would close a cycle). Its other edges are integral, and none can be 1, because together with the fractional edge its load would exceed 1. So its load equals that one edge's value, which is below 1, and moving that edge by $\pm \epsilon$ with $\epsilon ={min}_{e}min(x_e,1-x_e)$ keeps the load in $[0,1]$.

Either way $x=\frac{1}{2}(x+\epsilon d)+\frac{1}{2}(x-\epsilon d)$ with the two points different, so $x$ is not a vertex. Every vertex is therefore 0/1, and a 0/1 feasible point is exactly a matching. $◻$

The proof is also an algorithm. Push in whichever direction does not lower the weight, and go as far as feasibility allows, until some edge reaches 0 or 1. Each push makes at least one more edge whole and never makes a whole edge fractional. So at most $|E|$ pushes turn any feasible point into a matching at least as heavy.

Where it breaks: the triangle

Now the three people $u,v,w$, any two of whom may pair up, each pair worth 1.

TRI = [("u", "v", 1), ("v", "w", 1), ("u", "w", 1)]
c3, A3, b3 = matching_lp(["u", "v", "w"], TRI)
tri_path = walk(c3, A3, b3)
assert tri_path[-1] == (F(1, 2), F(1, 2), F(1, 2)) and sum(tri_path[-1]) == F(3, 2)
assert tri_path[1] == tri_path[2]              # one degenerate pivot: it swapped, did not move
assert best_matching(TRI) == 1

def det3(M):
    (a, b, c), (d, e, f), (g, h, i) = M
    return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)

assert A3 == [[1, 0, 1], [1, 1, 0], [0, 1, 1]] and det3(A3) == 2

The point $(\frac{1}{2},\frac{1}{2},\frac{1}{2})$ is a genuine vertex. All three vertex constraints are tight there, and their matrix has determinant $2\ne 0$, so they are independent: rank 3 in 3 dimensions. The simplex method stops on it with value $3/2$, while the best real pairing is worth 1. The walk also makes one degenerate pivot, changing the basis without moving.

The proof fails at exactly one step. The fractional edges form a triangle, an odd cycle. Alternating $+,-,+$ around it puts two $+$ edges on one vertex, whose load rises by $2\epsilon$. There is no direction to split along. Cramer's rule shows where the $\frac{1}{2}$ comes from: a vertex's coordinates are ratios with the determinant, here 2, in the denominator.

Integrality for every graph needs more constraints. Edmonds (1965) showed that adding ${\sum }_{e\subseteq S}{x}_e\le (|S|-1)/2$ for every odd set $S$ of vertices makes the polytope integral for all graphs. That theorem is stated here, not proved.

Total unimodularity

The determinant is the whole story, and it has a name. A matrix is totally unimodular (TU) if every square submatrix has determinant $-1$, $0$ or $1$.

Theorem. If $A$ is TU and $b$ is integral, every vertex of $\{x:Ax\le b,x\ge 0\}$ is integral. Proof. A vertex is the unique solution of $n$ independent tight constraints: a non-singular square system $Mx=b^{\prime }$ whose rows come from $A$ or from the identity (the tight bounds $x_j=0$). Expanding along the identity rows shows $detM$ is $\pm$ a square subdeterminant of $A$, so $detM=\pm 1$. Cramer's rule divides integers by $\pm 1$. $◻$

Lemma. The vertex–edge incidence matrix of a bipartite graph is TU. Proof sketch. Induct on the size of a square submatrix $M$. If some column of $M$ is zero, $detM=0$. If some column has a single 1, expand along it to a smaller submatrix, which is TU by induction. Otherwise every column has two 1s, one in a row of each side. Then the rows of one side and the rows of the other side both sum to the all-ones vector, so the rows are dependent and $detM=0$. $◻$

The same argument works for directed incidence matrices, with one $+1$ and one $-1$ per column, which is why max flow and min-cost flow with integer capacities have integral optimal solutions (modules 11–13). The triangle's matrix is not TU, since its determinant is 2. Neither is a general coefficient matrix such as $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$, whose determinant is 3.

Complexity achieved. With a TU matrix and integral data, a yes-or-no problem is solved as an LP with no rounding step: any method that returns an optimal vertex returns an integral answer. A polynomial LP method plus a final move to a vertex gives a polynomial algorithm for weighted bipartite matching, instead of $n!$ enumeration. Simplex itself has no polynomial pivot guarantee (Klee–Minty).

A problem that looks different

A city's streets run north–south and east–west. A camera placed at an intersection watches both streets through it. The city wants every street watched by the fewest cameras, and it plans to ask a solver that allows fractional cameras. Can it trust the solver to answer in whole cameras? Nothing here mentions workers or jobs. The lab's last problem is a different one.

Practise

The lab starts from the algebra. You will write the test "is this point a vertex?" and watch it hold at every point the simplex method visits on a new LP. Then you predict and carry out one split of a fractional point along an alternating cycle, and turn the split into a procedure that makes any fractional point of a bipartite graph whole. After that you measure pivot counts on a second Klee–Minty family under two rules. The last problem does not say what it is.

Recap

You can now: decide whether a point is a vertex by the rank of its tight constraints; follow the simplex method as a walk along edges between vertices; prove that bipartite matching LPs have 0/1 vertices, and show that a triangle breaks this; state total unimodularity and use it to trust an LP's answer to be whole.

Invariant: in a bipartite graph, a fractional feasible point sits in the middle of an even alternating cycle or path of fractional edges, so it is not a vertex.

Complexity achieved: an integral optimum from one LP solve, with no rounding and no branching, against $n!$ enumeration. Simplex can take $2^n-1$ pivots (Dantzig's rule on Klee–Minty, and exponentially many for Bland's rule on the measured cubes), while the ellipsoid and interior-point methods are polynomial in the input's bit length.

Failure mode: believing that "LP optima are vertices" means "LP optima are integral". The triangle's $(\frac{1}{2},\frac{1}{2},\frac{1}{2})$ is a vertex too. Integrality comes from the constraint matrix, and rounding a fractional answer can be infeasible or far from optimal.

In real software: the HiGHS solver, which SciPy's scipy.optimize.linprog calls, offers both a dual simplex method (method="highs-ds") and an interior-point method (method="highs-ipm"). Mixed-integer solvers such as HiGHS and SCIP solve LP relaxations inside branch and bound, so an integral relaxation ends the search at its first node.

Retrieval: module 11 proved that a network with whole-number capacities has a whole-number maximum flow without any LP. What was that argument, and which lemma above gives the same conclusion from the constraint matrix?

Check yourself

1. Why is the point with $\frac{1}{2}$ on the cycle A–P–B–Q not a vertex, and exactly where does the argument use that the graph is bipartite?
2. Run the hook's matching LP with Dantzig's rule instead of Bland's. Could the walk ever stand on a point with a fractional coordinate? Why, or why not?
3. On the Klee–Minty cube with $n=8$, compare Dantzig's rule with Bland's rule. What do the counts show, and what do they not show?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.