Questions tagged [branch-and-price]
The branch-and-price tag has no usage guidance.
10
questions
6
votes
1answer
156 views
Dual of a model to obtain reduced costs
I have the following model which I am going to solve with column generation. Basically it is a VRP problem with pick-up and delivery in which couriers are assigned to a set of shifts based on their ...
6
votes
1answer
55 views
Branch and price with two sets of exponential variables
There are classes of problems which allow for "natural" extended formulations using multiple exponential-size sets of variables.
For example, 2-echelon routing problems can be modelled ...
6
votes
5answers
975 views
How to implement branch and price?
I heard once that the branch and price (B&P) algorithm is among the hardest ones in OR, but if it's implemented well, it could be very efficient. Aare there other algorithms that are also that ...
1
vote
1answer
142 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 ...
6
votes
2answers
404 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
125 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
204 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
155 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 ...
6
votes
1answer
115 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
291 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 ...
