Originally posted by: RajaniK

Hi All, 

I am doing a job scheduling problem with column generation approach. I find duplicate columns being generated in my solution space. Can you please suggest how to avoid the duplicate columns. ( any script that I can check for the duplicate columns to avoid them)

Appreciate your support,

Regards,

Rajani K

The master problem is an LP (not MIP)? If so, I don't think duplication should be possible in theory. The subproblem optimizes what would be the reduced cost of the new column in the master problem, and if the column already exists, its reduced cost must be zero or have the "wrong" sign.

So (assuming this is an LP), you might want to check whether your comparisons of subproblem objective value to zero allow for sufficient rounding tolerance, and maybe see if your subproblem (or master problem) has a bad kappa value (condition number), indicating possible numerical instability.

Originally posted by: nhanquy

It is theoretically impossible to happens, however, I had coped with the same problem while resolving a MILP. I guess that your columns contains real number, so the pricing problem will be a bit confused in adding new columns (may be it would be not the same, just 10e-6 different in value) hence it could never stop. So try to search for some "Column Generation numerical stabilisation" on the litterature (http://pages.di.unipi.it/frangio/papers/StabCG.pdf).

Regards,

N-Q.Ng