Seeking help on Branch and Price

Note that this may not be the global minimum because we are not adding new columns during the solution of the mixed-integer problem model (an algorithm known as branch and price).

Could someone please help me how to formulate the branch and price model for this problem? Here they just generated columns without branching the variables, but I would like to implement branching and then generate columns based on pricing. Is it possible to provide the revised code?

Hi @wahadhasan, welcome to the forum.

Branch-and-price is not simple to implement, which is why the tutorial does not provide the code. You’ll need to manually implement the branch and bound tree.

Alternatively, you could investigate GitHub - atoptima/Coluna.jl: Branch-and-Price-and-Cut in Julia. See this tutorial:

2 Likes

My opinion is: one might not have to stick at branch and price (or, a column generation algorithm).

There are 2 iterative procedures regarding large-scale LP/MIP:

  1. iteratively adding cutting planes, aka outer approximation, constraint generation
  2. iteratively recruiting vertices of the original polyhedron, aka inner approximation, column generation

They essentially have a dual relationship—meaning that you only have to opt one of the two methods. The outer approximation cutting plane method is more widespread and technologically mature (e.g. the Gurobi solver is a branch-and-cut solver), thereby more advisable.

here is an example that might be illuminating.