Can the primal Simplex Method walk all optima in linear time?

It's typical that the Simplex Method implementation exits once it finds an optimum value. However, if I want to find all optima that exist at extreme points (not those that exist along a face), is it possible to walk through them in linear time? In polynomial time?

In my mind, it seems I would need to search through the $$n$$ decision variables to find one I could move into my basic solution without losing my optimum status. I would then have to back up my changes somehow so I could come back in what I picture to be a backtracking tree search. Am I picturing this correctly?

Can you recommend a source on this topic?

• Consider a problem with exponentially many extreme points and a constant objective function. Then all extreme points are optimal, and you need to enumerate exponentially many. So in general, no, you cannot enumerate all optima in polynomial time
– Sune
Commented Mar 5, 2022 at 6:57
• How do you define an LP with exponentially many extreme points? I was picturing that the worst case scenario would be the number of constraints squared, with each constraint intersecting all other constraints once. Commented Mar 5, 2022 at 12:23
• If that was the case, the simplex method would be polynomial if you use an anti cycling pivot strategy. That is not the case
– Sune
Commented Mar 5, 2022 at 12:26
• An example of a feasible set with an exponential number of vertices (as a function of the number of variables) is $\{ x\in \mathbb{R} ^n : 0\leq x_i\leq 1, i=1,2,...,n\}$
– Sune
Commented Mar 5, 2022 at 12:29

Unfortunately this is not the case for general LPs. To see this, consider an LP with exponentially many extreme points and a constant objective function. For this problem all extreme points are optimal, and you need to enumerate exponentially many.

A simple example of a feasible set with an exponential number of extreme points (as a function of the number of variables) is $$P=\{ x\in \mathbb{R}^n : 0\leq x_i\leq 1\}$$. The polytope $$P$$ has $$2^n$$ extreme points.

The feasible set of an LP problem is geometrically a polyhedron. Knowing the optimal value, say $$z^* = c^T x^*$$, over points in the feasible set, $$x \in P$$, thus provides you with a polyhedral description of its optimal face, $$\Omega$$, obtained simply by adding $$c^T x = z^*$$ to the constraint set. This means that you can use the answers in How to find all vertices of a polyhedron, for instance polymake, to enumerate all vertices of $$\Omega$$, thereby finding all optimal extreme point solutions of the LP problem. Nevertheless, as the number of vertices of a polyhedron (including $$\Omega$$) can be exponential in the dimension, see the answer by @Sune, no polynomial time algorithm can exist.

Adding to @Sune 's answer, some LPs can also be degenerate, which means that the objective acquires its optimal value along an edge rather than a vertex, which means there are infinite solutions. In other words, the optimal value still lies at a vertex, but there are infinitely many points that yield the same value. Enumerating those points would take infinite time.

• The question does specify extreme point solutions. As for degeneracy, a degenerate vertex can correspond to multiple bases, but only a finite number of them.
– prubin
Commented Mar 7, 2022 at 16:46
• @prubin I'm referring to the case where the objective contour is along the boundary of the polytope Commented Mar 9, 2022 at 14:56
• Right, but that still only includes a finite number of extreme points.
– prubin
Commented Mar 9, 2022 at 15:50
• Extreme points yes, but that's not what I wrote. I'm merely saying there are infinite solutions along that line - I thought it would be useful information for the OP in addition to the other answer. Commented Mar 9, 2022 at 18:55
• OK. What threw me was the last sentence ("Enumerating those points ..."), which sounded as though you were saying the answer to OP's question could take infinite time.
– prubin
Commented Mar 9, 2022 at 20:18