Column Generation - Large Dual Prices

ユーザーの入力を待っています。

Elisabeth

2023年07月27日 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.

関連

• Column Generation

1

• 

  David Torres Sanchez

  • Gurobi Staff

  2023年08月01日 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

サインインしてコメントを残してください。