Walking the Corners

The simplex method, duality, and the art of choosing a pivot

Slides by: Danielle Ripsman
Made for: Optimal Lab · Johns Hopkins University

Linear programs (LPs)

Making the most of limited resources

Business decisions

decide
how much of each product to make
limited by
materials, machine time, staff hours
goal
maximize profit
Our running example: a small bakery.

Radiation therapy planning

decide
the intensity of each beam
must meet
the prescribed dose to the tumor
goal
as little dose to healthy organs as possible
We assume dose at each point is linear in the beam intensities.

Scheduling appointments

decide
which patients go in which slots
limited by
clinicians, rooms, hours in the day
goal
minimize patient wait time
Whole-number decisions: integer programs, which solve many LPs along the way.
Same shape every time: \(\underbrace{\max\ \OB{c^\top x}}_{\text{goal}} \quad \text{s.t.} \quad \underbrace{Ax \le b}_{\text{limited resources}}, \quad \underbrace{x \ge 0}_{\text{decisions}}\)

A small business example: our bakery

Two products, three limited resources

breadcakeavailable
flour2110
oven hours3216
labor hours1212
profit / batch98

$ per batch. Units are made up; I'm not actually a baker.

\(x_1\) = bread batches,  \(x_2\) = cake batches decisions
\(\max\ \OB{z = 9x_1 + 8x_2}\) profit*
\(\text{s.t.}\ \ \FL{2x_1 + x_2 \le 10}\) flour
\(\phantom{\text{s.t.}}\ \ \OV{3x_1 + 2x_2 \le 16}\) oven hours
\(\phantom{\text{s.t.}}\ \ \LB{x_1 + 2x_2 \le 12}\) labor hours
\(\phantom{\text{s.t.}}\ \ x_1,\ x_2 \ge 0\) no negative items (why?)
\(\implies\) would imply we can unmake less profitable items and harvest their flour, labor and oven hours for more profitable products
*recall: profit = revenue − cost

Our bakery in the general form

The formula from slide 2, filled in with the bakery's numbers

breadcakeavailable
flour2110
oven hours3216
labor hours1212
profit / batch98
\(\max\ c^\top x \quad \text{s.t.} \quad Ax \le b, \quad x \ge 0\)
\(\max\ \textcolor{d9aa14}{\underline{c}}^\top x \quad \text{s.t.} \quad Ax \le b, \quad x \ge 0\)
\(\max\ c^\top x \quad \text{s.t.} \quad \textcolor{f2a7c3}{\underline{A}}x \le b, \quad x \ge 0\)
\(\max\ c^\top x \quad \text{s.t.} \quad Ax \le \textcolor{9aa0ad}{\underline{b}}, \quad x \ge 0\)
\(\max\ \OB{c}^\top x \quad \text{s.t.} \quad \textcolor{f2a7c3}{A}x \le \textcolor{9aa0ad}{b}, \quad x \ge 0\)
profit per batch\(\OB{c^\top = \begin{pmatrix} 9 & 8 \end{pmatrix}}\)
resources used per batch
rows: resources · columns: products
\(\textcolor{f2a7c3}{A = \begin{pmatrix} \FL{2} & \FL{1} \\ \OV{3} & \OV{2} \\ \LB{1} & \LB{2} \end{pmatrix}}\)
resources available\(\textcolor{9aa0ad}{b^\top = \begin{pmatrix} \FL{10} & \OV{16} & \LB{12} \end{pmatrix}}\)
\(\max\ \OB{\begin{pmatrix} 9 & 8 \end{pmatrix}} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \quad \text{s.t.} \quad \textcolor{f2a7c3}{\begin{pmatrix} \FL{2} & \FL{1} \\ \OV{3} & \OV{2} \\ \LB{1} & \LB{2} \end{pmatrix}} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \le \textcolor{9aa0ad}{\begin{pmatrix} \FL{10} \\ \OV{16} \\ \LB{12} \end{pmatrix}}, \quad x \ge 0\)

Every constraint cuts the plane in half

The plans that satisfy all of them form the feasible region

\(x_1, x_2 \ge 0\): the positive quadrant
\(\FL{2x_1 + x_2 \le 10}\)\(x_1\)-intercept \((5, 0)\), \(x_2\)-intercept \((0, 10)\)
\(\OV{3x_1 + 2x_2 \le 16}\)\(x_1\)-intercept \((\tfrac{16}{3}, 0)\), \(x_2\)-intercept \((0, 8)\)
\(\LB{x_1 + 2x_2 \le 12}\)\(x_1\)-intercept \((12, 0)\), \(x_2\)-intercept \((0, 6)\)
Five corners. Each one is where two constraints meet.

Slide the profit line

All plans with the same profit lie on one line

\(\OB{9x_1 + 8x_2 = z}\)
z = 0

Push the line in the direction of the arrow, as far as the region allows.

The last plan it touches is a corner: \((2, 5)\), profit \(\OB{58}\).

Any further and no plan is left.

profit z
last feasible plan: 58 ▲

Always a corner… unless the profit line is parallel to an edge

Turn the profit direction and watch the best corner

Best plan: one corner.
bread profit
▲
Parallel to an edge ⇒ the whole edge ties. Its two ends are still corners, so checking corners is always enough.

Optimality: how do we prove 58 is the best?

Plan feasibility is easy to check

Bake \(x = (2, 5)\):

\(\FL{2\cdot2 + 5 = 9 \le 10}\) ✓
\(\OV{3\cdot2 + 2\cdot5 = \boldsymbol{16 \le 16}}\) ✓
\(\LB{2 + 2\cdot5 = \boldsymbol{12 \le 12}}\) ✓

Profit:  \(\OB{9\cdot2 + 8\cdot5 = 58}\).

"Nothing beats it" is harder

Check every corner? Fine here: there are 5.*

A business with 50 products and 50 resources: up to \(\binom{100}{50} \approx 10^{29}\) corners.

We want a short proof that anyone can check.

*\(\binom{5}{2} = 10\) possible corners in our 2D problem, but only 5 are feasible

LPs have a “built in” proof, in the form of an upper bound. Given \(n\) variables and \(m \ge n\) constraints, the best plan sits where \(n\) of the constraints meet, and the proof is built from those same constraints. When a valid upper bound meets a valid lower bound, we are at optimality, and the principle of strong duality guarantees that, whenever there is a best plan, they meet.

Duality and bounds*

\(\max\ \OB{9x_1 + 8x_2}\)
  • A feasible solution to our original model (called the primal model) is a lower bound.
    \(9(0) + 8(0) = \OB{0}\)lower bound
    →
    \(9(5) + 8(0) = \OB{45}\)new lower bound
    →
    \(9(4) + 8(2) = \OB{52}\)new lower bound
    →
    \(9(2) + 8(5) = \OB{58}\)new lower bound
  • Any function with coefficients ≥ our objective function's coefficients is ≥ our objective function, for any value of \(x \ge 0\).
    e.g., \(\OB{9}x_1 + \OB{8}x_2 \le 10x_1 + 8x_2\)
  • We can thus use constraints, that are all true for this problem, to bound our objective function from above:
    \(\FL{2x_1 + x_2 \le 10} \quad (\times\, \FL{8}) \quad \Rightarrow \quad 16x_1 + 8x_2 \le 80\)
    \(z = \OB{9x_1 + 8x_2} \le 16x_1 + 8x_2 \le 80\)

* Adapted from A. Majumdar, “Duality: the unsung hero of optimization explained through an example”, Towards Data Science (2021).

Understanding dual variables

Given our primal model, we can assign a dual variable \(y\) to each constraint

  • Our first dual guess from the previous slide was \(y^\top = (\FL{8}, \OV{0}, \LB{0})\), with \(z \le 80\).
  • Constraint 2 would give us \(y^\top = (\FL{0}, \OV{4}, \LB{0})\): \(z \le 64\); constraint 3, \(y^\top = (\FL{0}, \OV{0}, \LB{9})\): \(z \le 108\). So 64 is our best upper bound so far.
  • We can also take combinations of the constraints, but they need to remain ≥ our coefficient values.

The bound game: add up the constraints

Pick a dual variable ≥ 0 for each resource. If the mix covers the profit, it is a valid dual: it caps the profit.

sum:
sum coversprofitdual slack
(covers − profit)
bread \(x_1\)9
cake \(x_2\)8

Formalizing the dual

The bound game as an LP: choose \(y \ge 0\) so the mix covers every product's profit, with the smallest bound

Primal
Dual
min: we want the smallest upper bound

Primal and dual, in general

Primal
\(\max\)\(\OB{c}^\top x\) \(\text{s.t.}\)\(\textcolor{f2a7c3}{A}x \le \textcolor{9aa0ad}{b}\)\((y)\) \(x \ge 0\)
\(n\) variables, \(m\) constraints
Dual
\(\min\)\(\textcolor{9aa0ad}{b}^\top y\) \(\text{s.t.}\)\(\textcolor{f2a7c3}{A}^\top y \ge \OB{c}\) \(y \ge 0\)
\(m\) variables, \(n\) constraints

Turning slack into a decision variable (and inequalities into equalities)

Slack is a big part of optimality, and we can turn it into a variable, just like our \(x\)'s

A slack variable \(s_i\) is how much of resource \(i\) is left over:

\(\FL{2x_1 + x_2 + s_1 = 10}\)
\(\OV{3x_1 + 2x_2 + s_2 = 16}\)
\(\LB{x_1 + 2x_2 + s_3 = 12}\)
\(x_1, x_2, s_1, s_2, s_3 \ge 0\)
\(x\) on a line ⇔ that resource is used up ⇔ its slack is 0.
At a corner, two things are zero.

3 equations, 5 unknowns: set 2 to 0, solve for the other 3

  • Set 2 of them to 0 (here \(s_1 = s_2 = 0\): flour and oven are tight), then solve the 3 equations for the other 3 (the basic variables, or the basis; the 2 zeros are nonbasic).
  • \(x_1 = s_2 = 0\) is a corner too, at \((0, 8)\), but solving gives \(s_3 = -4\): labor runs over. Not a feasible corner.
  • Try it yourself: hit clear, then click any 2 boxes to set them to 0; the other 3 get solved for. There are \(\binom{5}{2} = 10\) corners and 5 are feasible. Find them all!

Dual slack: the same trick for the dual (≥ into =)

Each dual constraint, one per product, gets a slack too

A dual slack \(d_j\) is how much the mix over-covers product \(j\)'s profit:

\(\FL{2y_1} + \OV{3y_2} + \LB{y_3} - d_1 = \OB{9}\)bread
\(\FL{y_1} + \OV{2y_2} + \LB{2y_3} - d_2 = \OB{8}\)cake
\(y_1, y_2, y_3, d_1, d_2 \ge 0\)
At each corner, \(y\) is fixed by its two tight constraints: \(y^\top = c_B^\top B^{-1}\) (\(B\): the columns of the corner's basic variables, its basis; \(c_B\): their profits).
Inside the region the primal is valid; outside, the dual can be.
Outside bounds: 80, 64, 108, 61.33. Only \((2, 5)\) has both: \(58 = 58\).

Two readings of the same equations

The primal and the dual are two readings of the same equations: at a corner, the tight constraints form one square system. Click a ringed corner.

primal
by rows
dual
by columns
primal
⇓ row-reduce
dual
⇓ row-reduce

Primal and dual variables and slacks at a corner point

Every primal variable has a dual partner: \(x_j\) with its dual slack \(d_j\), \(s_i\) with its dual variable \(y_i\)

  • Primal: the corner's 2 tight constraints give 2 zeros (a slack, or an \(x\) on its axis); the other 3 are solved for: the basis.
  • Dual: the partners of those 3 are 0; the other 2 are solved for: the multipliers of the 2 tight constraints (the dual's basis).
  • In every pair at least one is 0: complementary slackness. The corner is optimal when both rows are \(\ge 0\).

Common names and interpretations for parts of the dual

Dual variable = shadow price

\(\FL{y_1}, \OV{y_2}, \LB{y_3}\): what one more unit of each resource is worth. At the optimum, \(y = (\FL{0}, \OV{2.5}, \LB{1.5})\).

Best profit = best bound = \(\FL{10y_1} + \OV{16y_2} + \LB{12y_3}\), so one more oven hour adds \(\OV{y_2}\), as long as the same dual stays best: 17 hours ⇒ 58 → 60.5, that's \(+\OV{2.5}\). One more unit of flour ⇒ +0 (we already have spare).

Dual slack = reduced cost

Each product has a dual constraint: the value of the resources it uses must cover its profit (bread: \(\FL{2y_1} + \OV{3y_2} + \LB{y_3} \ge \OB{9}\)). Its slack is the product's reduced cost: value of the resources it uses − its profit.

Negative ⇒ the prices undervalue it ⇒ worth making more. At \((0, 0)\) every price is 0, so \(d_1 = -9\) and \(d_2 = -8\): both are worth making.

The simplex method, in one picture

The best plan is always at a corner, so walk from corner to corner

  1. Start at a corner.
  2. Look along the edges. Which ones improve profits? (duals)
  3. Walk one to the next corner (profit never goes down). Repeat.
  4. Stop when no edge improves profits.
There was a shorter way (2 pivots vs. 3 pivots). Which edge to take is the pivot rule, and it's the question this talk builds up to.

Putting it all together: how simplex works

Relax dual feasibility. Go from corner point to feasible corner point, guided by dual variable values towards dual feasibility.

This is essentially the revised simplex method. Real solvers skip \(D\) and reuse \(B\): \(y^\top = c_B^\top B^{-1}\), because \(B^{-1}\) already holds what \(D\) needs. They also update \(B\)'s factorization at each pivot instead of rebuilding it: much cheaper on large problems.

The tableau: all the bookkeeping in one place

Bottom row: reduced costs (dual slacks) under the products, shadow prices (dual variables) under the slacks

Optimal ⇔ every bottom-row entry ≥ 0: the primal is feasible and the dual is valid. Here \(-9\) and \(-8\) say: not yet.

Pivoting: enter, walk the edge, leave, repeat

One step per click: entering variable, min ratio test, exiting variable, pivot

What if we chose the other direction?

Cake (−8) is negative too, so it can enter first: same steps, a different route

2 pivots or 3: does it matter?

Not for our bakery. But real problems are bigger, often integer, and rarely start at a convenient corner.

Bigger problems

thousands to millions

Real LPs (airline crews, power grids, supply chains) have thousands to millions of variables and constraints. Each pivot scales with the increased problem size.

Integer problems

an LP at every node

Whole-number decisions (appointment slots, how many trucks) are solved by branch and bound, i.e., many LPs per problem, meaning a few extra pivots per LP add up fast.

Harder starts

no easy first corner

In our bakery, zero product is feasible. "At least" or "exactly" constraints (bake at least 20 batches, staff exactly 8 hours) would require simplex to run an additional phase to find a feasible start.

Even one more dimension on this toy problem changes the landscape. Next: a third product.

A new product: cookies. Worth making?

Price it with the shadow prices we already have

breadcakecookiesavailableprice \(y\)
flour211100
oven hours321162.5
labor hours121121.5
profit / batch985
value of a batch \(= 1\cdot\FL{0} + 1\cdot\OV{2.5} + 1\cdot\LB{1.5} = 4\)
reduced cost \(d_3 = 4 - \OB{5} = -1\)
\(B^{-1}a_3 = B^{-1}(1,\ 1,\ 1)^\top = (0,\ 0.5,\ 0.5)^\top\)

Cookies' column in the tableau. \(B^{-1}\) is the highlighted slack block, so this is its row sums: per batch, cake drops 0.5, spare flour drops 0.5, bread stays put.

Cookies add a dimension

Our pentagon, seen from above.

Tilt the camera: it is the floor of a 3D picture, where \(x_3 = 0\) (no cookies).

Each constraint becomes a plane, and the plans form a polyhedron with 8 corners.

The 2D picture was the floor all along.
Drag the picture to rotate it.

Slide the profit plane

In 3D, all plans with the same profit lie on a plane

\(\OB{9x_1 + 8x_2 + 5x_3 = z}\)
z = 0

Push the plane along the arrow. The gold slice is every plan that earns exactly z.

The slice shrinks to a single corner: \((2, 4, 2)\), profit \(\OB{60}\).

Any further and no plan is left.

One pivot up

Cookies enter; walk up the edge until a resource runs out

The 3D dual: three planes meet at the corner

\(2 \times (\FL{2x_1 + x_2 + x_3 \le 10})\)
\(1 \times (\OV{3x_1 + 2x_2 + x_3 \le 16})\)
\(2 \times (\LB{x_1 + 2x_2 + x_3 \le 12})\)
\(= 9x_1 + 8x_2 + 5x_3 \le 60\)

That is exactly the profit \(\OB{9x_1 + 8x_2 + 5x_3}\), so no plan beats 60, and \((2, 4, 2)\) earns 60.

Three tight planes, three unknowns ⇒ one corner. The profit arrow lies inside the cone of the planes' outward directions ⇔ every multiplier ≥ 0 ⇔ optimal.

(In other words, the objective direction is a nonnegative combination of the three tight constraints, so the corner is primal and dual feasible ⇔ optimal.)

One corner, four rules

At the origin, bread, cake and cookies all have negative reduced costs. Which one enters?

bread \(x_1\)cake \(x_2\)cookies \(x_3\)
reduced cost \(d\)
Dantzig: most negative \(d\)
step until a resource runs out \(t^*\)
Greatest increment: biggest gain \(|d|\,t^*\)
edge length² \(1 + \lVert B^{-1}a_j \rVert^2\)
Steepest edge: \(d^2 \,/\) length²
Bland: lowest index

The edge length counts all six variables, leftovers included: a batch of bread uses up a lot of resources.

Three different answers at the same corner. Each rule is a different guess at which edge leads to the top fastest.

The race: same polyhedron, four routes

Every rule reaches the same optimum (2, 4, 2), by a different path

Dantzig
most negative d
Bland
lowest index
Steepest edge
best gain per unit length
Greatest increment
biggest gain this step
Dantzig solves the bread-and-cake problem on the floor first, then climbs: 4 pivots. The others need 3, the fewest possible here (there are four different shortest routes). On a problem this small the gap is one pivot. It can be much worse…

When the rule really matters: the Klee–Minty cube

\(\max\ 4x_1 + 2x_2 + x_3\) s.t. \(x_1 \le 5,\ 4x_1 + x_2 \le 25,\ 8x_1 + 4x_2 + x_3 \le 125\) (axes rescaled to look like a cube)

Dantzig
Steepest edge
Dantzig visits all 8 corners (7 pivots); steepest edge goes straight to the top (1 pivot). The same construction in n dimensions makes Dantzig take \(2^n - 1\) pivots: about \(10^{15}\) in 50 dimensions. (Bland: 5 here.)

Two more things about rules

Devex

Steepest edge needs the length of every candidate edge at every pivot, which is expensive on large problems. Devex keeps cheap running estimates of those lengths instead.

Real solvers use Devex or steepest edge. On the bakery, Devex makes the same choices as Bland.

Bland's rule and cycling

At a degenerate corner (more constraints tight than needed), a pivot can change the basis without moving. A careless rule can then cycle through the same bases forever.

Bland's rule provably never cycles. It is slow in practice, so it is mostly a safety net; solvers also break ties with small perturbations.

For our research, we can depict rules as a pivot timeline

All previous routes without the polyhedron (meaning it can generalize for much larger LPs)

Columns are pivots: start → … → optimum.
Rows are variables. A node is the variable that enters at that pivot; ↓ marks the one that leaves.
Each coloured thread is one rule. Dantzig's needs an extra column.
A* (black) searches every option to find a provably shortest route. Far too slow to run inside a solver, but it shows how short a route can be.

Klee–Minty, as a timeline

Dantzig's thread snakes through 7 columns; steepest edge and A* jump straight to the optimum

Our question: can a policy learn to pick pivots?

Pivots needed on an LP with 40 products and 40 resources

A short route exists: 6 pivots. A* proves it, but only by searching far more than a solver can afford.
Every rule is a fixed guess about which edge to take. The best one here needs 9; Bland needs 37.
SimplexRL: learn the guess. A neural policy looks at the current tableau, picks the entering variable, and is rewarded for reaching the optimum in fewer pivots.

40 products, 40 resources: no picture, same timeline

An 80-dimensional polyhedron we can't draw, but every route is still visible

Inside SimplexRL: a network that learns to pivot in progress

Our current model, walked through on the bakeryFelix Parker, Emmett Springer, Danielle Ripsman, Kimia Ghobadi

1 · Read the LP once per problem

Variables and constraints become nodes; each nonzero of \(A\) is an edge (thicker = bigger coefficient).

A graph neural network passes messages along the edges; each coloured strip is a node's vector (embedding).

2 · Compare the candidates every pivot

Each candidate (negative reduced cost) adds the solver's numbers; a transformer compares candidates with each other and with the current basis.

3 · Pick

The solver pivots on the top score. Dantzig takes bread: 3 pivots. Cake first: 2.

How it learns
Imitate a classic rule, or A*
Reinforcement learning: −1 per pivot
Search as a teacher (like AlphaZero): in training, try pivots ahead in the solver and teach the network the best one
The early learned offline policy (IQL) already ties steepest edge on the 40 × 40 LP.

Takeaways

The best plan sits at a corner (or on a tied edge or face, whose corners are all best too).
Shadow prices are dual variables: adding up the tight constraints with them proves a plan optimal.
Reduced costs are dual slacks: a negative one says the dual doesn't work yet, and which way to move.
A pivot rule is actually just a policy that we can decide. The 'best' one can vary problem to problem, potentially creating or removing exponential amounts of work.

Thank you! Questions?
[email protected] · danirip.github.io