7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ 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 $\endgroup$
    – Sune
    Commented Mar 5, 2022 at 6:57
  • $\begingroup$ 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. $\endgroup$
    – Brannon
    Commented Mar 5, 2022 at 12:23
  • $\begingroup$ If that was the case, the simplex method would be polynomial if you use an anti cycling pivot strategy. That is not the case $\endgroup$
    – Sune
    Commented Mar 5, 2022 at 12:26
  • 3
    $\begingroup$ 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\}$ $\endgroup$
    – Sune
    Commented Mar 5, 2022 at 12:29

3 Answers 3

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Mar 7, 2022 at 16:46
  • $\begingroup$ @prubin I'm referring to the case where the objective contour is along the boundary of the polytope $\endgroup$
    – Nikos Kazazakis
    Commented Mar 9, 2022 at 14:56
  • 1
    $\begingroup$ Right, but that still only includes a finite number of extreme points. $\endgroup$
    – prubin ♦
    Commented Mar 9, 2022 at 15:50
  • $\begingroup$ 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. $\endgroup$
    – Nikos Kazazakis
    Commented Mar 9, 2022 at 18:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Mar 9, 2022 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.