7

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?

Brannon
  • 900
  • 2
  • 12
  • 7
    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 Mar 05 '22 at 06: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. – Brannon Mar 05 '22 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 Mar 05 '22 at 12:26
  • 3
    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 Mar 05 '22 at 12:29

3 Answers3

12

Converting previous comments into an answer:

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.

Sune
  • 6,457
  • 2
  • 17
  • 31
4

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.

Henrik Alsing Friberg
  • 1,467
  • 7
  • 13
2

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.

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • 4
    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 Mar 07 '22 at 16:46
  • @prubin I'm referring to the case where the objective contour is along the boundary of the polytope – Nikos Kazazakis Mar 09 '22 at 14:56
  • 1
    Right, but that still only includes a finite number of extreme points. – prubin Mar 09 '22 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. – Nikos Kazazakis Mar 09 '22 at 18:55
  • 1
    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 Mar 09 '22 at 20:18