Column Generation  Large Dual Prices
Awaiting user inputHi,
I'm trying to solve a graph colouring problem with CG, in which I assign the sets to specific colours. This is a minimisation problem, of which the objective function value cannot be negative. However, when I retrieve the dual prices, the dual prices are much larger than my current objective value. Therefore, the pricing problem (consisting of a cost part and a part that is multiplied by the dual prices) only focusses on the dual prices and the CG algorithm is stuck in an infinite loop (because the cost component is not improved, but there are sets with negative RCs that can be added to the MP). I tried every debug trick, but nothing seems to work.

Hi Elisabeth,
Is this for the first iteration?
You may want to try to create and set the dummy variables to have a very large cost. Dummy variables in this context typically represent a feasible yet really poor starting solution (e.g. 1set for each colour).Cheers,
David0
Please sign in to leave a comment.
Comments
1 comment