6

For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form.

Since the Simplex algorithm iterates from extreme point to extreme point (corresponding to the fact that Simplex iterates from BFS to BFS when the LP is in SEF), how does the Simplex algorithm geometrically work when the feasible region is a polyhedron that cannot be realized in SEF (e.g. a halfspace)? Suppose we have an LP for which the feasible region has no extreme points. Then we can write an 'equivalent' LP which is in SEF and run the Simplex algorithm on it instead. But there are extreme points for this new polyhedron, whereas there are none for the original, by assumption. I originally thought that the extreme points of one LP bijectively corresponded to extreme points of the other, but this is evidently not the case.

So when exactly do the extreme points of the SEF version of an LP correspond bijectively to extreme points of the original? And further, when such a bijection does not hold, how are we supposed to geometrically interpret what the Simplex algorithm is doing in terms of the original LP?

t42d
  • 201
  • 1
  • 1

2 Answers2

10

the Simplex algorithm iterates from extreme point to extreme point

Technically, no. The simplex algorithm iterates from basis to basis. It just happens that feasible basic solutions correspond to extreme points. (for instance, the dual simplex iterates through dual-feasible basic solutions, which are not extreme points of the primal-feasible region).

Consider an LP in standard form, which writes \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align} That LP's feasible region is always polyhedral. If it has no extreme points, then it is either empty (and there are no basic feasible solutions), or an affine sub-space of $\mathbb{R}^{n}$. Now, the latter case cannot happen, because no affine sub-space can be a subset of $\mathbb{R}_{+}^{n}$.

Now, coming back to (what I think is) your original question: given an original polyhedron and a SEF representation for it, does that representation has extreme points, and do they correspond to extreme points of the original polyhderon? The answer is: yes, the SEF will have extreme points, and no, they may not always correspond to extreme points of your original polyhedron.

Here is a simple example: take $\mathcal{P} = \{x \in \mathbb{R}\}$, which is a 1-dimensional polyhedron. Its formulation has one free variable and no constraints.

To build a SEF representation, replace $x$ by $x^{+} - x^{-}$ with $x^{\pm} \geq 0$. Now, $(0, 0)$ is an extreme point of that SEF, which corresponds to $x=0$, which is not an extreme point of $\mathcal{P}$.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
mtanneau
  • 4,123
  • 11
  • 24
  • 1
    Thank you for the reply, and yes, this is the first part of my question. But for example, if we have $Ax\leq b$ and $x\geq 0$ as the constraints, then we can convert to SEF form by adding slack variables, so we have $Ax + s = b$ and $(x, s)\geq 0$ ($s$ is the vector of slack variables). And in this case, $x$ is extreme for the original constraints if and only if $(x, s)$ is extreme for the SEF constraints. So why is there a correspondence in this example, whereas in your example there is not? Is it characterized by the existence of free variables? – t42d Aug 18 '20 at 17:59
1

Not sure I fully understand your question, but I guess your confusion stems from the assumption that a basic solution is an "extreme point". A basic (not necessarily primal or dual feasible) solution is just the intersection of number of rows constraints (some of which might be bounds). It is possible that a problem does not have a primal or dual feasible solution in as a result is either infeasible or unbounded. Textbook simplex algorithms sometimes skip over the fact that some form of phase 1 approach is needed to establish a BFS to actually start the algorithm. It is possible that a primal phase 1 finds the problem primal infeasible and its also possible that a dual phase 1 finds the problem unbounded.

Update: The answer by mtanneau is probably saying all there is to say, for a single constraint with free variables the same applies. I just want to add that simplex implementations work with free variables directly and do not convert them to two variables bounded by 0. But the same holds, the algorithm iterates over basic solutions and the convention is made that non-basic free variables take the value 0. Also note that for bounded polyhedra, basic solutions correspond to extreme points.

Philipp Christophel
  • 3,188
  • 8
  • 24
  • Thank you for your reply. One thing I didn’t appreciate is that there are (apparently) different versions of the Simplex algorithm. For me, I am not doing anything involving both a primal and dual. It is just an LP in SEF form, and then Simplex does a basis exchange and puts the LP in canonical form for the new basis and iterates. So I don’t think my issue is regarding feasibility of the LP. – t42d Aug 17 '20 at 22:46
  • Say instead we have a single half space as the feasible region. Then there are no extreme points. But on the other hand, there is supposed to be a basic feasible solution when this is put in SEF form, right? So the SEF form has an extreme point whereas the original version did not. So is there some significance of the extreme point in the context of the original half space? – t42d Aug 17 '20 at 22:49
  • I think I understand your problem now. You want to know what the basic solution to a problem with a single constraint and free variables is. Since graphically speaking there are no intersections of constraints, how can there be an extreme point, i.e. basic feasible solution? I will have to think about that and will update my answer when I have something. – Philipp Christophel Aug 18 '20 at 09:45
  • Yes, this is essentially my question. It doesn't $\textit{have}$ to be a single constraint and free variable, although this is a good instance. In general, I am wondering when the extreme points of the SEF version of an LP correspond to the extreme points of the original LP. It is clear that such a correspondence does not hold in the example of the single half space with free variables, because there are $\textit{no}$ extreme points in that original LP at all. But I don't know how we can characterize the situations when extreme points do correspond to extreme points of the SEF version. – t42d Aug 18 '20 at 17:50
  • My understanding is that this holds for bounded polyhedra (polytopes), but I don't have a rigorous proof for that. – Philipp Christophel Aug 19 '20 at 09:30
  • Yes, after thinking about it a bit more, I am able to show that a bijective correspondence between extreme points will exist if the original polyhedron is in the positive orthant (i.e. all the original variables are non-negative). Here, it especially easy to convert to SEF form by just adding non-negative slack variables. In particular this guarantees the initial polyhedron will have an extreme point. So I am still wondering more generally if it is true that a bijective correspondence of extreme points will occur if and only if the original polyhedron has an extreme point. – t42d Aug 19 '20 at 16:38