sci.op-research

On Mar 7, 11:10 pm, vijay patil wrote:
> 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)
>

Correction:
if ( (ith column is in basis) && (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. */