What you can do is to solve the LP relaxation of your model with column generation.
AnsweredLooking for advice here.
I have a column generation model to solve a crew pairing problem (a set partitioning problem). I am solving the LP relaxation of the model at the root using column generation and a shortest path with ressource constraints for the pricing algorithm.
In a toy example using 14 flight legs, the shortest path algorithm suggests first to add a new column with negative reduced cost (-20.349). Let's call this column c1=[1,2,3,4].
Once added to the relaxed LP, the dual and shortest path suggest adding a new column with reduced cost (-20.349). This is the same reduced cost as for c1. Let's call it c2=[10,11,3,4]. Both c1 and c2 had negative reduced cost during the first execution of the shortest path algorithm but c1 was selected as I wanted to debug by adding one column at a time.
Obviously in a set partitioning problem, I can't have c1 and c2 in the solution since leg 3 and leg 4 are over-covered and indeed the solution to the relaxed LP with the new c2 added does not include c2.
At the next iteration, I have another column suggested with reduced cost (-20.1). Let's call it c3=[10,11,7,9] and this c3 is indeed used in the solution of the LP relaxation.
I am a bit intrigued because I thought that columns with negative reduced costs would be immediately part of the solution to the LP.
Thoughts?
-
Hi Cedric,
This is coming from our specialized Gurobi AI Guide and hits the bull's eye:
In the column generation method for solving LP relaxations, columns with negative reduced costs are not always included in the solution for a few reasons:
-
Feasibility and Constraints: A column must be feasible under the current dual prices and constraints. If it disrupts feasibility (like over-covering a route), it might not be included even if it has a negative reduced cost.
-
Column Dominance and Redundancy: If a new column doesn't provide a new or better way of improving the objective compared to existing columns, it might be excluded.
-
Simplex Algorithm Dynamics: The simplex method selects columns that best maintain overall feasibility and optimize the objective rather than just those with the most negative reduced cost.
-
Algorithm Settings: Implementation details and parameter settings in the algorithm can affect column selection, potentially prioritizing some columns over others even if they have similar reduced costs.
0 -
Please sign in to leave a comment.
Comments
1 comment