column generation dual variables

Answered

Menglei Jia

• February 21, 2022 07:24
• Edited

I am trying to solve a MIP formulation using CG. It is hoped that each time adds a column into RMP, the dual variables will change and a new column can be obtained by solving PP. However, after adding a new column to the RMP, the dual variables are not changed. I am sure that the RMP has changed, and the unchanged dual variables do not meet the dual problem of the changed RMP. My question is why dual variables are not changed? Are there any approaches to diagnose it?

Related to

• Column Generation

0

• Official comment

  

  Jaromił Najman

  Gurobi Staff

  • February 24, 2025 12:46

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  Gurobi Staff

  • February 22, 2022 13:06

  You could use the write method to write an LP file before and after adding the new column and analyze what is going on. You should check whether the two model differ in the correct column and check the solution of the two models when you solve them outside of your CG framework. This should provide a good starting point to debug this issue.

  Best regards, 
  Jaromił

  0
• 

  Menglei Jia

  • February 23, 2022 06:32

  

  

  

  Thanks for your suggestion, Jaromił. Actually, I have written the formulations down and the column is correctly added into the RMP, and correspondingly, the optimal solution of the RMP is also changed, it seems everything is correctly going on except the dual variables. It is strange. However, recently I have some new findings: In my RMP, there is a constraint such that sum x=1, and when adding a column, I restricted it both about LB and UB (LB=0, UB=1). I tried to discard the UB restriction, then the problem is no longer exists. It seems that something is wrong with the bounds as mentioned here. 

  0
• 

  Jaromił Najman

  Gurobi Staff

  • February 24, 2022 08:31
  • Edited

  I tried to discard the UB restriction, then the problem is no longer exists. It seems that something is wrong with the bounds as mentioned here. 

  This behavior is explained by Tobias on the post you linked. It is not wrong behavior but an effect of using finite upper bounds. You don't need upper bounds of \(1\) for your \(x\) variables because each \(x\) cannot be larger than 1 anyway due to the equality constraint \(\sum x = 1\).

  Best regards, 
  Jaromił

  0
• 

  Menglei Jia

  • February 24, 2022 01:48
  • Edited

  

  

  

  Thank you for your further explanation, now I got it!

  0
• 

  Hamed Pouya

  • February 14, 2025 21:22

  

  

  Hi Jaromil,

  I have the same problem and in my case, there is no such constraint to harness x variables ($\sum x <= n) and I have to force the bounds. What is your suggestion in this case? CG generates repeated columns and dual values do not get updated even though the columns are correctly added and the obj value of RMP decreases.

  Thanks, HP

  0

Please sign in to leave a comment.