Source-linked AI summary
Escaping Degeneracy by Following Shadow Edges
Alexander E. Black, Sean Kafer, Laura Sanità
TL;DR
Degenerate Simplex pivots can change the basis without changing the vertex, complicating efforts to bound pivot counts. The paper shows how shadow pivot rules can reach a desired edge-direction with linearly many degenerate pivots, and obtains a polynomial pivot bound for 0/1-LPs.
Problem
Degenerate pivots can leave the current vertex unchanged, and a polynomial-time Simplex pivot rule remains unproven.
Source: §1 · p. 2Method
The paper uses shadow pivot rules to follow a specified shadow edge from a compatible basis through a sequence of degenerate pivots.
Source: §3 · pp. 4–5Results
Takeaways & Limitations
For 0/1-LPs, the Shifting Shadow pivot-rule reaches an optimal solution in a number of pivots bounded by a polynomial depending only on n.
Source: §4 · p. 9The approach relies on knowing the shadow edge-direction, whose computation for general LPs is no easier than solving the LP itself.
Source: §4 · p. 9
Abstract
from arXiv · showhide
The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.
1 Introduction
The paper addresses the difficulty of bounding Simplex pivot counts when degeneracy must be handled without losing control of the path. It gives shadow-pivot results that bound degenerate pivots while preserving a desired edge direction, including a polynomial bound for a modified rule.
1 Introduction
- Degeneracy matters because a pivot can change the basis while leaving the vertex unchanged, so pivot counts need not track progress between vertices.Non-degenerate pivots trace a monotone path on the polyhedron's 1-skeleton.Source: §1 · p. 2
- A polynomial-time Simplex rule remains open, as does the polynomial Hirsch conjecture's guarantee of polynomial-length paths between polyhedron vertices.Existing ellipsoid and interior-point algorithms are weakly polynomial: their elementary-operation counts depend on LP coefficient size.Source: §1 · pp. 1–2
- Shadow pivot rules can reach a desired shadow edge-direction from a compatible basis using linearly many degenerate pivots, with the sequence computable in strongly polynomial time.Every edge-direction is a shadow edge-direction for some shadow.Source: §1 · p. 2
- Earlier work could escape degeneracy in linearly many pivots given an improving feasible direction, but could not control which non-degenerate pivot followed.The paper's shadow-pivot result adds control over that next edge.Source: §1 · p. 2
- For 0/1-LPs, prior rules could follow desired paths with polynomially many non-degenerate steps, but had not bounded the number of degenerate pivots.The paper identifies this as an unresolved issue in that work.Source: §1 · p. 2
- A modified pivot rule has polynomially many non-degenerate pivots and at most linearly many degenerate pivots at each vertex.The paper presents this as an answer for one of the pivot rules considered in prior work.Source: §1 · p. 3
2 Preliminaries
The preliminaries set the LP assumptions and define bases, feasible cones, and pivot directions. They then formalize shadows and the edge and pivot directions used by the paper's shadow rules.
2 Preliminaries
- The paper studies maximizing a linear objective over a polytope, assuming full-rank equality constraints and a generic objective.The equality assumption is made without loss of generality; a generic objective can be obtained by a small perturbation.Source: §2 · p. 3
- A feasible basis is a set of inequality indices defining a feasible vertex, while the feasible cone at that vertex contains directions that remain feasible for some positive step.The paper's basis convention uses constraint indices rather than the variable-index perspective common in Simplex descriptions.Source: §2 · p. 3
- A basis's basic cone encodes its available pivot-directions; a pivot is degenerate when the maximum feasible step is zero.A pivot-direction determines the leaving index, while degeneracy can leave multiple entering-index choices.Source: §2 · pp. 3–4
- A shadow is the two-dimensional projection of the feasible polytope onto the coordinates given by an auxiliary vector and the objective.A shadow edge at a vertex is the edge-direction maximizing objective increase there.Source: §2 · p. 4
- On a shadow, the shadow pivot-direction maximizes the objective-to-shadow-coordinate ratio among objective-improving pivot-directions.The shadow definition includes a condition excluding certain degenerate situations at an initial basis.Source: §2 · p. 4
3 Degenerate pivots can follow shadow edges quickly
For a basis on the (v, c)-shadow, knowing the target shadow edge-direction lets a strongly polynomial sequence of degenerate pivots make that direction available, with a linear pivot bound.
3 Degenerate pivots can follow shadow edges quickly
- Theorem 4 finds a degenerate pivot sequence making sx′ available, of length |B∗∩R(x′)| − |B∩R(x′)| ≤ n − rank(A) − 1 − |B∩R(x′)|, in strongly polynomial time.The starting basis must be on the (v, c)-shadow, and sx′ must be given.Source: §3 · p. 5
- For the non-c-maximal cones covered by Lemma 5, being on the (v, c)-shadow is equivalent to every c-improving direction having positive v-direction.Source: §3 · p. 5
- At a non-c-maximal basis on the shadow, the shadow pivot direction is an LP-optimal direction, and pivoting along it keeps the next basis on the shadow.Source: §3 · p. 5
- Face-restricted LPs let the construction add constraints tight at sx′ without later removing them, while retaining a shadow basis for subsequent steps.Each resulting pivot increases the number of basis constraints in R(x′) by one.Source: §3 · pp. 6–7
4 Degeneracy via shadow edges in 0/1-LPs
For 0/1-LPs, the authors adapt a shadow-edge pivot strategy so degenerate moves remain Simplex pivots, obtaining a polynomial total pivot bound. Their coordinate-basis construction also answers an open question about reaching the steepest edge from that basis with a linear number of degenerate Simplex pivots.
4 Degeneracy via shadow edges in 0/1-LPs
- The coordinate basis restores access to the (v, c)-shadow, since intermediate shadow pivots in face-restrictions may take visited bases off P's shadow.The coordinate basis at the vertex is on the (v, c)-shadow.Source: §4 · pp. 7–8
- For any initial basis, Shifting Shadow reaches an optimal solution on a 0/1-LP using a number of pivots bounded by a polynomial in n.The proof bounds the initial degenerate sequence and the subsequent non-degenerate steps by quantities depending only on n.Source: §4 · p. 9
- From the first visited vertex, the rule reaches its coordinate basis in at most n degenerate pivots, then uses at most n Simplex pivots before taking the steepest shadow edge.The chosen shadow edge-direction is the steepest edge-direction at that vertex.Source: §4 · pp. 8–9
- The method presumes knowledge of the shadow edge-direction; computing it is strongly polynomial for 0/1-LPs but, for general LPs, is no easier than solving the LP.The authors note that standard combinatorial algorithms can provide the relevant direction for some polytope classes, including matching and flows.Source: §4 · p. 9
4.1 Necessity of the Coordinate Basis
- A non-coordinate basis can leave only one improving move, with gain ε, even though the steepest edge gains 1 + ε and cannot be reached by Simplex pivots.The example shows why access to the steepest edge depends on the basis representing the current vertex.Source: §4.1 · p. 10
- The counterexample uses a redundant inequality, which cannot generally be ignored because identifying redundant inequalities is no easier than solving the LP.Source: §4.1 · p. 10