Column Generation - Large Dual Prices

Awaiting user input

Elisabeth

• July 27, 2023 12:11

Hi, 

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.

Related to

• Column Generation

1

• 

  David Torres Sanchez

  Gurobi Staff

  • August 01, 2023 08:33

  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. 1-set for each colour).

  Cheers, 
  David

  0

Please sign in to leave a comment.