Questions tagged [branch-and-price]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
270 views

Branch and Price Algorithm

Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP. In the literature, I haven'...
3
votes
1answer
82 views

A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
11
votes
1answer
123 views

Branch and Price algorithm is exact?

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
2
votes
1answer
76 views

C++ code for branch and price

I looking to learn to use bpcolumn generation techniques in c++. Does any body know of GitHub repository or any other site where I can find some code And learn about it... The application can be ...
2
votes
0answers
73 views

Branch-and-Price: return gap using SCIP

I implemented a branch-and-price tree in python. I would like to stop the process after 5 hours and return the gap in % between the best integer solution found so far and the optimal solution. How ...
5
votes
1answer
91 views

When using column generation, can I delete a node with negative reduced cost from my subproblem?

I am solving a minimization problem with a column generation procedure. The master problem is of the form $$ \min \sum_{i\in \Omega}c_i \lambda_i $$ subject to $$ \sum_{i\in \Omega \mid v \in i } \...
12
votes
0answers
188 views

Tools to implement branch-and-price algorithms

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms. I ...