メインコンテンツへスキップ

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

回答済み

コメント

2件のコメント

  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff
    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

    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.

    0

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