How to accurately calculate reduced cost when generating one column in column generation?
AnsweredHello good people,
I am working on a variant of VRP & solving it using Column Generation. The objective function of the pricing problem is my reduced cost (RC) of each route/sequence.
My initial solution has 8 feasible routes.
1. If I generate 8 columns using the pricing problem, RC calculation is accurate, & getting optimal solutions of the RMP.
2. But, when trying generating one column at a time, cost of sequence (based on newly generated one column) are much higher. My manager is expecting to this “one column” approach to be implemented for the final product. The cost of sequences based on generating one column approach is given below. I think the problem is the values of dual variable of the RMP is not preserved during each iteration. The same RC & dual value calculation works fine when we generate multiple columns at a time. Any tips?
> RC_s = c_s - \sum (pi_i. z_i )
Note: I am not sure if I explained my problem in this post properly/ how much details is needed for a reader.
C_s [310.0, 1620.0, 410.0, 1090.0, 360.0, 1030.0, 1830.0, 2810.0, 3930, 3480, 2090, 5160, 4470, 5090, 5620, 3870]
0
-
Hi Tanmoy,
The dual values will change as adding columns will change the master problem in every iteration. This will allow you to generate more or stop if no column with a negative reduced cost can be produced. If this process doesn't stop, you may have a bug. It is worth experimenting with adding columns in batches or one by one.
Cheers,
David0
Please sign in to leave a comment.
Comments
1 comment