Questions tagged [branch-and-price]
The branch-and-price tag has no usage guidance.
16
questions
1
vote
0
answers
67
views
How to consider time cost in VRP with BPC method
When we use branch, price and cut method to solve VRPTW problems, the objectives is always:
minimize the total distance, or
minimize the sum of distance-related variable cost and truck-related fixed ...
5
votes
3
answers
580
views
Puzzles of branch and price algorithm
I'm new to the branch and price algorithm. Though I have some knowledge about how branch & bound and column generation work, there're still some details making me confused.
In short, my problem is:...
- 51
4
votes
1
answer
303
views
How do we branch a Cutting Stock problem using Branch and Price?
I'm sure this is a straightforward question, but since I started learning integer programming recently this isn't clear to me.
Consider solving a 1 dimensional cutting stock problem using delayed ...
- 41
7
votes
1
answer
165
views
Name of graph algorithm arising while using the Ryan Foster Branching
I'm using the Ryan-Foster branching in my Branch and Price algorithm for a pickup and delivery problem, but I'm having trouble keeping track of all the pairs as I go down the search tree.
Let's say ...
- 173
10
votes
1
answer
367
views
Integer column generation without branch & price
Consider the following situation. I have an integer program which I want to solve using column generation. After a suitable decomposition, the master problem has decision variables that select the ...
- 123
9
votes
1
answer
267
views
Odd behavior in the branch bound and price algorithm with column generation
I have two questions on branch-bound-and-price.
Why does it sometimes fail? For instance, the paper by Dabia et al shows results where the proposed algorithm fails for some cases. The paper does not ...
6
votes
1
answer
395
views
Dual of a model to obtain reduced costs
I have the following model which I am going to solve with column generation.
\begin{align}
\max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\
...
- 61
7
votes
1
answer
80
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 ...
- 2,073
6
votes
5
answers
2k
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 ...
- 567
6
votes
2
answers
560
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'...
- 455
5
votes
1
answer
259
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 ...
- 455
13
votes
1
answer
797
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 ...
- 233
2
votes
1
answer
404
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 ...
- 173
1
vote
1
answer
287
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
1
answer
201
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.9k
14
votes
1
answer
597
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 ...
- 383