Skip to main content

What you can do is to solve the LP relaxation of your model with column generation.



1 comment

  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    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:

    1. 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.

    2. 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.

    3. 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.

    4. 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.


Please sign in to leave a comment.