2
$\begingroup$

When I used Column Generation, I found a column with reduced cost < 0, and added it to the Restricted Master Problem.

Must the newly added column be used in the solution of RMP at once? If not, then why this reduced cost does not work to the objective of RMP?

e.g. Suppose $z_1, z_2, z_3 $ are initial columns, we have a RMP below,
$P_1:\min {3 z_1 + 4 z_2 + 9 z_3} $
s.t.
Constraint a: $z_1 + z_2 + z_3 = 2$
Constraint b: $z_1 + 2 z_3 = 1$
Constraint c: $z_2 + 0.5 z_3 = 1$
If we solve this model directly, the objective value should be 7, and the dual values should be $\pi_a = -2/3, \pi_b = 11/3, \pi_c = 14/3$.
Then if we find a new column $z_4$, with the cost equals to 3.5
As the reduced cost should be 3.5 - 11/3 - 14/3 + 2/3 < 0, so it will be added to RMP.
$P_2:\min {3 z_1 + 4 z_2 + 9 z_3 + 3.5 z_4} $
s.t.
Constraint a: $z_1 + z_2 + z_3 + z_4 = 2$
Constraint b: $z_1 + 2 z_3 + z_4 = 1$
Constraint c: $z_2 + 0.5 z_3 + z_4 = 1$
when $z_4$ is added, it cannot be used instantly. The newly solution will be $z_1 = 1, z_2 = 1$, the Obj value of RMP not changed and the newly column $z_4$ not used.
While if we changed the equal signs in the constraint to Greater than or equal signs.
$P_3:\min {3 z_1 + 4 z_2 + 9 z_3} $
s.t.
Constraint a: $z_1 + z_2 + z_3 >= 2$
Constraint b: $z_1 + 2 z_3 >= 1$
Constraint c: $z_2 + 0.5 z_3 >= 1$
and
$P_4:\min {3 z_1 + 4 z_2 + 9 z_3 + 3.5 z_4} $
s.t.
Constraint a: $z_1 + z_2 + z_3 + z_4 >= 2$
Constraint b: $z_1 + 2 z_3 + z_4 >= 1$
Constraint c: $z_2 + 0.5 z_3 + z_4 >= 1$
Now the newly column $z_4$ will be used and make the new obj becomes 6.5.

My question becomes, In $P_1 \& P_2$, do the newly column $z_4$ enter the basis? If do, why the value of $z_4$ if 0, is this situation right?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

I assume that you are minimizing. If you only add one column at a time, the new column should immediately enter the basis. If you add multiple columns with negative reduced costs before doing more pivots in the RMP, it is possible that one of the new columns might not make it into the basis due to some of the other new columns.

One caveat has to do with what you mean by "used in the solution". If you add a single new column, update and get a degenerate solution, it is possible that the new column might be in the basis but with value 0 (so not obviously basic if you just look at the variable values in the new solution).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you! So, although in the new solution, the value of the new column be 0, it is also possible this column is in the basis. As there are a lot of columns that the value might be 0, how can I identify which is in the basis, and which is not? $\endgroup$
    – West Wind
    Commented Apr 12, 2023 at 3:05
  • $\begingroup$ P.s. I added a simple possible example in the question description. $\endgroup$
    – West Wind
    Commented Apr 12, 2023 at 3:49
  • 1
    $\begingroup$ What would happen in you example is hard to say, and somewhat dependent on how you are solving the RMP. You have four constraints but only three variables. It is possible (I would say likely) that the presolve function in your solver would eliminate one constraint as redundant. Your constraint "sum" is implied by a and c, so it might be eliminated, after which all three variables would be in the basis. On the other hand, the solver might add artificial variables to the constraints (giving you seven variables in total), and then create a basis from four of them, which might include $z_3.$ $\endgroup$
    – prubin ♦
    Commented Apr 12, 2023 at 15:31
  • 1
    $\begingroup$ As far as determining who is in the basis, that is very much dependent on what solver you are using. $\endgroup$
    – prubin ♦
    Commented Apr 12, 2023 at 15:31
  • 1
    $\begingroup$ In P2, $z_4$ is indeed basic in the optimal solution but equal to 0 because the optimal corner point is degenerate. As to why it is degenerate, and why specifically it is $z_4$ and not one of the other basic variables that is 0, that has to do with the constraint coefficients (1, 1, 1) for $z_4.$ $\endgroup$
    – prubin ♦
    Commented Apr 13, 2023 at 18:59

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.