sci.op-research

vijay patil wrote:

> As my understanding improves, now I fill that I should have considered
> possible issue of degeneracy. Specifically, before adding any new
> (generated) pattern/column, I should check if one or more variables
> current basis are at level 0.0. In other words, basis is degenerate.
> As I understand, in such case dual values of rows are only
> *theoretical* and actual improvement in obj. func. cannot be realized,
> as one or more basic variable is already at 0 level.

I'm not sure what you mean by "theoretical". If the primal solution is
degenerate, the dual solution is valid optimal solution for the dual
problem. It's just that the dual problem has multiple optima, and you
are only getting one of them.
>
> Now I think that I should have used following formula for reduced
> cost:
>
> Let Xi = Optimal value of ith variable, after solving LP during column
> generation.
> if (Xi == 0.0)
> Wi = 0.0; /* Do not consider dual cost of this row because ith
> variable is at level 0 */
> else
> Wi = Wi; /* No issues in this case. */

That seems inappropriate to me. First, it makes no sense, unless you
are assuming that Xi is basic in the i-th row. Second, if we assume
that Xi is basic in row i, that does not "implicate" the i-th constraint
in any meaningful way. Bear in mind that the i-th row of the _final_
tableau has a zero right-hand side, but that row is the result of a
number of pivots and thus represents a linear combination of the
original constraints, not just the i-th original constraint (whereas the
i-th shadow price does correspond to the i-th original constraint).

Are you observing any substantial number of iterations where you add a
column and the primal solution does not change?

/Paul