Column generation: how to add new variables

Awaiting user input

Jisoon Lim

• February 06, 2025 14:45
• Edited

Hi ,

I'm trying to implement column generation on my MIP (minimization objective).

I have a RMP, which is a linear relaxation of the original MIP with all of my "path" variables defined but most of the path variables fixed to zero -- by setting the lower and upper bounds of such variables to zero. After solving RMP, I solve a Pricing problem and I obtain a number of new paths (with negative reduced costs). To add the corresponding path variables to the RMP, as I already have all path variables defined in the RMP, I simply remove the bounds to the variables to introduce them to the RMP. 

I know a "standard" way of doing CG is rather to have such "unused path variables" not introduced to the RMP, and add them later to the RMP only when discovered by the Pricing problem. I took my approach because I wanted to avoid making excessive modifications on the left-hand-side of my RMP -- removing bounds on a variable requires fewer lines of code than adding a new variable and modifying left-hand-side of all constraints that contain a variable.

My question is whether my method of modeling, other than a memory issue, can cause additional problems in model solution efficiency, i.e., would my RMP solution time be worse than the "standard" way? My understanding is that all variables fixed to zero in RMP would be removed at presolve (and all corresponding columns too), so it would not impact the efficiency of simplex (or any other method the solver decides to take to solve the LP), but I want to double-check.

Thank you.

 

 

Related to

• Column Generation

0

• 

  David Torres Sanchez

  Gurobi Staff

  • February 06, 2025 14:56
  • Edited

  Hi Jisoon,

  How are you generating the variables beforehand, and how are you choosing which ones are set to 0?

  You need to solve the intermediate RMP to get the duals that are used in the pricing problems. I don't think you can skip this. Unless you enumerate all columns in which case you are not performing column generation as you are just solving the full master problem.

  There are efficient ways of adding columns, e.g. by using the Column object, which is passed when generating a variable via addVar (\(\texttt{column}\) argument). There are some sample codes online.

  Cheers, 
  David

  0
• 

  Jisoon Lim

  • February 06, 2025 16:47
  • Edited

  

  

  

  Hi David,

  I am providing an initial feasible solution, which is a path found through a heuristic. For the path found with the heuristic, I set the variable lb/ub to 0/1, and the rest to 0/0. So, even if the variables "exist" in the RMP, they are effectively restricted from selection, as I have a constraint staying a sum of path_variables equals to 1

  Essentially, my MIP is a path-finding problem that minimizes a cost, and my Pricing problem is a flow-based shortest path problem with dual variables as coefficients in the objective function. 

  0
• 

  David Torres Sanchez

  Gurobi Staff

  • February 06, 2025 18:22

  Hi Jisoon,

  You can start with a subset of columns (e.g., the solution from a heuristic), but I'm confused because it sounds like you're starting with all of them.
  Won't fixing variables affect the duals? 

  To answer your original question:

  My understanding is that all variables fixed to zero in RMP would be removed at presolve (and all corresponding columns too), so it would not impact the efficiency of simplex (or any other method the solver decides to take to solve the LP), but I want to double-check.

  Yes, presolve will remove those variables that are fixed to 0.

  Cheers, 
  David

  0

Please sign in to leave a comment.