2
$\begingroup$

During the primal simplex algorithm, a non-basic variable must be chosen to enter the basis.

Many resources on the subject choose a variable based solely on its coefficient in the row of the tableau corresponding to the objective, whereas others calculate reduced costs before making a choice.

Why is there not consistency, and is one more popular in practice?

$\endgroup$
4
  • 6
    $\begingroup$ The coefficient of $x$ in the objective row of a simplex tableau is the reduced cost of $x.$ $\endgroup$
    – prubin
    Commented Sep 20, 2022 at 3:30
  • $\begingroup$ Is there multiple definitions for reduced cost? In this video, they calculate c_j - z_j where z_j is the dot product of c_B and the j-th column of the tableau. In this video they just choose based on the coefficient alone. $\endgroup$
    – Ram
    Commented Sep 20, 2022 at 3:51
  • $\begingroup$ Maybe the c_B and the coefficients of the basis variables in the objective row are two different things? $\endgroup$
    – Ram
    Commented Sep 20, 2022 at 3:54
  • $\begingroup$ I think I see where I went wrong. Thanks @prubin $\endgroup$
    – Ram
    Commented Sep 20, 2022 at 4:21

1 Answer 1

8
$\begingroup$

As long as you choose something with a negative reduced cost, the simplex algorithm "works". See https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec13.pdf for examples of ways you can choose the entering variable based on how much work you want to do. You can't just base it on the original cost: it has to be based on the reduced cost. Normally, this is the value in the cost row of the tableau if you are doing the full tableau method; if you are doing a more compact approach, then the reduced cost might need to be calculated (hence the value of the "first negative reduced cost" approach: you don't calculate all the reduced costs).

$\endgroup$
3
  • 7
    $\begingroup$ Welcome back! ${}$ $\endgroup$
    – TheSimpliFire
    Commented Sep 20, 2022 at 12:24
  • 1
    $\begingroup$ Thanks @Michael, I think the confusion came from seeing both the "compact" approach and the alternative, and not realizing the difference. $\endgroup$
    – Ram
    Commented Sep 20, 2022 at 22:28
  • $\begingroup$ Can it happen that in an intermediate simplex iteration we see more than one entering variables, however for one of them there is no leaving variable indicating unboundedness and for the other there is a leaving variable. $\endgroup$
    – Upstart
    Commented Feb 7, 2023 at 10:46

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.