Skip to main content

Column generation when number of rows depend on number of columns




  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi Marco,

    For me, this sounds like it requires both dynamic column and cut generation, resulting in a branch-price-and-cut algorithm.

    Usually, you start with the pricing loop in which you iteratively add all columns with negative reduced costs (in case of minimization) until you can prove that no further such columns exist. In those pricing problems, you only consider the duals for the constraints that currently exist in the model.

    Then, you switch to the cut loop, where you iteratively add all violated constraints until you prove that there are no further such constraints by solving the separating problem. In your case, the separation algorithm just might be enumerating the missing constraints for the current variable set.

    Then, you have to return to the pricing loop, etc. You switch between the two loops until you cannot find more columns and cuts to add. Then, you have solved the LP relaxation at the current branch-and-bound node.

    Best regards,

  • Marco Correia
    First Comment
    First Question

    Hi Mario! Thanks for the answer, that makes sense!


Please sign in to leave a comment.