Wolfe's Minimum-Norm-Point Method Generalizes the Simplex Method

Get email updates

Yann Disser, Nils Mosis

Disser and Mosis give a polynomial-time reduction from bounded, nondegenerate linear programs with nn variables and mm equality constraints to minimum-norm-point instances on n+1n+1 integer points in dimension m+1m+1. The reduction matches sequences of simplex pivots with sequences of Wolfe insertions. It transfers an exponential lower bound from Dantzig’s pivot rule to Wolfe’s original linopt rule.

What was already known

De Loera, Haddock and Rademacher showed that the minimum-norm insertion rule can take exponentially many iterations. They left open the worst case for Wolfe’s original linopt rule.

AI involvement AI-centered

Disser and Mosis report that the central link between Wolfe’s method and the simplex method emerged in their discussions with Claude Opus 5.5. They developed and rewrote the proofs with model assistance.

Importance Notable

The reduction transfers lower bounds for multiple simplex rules and settles the exponential worst case for linopt. It also yields an exponential example for the Lawson–Hanson algorithm.

Technical verification Formal (Lean 4 + human)

The authors report verifying all statements and proofs. They also report Lean 4 checking of the main reduction, the first four corollaries and their numbered supporting statements.

Formal checking

The authors report verifying all statements and proofs. They also report Lean 4 checking of the main reduction, the first four corollaries and their numbered supporting statements.

Checker
Yann Disser and Nils Mosis, with Lean 4 for the specified statements
Scope
Disser and Mosis give a polynomial-time reduction from bounded, nondegenerate linear programs with nn variables and mm equality constraints to minimum-norm-point instances on n+1n+1 integer points in dimension m+1m+1. The reduction matches sequences of simplex pivots with sequences of Wolfe insertions. It transfers an exponential lower bound from Dantzig’s pivot rule to Wolfe’s original linopt rule.
Basis
Reported by the linked checker

Human understanding Explained

Disser and Mosis explain why feasible simplex bases give Wolfe active sets and how the correspondence preserves the order of additions and removals.

Correction and publication history