6
$\begingroup$

Does anybody has idea how to solve this problem ?

"Show that in Phase I of the simplex method, if an articial variable becomes nonbasic, it need never again become basic. Thus, when an articial variable becomes nonbasic, its column can be eliminated from the tableau"

$\endgroup$
  • 2
    $\begingroup$ FYI, This is Question 3.24 from "Introduction to Linear Optimization" by Dmitri Bertsimas & John Tsitsiklis. $\endgroup$ – Michael Grant Dec 4 '14 at 16:58
  • $\begingroup$ @BCLC, Let's see if we've helped here. $\endgroup$ – Michael Grant Dec 4 '14 at 20:33
  • $\begingroup$ It is also question 20 from Chapter 3 of Luenberger & Ye's "Linear and Nonlinear Optimization" (3rd edition) $\endgroup$ – Jay Oct 13 '15 at 19:44
  • $\begingroup$ @Jay do you know how to answer this? In the simplex algorithm, when might some a variable leave a basis? $\endgroup$ – BCLC May 20 '16 at 19:19
4
+200
$\begingroup$

As mentioned above, this is from the Bertsimas and Tsitsiklis, and the Phase I approach they are referring to is in Section 3.5. The standard form LP they use is \begin{array}{ll} \text{minimize} & c^T x \\ & A x = b \\ & x \geq 0 \end{array} They assume that $b\geq 0$; if this is not the case, negate the corresponding rows to make it so. (And for simplicity, let's assume $b$ has at least one nonzero value.) The corresponding Phase I problem looks like this: \begin{array}{ll} \text{minimize} & \textstyle\sum_i y_i \\ & A x + y = b \\ & x \geq 0, y \geq 0 \end{array} Now you see why $b\geq 0$ is important: $(x,y)=(0,b)$ constitutes a trivial feasible solution, so that's your starting point for the Phase I method, with an initial objective of $\sum_i b_i>0$. If the optimal value of this Phase I model is zero, then original model is feasible; otherwise, the original model is infeasible.

It is important to read the statement carefully. It is not claiming that an artificial variable will never re-enter the basis if you leave it in the tableau. In fact, it can. If you have the book, look at Example 3.8. In one of the steps, one of the nonbasic artificial variables has a negative reduced cost, making it an entirely valid candidate for selection, depending on the pivoting rule you use. (The example chose a different pivot, though.)

The statement, therefore, is not that it will never re-enter the basis. Rather, the statement is saying that it does not need to re-enter the basis. What we wish to show is that eliminating one of these variables from the tableau does not prevent the simplex method from terminating properly.

To see why this is the case, consider this "restarting" approach to solving the Phase I model:

  1. Initialize: basis $\mathcal{B}=(y_1,y_2,\dots,y_n)$, $(x,y)=(\vec{0},\vec{1})$.
  2. Begin the simplex algorithm simplex with the current basis $\mathcal{B}$ and current $(x,y)$.
  3. If the algorithm terminates before an artificial variable is eliminated:
    • If the cost is zero, STOP. The problem is feasible, but extra steps need to be taken to drive the remaining artificial variables out of the basis. See Section 3.5 for details.
    • If the cost is positive, STOP. the problem is infeasible.
  4. As soon as an artificial variable is removed from the basis, stop the simplex method, and obtain the current basis $\mathcal{B}$ and current point $(x,y)$. (The first time through, this will happen on the very first pivot. In subsequent iterations, it might take longer.)
  5. Remove the newly nonbasic artificial variable from the problem. If no basic artificial variables remain, STOP. Your problem is feasible and you have a basic feasible solution.
  6. Repeat steps 2-6.

The key to the success of this approach is noting that, after removing a nonbasic artificial variable in Step 5, you're still left with a valid pseudo-Phase I model and a feasible point for that model. The model still has an optimal value of $0$ if the model is feasible. It's also important to note that objective value reached in Step 4 is going to be the initial objective value at Step 2. So we do not lose progress with our restarts.

In fact, one way to look at it is this: we're not really restarting the simplex algorithm per se. Rather, we are just choosing to recompute the inverse basis matrix $B^{-1}$ from scratch every time an artificial variable exits the basis. Still, by expressing the approach in this way, it is hopefully easier to see why the elimination of nonbasic artificial variables does not prevent the algorithm from terminating.

Once you are satisfied with this, you don't need to actually restart at all. You will get exactly the same sequence of simplex pivots if you simply include in your pivot rule the clause: never choose a nonbasic artificial variable.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the bounty BCLC! Since I hadn't received any votes I was concerned that it was considered incomplete. $\endgroup$ – Michael Grant Dec 10 '14 at 13:58
  • $\begingroup$ Oh lol just saw this. Ayt. Hahaha $\endgroup$ – BCLC Apr 17 '15 at 17:43
  • $\begingroup$ Michael Grant, do you know how to answer this? In the simplex algorithm, when might some a variable leave a basis? $\endgroup$ – BCLC May 20 '16 at 19:19
1
$\begingroup$

I am not sure whether I answer your question or not:

In Phase I the objective function is $$\min s_1+s_2+\ldots+s_m$$ where $s_i$ for $1\le i \le m$ are the artificial slack variables of the original problem. But one constraint (of the Phase I LP) is that $$s_i\ge 0, \qquad \text{ for } i=1,2, \ldots, m$$ and therefore if one of these variables becomes $0$ it is "as good as it gets" (for that variable and the objective of the LP of Phase I). This gives the reason that a variable which leaves the basis does not enter the basis again:

  1. Since you start Phase I with each of these variables having a positive value, making one of them equal to $0$, strictly improves the value of the objective function. But this means that this variable has left the basis.
  2. Now, as long as there is a positive slack variable you will do strictly better taking this one out of the basis instead of bringing a variable with value $0$ back in (cycling).
  3. When all of these variable are equal to $0$ - if possible - then you can finish with Phase I.

A good book which covers (more than) the basics of linear optimization and provides intuitive explanation for most subjects, is that of Bertsimas and Tsitsiklis (1997), the biggest part of which (including the description of Phase I, p. 111) can be found online here.

$\endgroup$
  • $\begingroup$ Actually, in Phase 1, the objective function is the sum of the artificial slack variables, not the original slack variables. $\endgroup$ – Michael Grant Dec 4 '14 at 17:02
  • $\begingroup$ @MichaelGrant Yes, of course, thanks for the correction. Still I am not sure whether I answered OP's question. $\endgroup$ – Jimmy R. Dec 4 '14 at 17:23
  • $\begingroup$ Note that it can occur that a non-basic artificial variable has a reduced cost that is negative. This means that bringing it back into the basis can improve the objective, so unless the pivot rule explicitly disallows it, it can be selected again. This is possible because artificial variables are coupled via the equality constraints. So reducing one artificial variable by, say, 1, ends up corresponding to increasing another by, say, 1/2. That is a trade worth making. $\endgroup$ – Michael Grant Dec 7 '14 at 19:38
  • $\begingroup$ JImmy R., do you know how to answer this? In the simplex algorithm, when might some a variable leave a basis? $\endgroup$ – BCLC May 20 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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