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?
-
Official comment
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. -
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 -
Post is closed for comments.
Comments
2 comments