0

Let's assume we want to maximize $x_1+x_2$, satisfying $x_1+x_2 \leq 1, x_1 \geq 0, x_2 \geq 0$.

Simplex algorithm is going to return $\vec{x}=(0, 1)$ or $\vec{x} =(1, 0)$.

But is there some reason why an LP solver couldn't return $\vec{x}=(0.5, 0.5)$? I assume that it is convenient to return just the solutions at the vertices of the polytope, because that allows us to enumerate all the "canonical" solutions. But is it just a convention? Or is it part of the definition?

Tortar
  • 3,980
  • 1
    It could. Some interior-point solvers will tend to converge to the analytic center of the optimal face, in your case the midpoint. – Michal Adamaszek Aug 14 '20 at 10:38

3 Answers3

1

The optimal solution of that problem is $(x_1^*,x_2^*)=(x_1, 1-x_1)$, where $x_1,x_2 \in [0,1 ]$. That´s true. But the simplex algorithm just inspect vertices like $(0,1)$ and $(1,0)$. This solutions are optimal since they are subset of the general optimal solution. The simplex algorithm omits the solutions in between. One way to see that that the solution is a straight line is to observe the ratios of the coefficients are equal.

Objective function $z=\color{red}1x_1+\color{red}1x_2\Rightarrow \textrm{ratio}=\frac{1}{1}=1$

Constraint $\color{red}1x_1+\color{red}1x_2\leq 1\Rightarrow \textrm{ratio}=\frac{1}{1}=1$

A graphical solution shows that the (optimal) objective function lies on the constraint.enter image description here

callculus42
  • 30,550
0

There's a theorem which says that at least one maximizing solution is at a vertex, and that there is a finite number of them.

So, if you need only one maximizing tuple $(x_1^*,x_2^*,...,x_n^*) $ and not all the solutions, it's convenient to search the maximum on these points when programming a LP solver (however, there are also other methods).

Tortar
  • 3,980
0

The term "LP solver" is very general.

For simplex algorithm, by the design of the algortihm, it starts from a vertex and travel from vertex to vertex, hence it only terminates at a vertex. It does so due to the result that if there is an optimal solution, there is one at the vertex.

We can design an algorithm that returns a point that is not a vertex if there is one. We should not think the simplex algorithm as the only "LP solver".

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149