1
$\begingroup$

I am studying linear optimization from the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis and came up with the following question:

If a standard form problem $$ \begin{align} \min&\quad c'x \\ \text{s.t.}&\quad Ax=b \\ &\quad x\ge 0 \end{align} $$ has exactly two optimal basic feasible solutions $x^*$ and $x^{**}$, must they be adjacent?

Here "adjacent" means that the bases of $x^*$ and $x^{**}$ differ by one element.

Intuitively this is true. If $x^*$ and $x^{**}$ were not adjacent, then perhaps there would be a path from $x^*$ and $x^{**}$ in which all of the intermediate BFS are optimal, which is a contradiction. However, I do not know how to convert this idea to a rigorous proof.

I thought about applying the simplex method with $x^*$ as the initial point and letting it lead to $x^{**}$, but clearly this doesn't work, because $x^*$ is already optimal and the simplex method may terminate directly (if the reduced costs associated with $x^*$ are nonnegative). Any help will be appreciated.

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Hint:

Consider the feasible region of this graph: enter image description here

Then, consider the objective function of the model (the green line) on this feasible region: enter image description here

Then, consider this in three dimensions: enter image description here

Where the optimal region is a triangle with each optimal solution $x^*$ having two adjacent $x^{**}$ and $x^{***}$.

Then, in a fourth dimension, there would exists four equally optimal points and so on with higher dimensions. Think about how the Simplex method would handle these, and how this works intuitively with the objective function.

With each additional dimension we add, we're going from a line, to a triangle, to a tetrahedron, and so on.

In other words, a one simplex, a two simplex, a three simplex, a four simplex, and so on.

$\endgroup$
11
  • 2
    $\begingroup$ in order for an alternative optimal solution to exist, the reduced cost coefficient of a non-basic variable must be equal to zero in the optimal simplex tableau, and if we pivot that zero reduced cost of that non-basic variable we'll find the other point. there'll never exist an optimal adjacent point that doesn't have a zero reduced cost $\endgroup$
    – user1098096
    Oct 29, 2022 at 18:22
  • 1
    $\begingroup$ what I'm hinting at above is that the simplex tableau will be littered with multiple zero reduced cost coefficients of the amount of dimension $n -1$ which will correlate to the amount of multiple optimal extreme points in the model which will be the size of the dimension $n$, and each additional point will always be adjacent to all the other optimal extreme points $\endgroup$
    – user1098096
    Oct 29, 2022 at 18:28
  • 1
    $\begingroup$ if it's adjacent and optimal, it mustn't change the objective function value, but it must only change the values of the RHS of the other basic variables the entering non-basic variables isn't replacing, which would be the positive distance we're looking for, and this is measured by the amount of change need to make the row of that entering variable basic for that variable, and the amount of change needed to reduce the other rows, excluding the objective row, to allow that entering variable to be basic $\endgroup$
    – user1098096
    Oct 29, 2022 at 18:46
  • 1
    $\begingroup$ the amount you move for the objective function is always zero, but amount you move on the right hand side of the tableau isn't zero, and is dependent on the new RHS produced by the new entering basic variable. which is what you're going to need to prove they're adjacent, because if they aren't you can't undo that pivot action to get the other point, or there wouldn't be the a non-basic variable of that other point for that pivot $\endgroup$
    – user1098096
    Oct 29, 2022 at 18:56
  • 1
    $\begingroup$ degeneracy isn't adjacency, as it exists on the same point $\endgroup$
    – user1098096
    Oct 29, 2022 at 19:00
0
$\begingroup$

Here is a simple solution. Denote the rest of the basic feasible solutions by $z_1,...,z_k$. Take $\epsilon>0$ small and perturb $c$ by $\epsilon(x^*-x^{**})$, so that the new cost vector $d=c+\epsilon(x^*-x^{**})$ satisfies $d'x^{**}<d'x^*<d'z_i$ for $i=1,...,k$. Now run the simplex method on the new linear program with $x^*$ as the initial point. It must move to an adjacent vertex with a lower cost, which can only be $x^{**}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .