sci.op-research

In one of the project I worked few months back, I used column
generation technique to solve LP. The problem was very similar to
classic cutting stock problem. The decision variables are binary and
they represent a pattern. Objective is to minimize total cost of
patterns, subject to cover constraints.

Incident matrix is defined as :
Aij = if row i is part of pattern j then 1.0, else 0.0
Let I = set of all rows.

To solve actual/original LP, I start with no patterns, only slack
variables (with high penalty), solve lp, get dual variables, generate
N best patterns (using reduced cost i.e. pricing out columns), add
them to the model and resolve lp. The loop is repeated till there are
no new patterns generated. At the end of the loop it is concluded that
original lp is optimally solved.

Reduced cost of pattern/column (say index j) = Cj - sum{i in I} Aij *
Wi
Cj = obj. func. coeff. of column
Wi = dual value of ith row

This worked fine for small problem size, however for large problem
size runtime was huge. At that time I was not sure if there is problem
with column generation logic.

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.

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. */

Reduced cost of pattern/column (say index j) = Cj - sum{i in I} Aij *
Wi (Same formula as above)

I think this will avoid adding some useless columns to the model and
therefore might improve total runtime. Does this make sense? Does
anyone else used similar technique against degeneracy during column
generation. I have not done much research on this issue (I should) but
my current understanding is based on degeneracy in simplex algorithm
explained on Page 97-98, "Linear Programming and Network Flows" By
Bazaraa et. al, Second Ed.

Of course I could just code above logic and see how it goes, but
additional thoughts will help.

Thanks