Column generation when number of rows depend on number of columns

回答済み

Marco Correia

2023年10月27日 06:42

• 
• 
• 

Hi!

I'm trying to solve a MIP with gurobi using column generation. The novel thing (for me) about this problem, is that the set of rows in the problem depends on the set of columns. That is, whenever I add a new column to the restricted master problem, there are N new constraints that must be added as well. My question is how to formulate the pricing problem since the duals of these new constraints does not yet exist in the restricted master problem. 

I've described the problem in more detail here https://math.stackexchange.com/questions/4794418/column-generation-when-number-of-rows-depend-on-number-of-columns , because this looks like a generic MIP/LP question not gurobi specific. Perhaps someone on this mailing list knows the answer?

 

Thanks!

Marco

関連

• Column Generation

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:35

  This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Mario Ruthmair

  • Gurobi Staff

  2023年11月08日 13:26

  Hi Marco,

  For me, this sounds like it requires both dynamic column and cut generation, resulting in a branch-price-and-cut algorithm.

  Usually, you start with the pricing loop in which you iteratively add all columns with negative reduced costs (in case of minimization) until you can prove that no further such columns exist. In those pricing problems, you only consider the duals for the constraints that currently exist in the model.

  Then, you switch to the cut loop, where you iteratively add all violated constraints until you prove that there are no further such constraints by solving the separating problem. In your case, the separation algorithm just might be enumerating the missing constraints for the current variable set.

  Then, you have to return to the pricing loop, etc. You switch between the two loops until you cannot find more columns and cuts to add. Then, you have solved the LP relaxation at the current branch-and-bound node.

  Best regards,
  Mario

  0
• 

  Marco Correia

  2023年11月16日 14:41

  • 
  • 
  • 

  Hi Mario! Thanks for the answer, that makes sense!

  0

投稿コメントは受け付けていません。