Questions tagged [branch-and-price]
The branch-and-price tag has no usage guidance.
20
questions
2
votes
0
answers
62
views
Branching in branch and price
I implement a branch-and-price approach to solve a variant of the bin packing problem. I start with a compact IP formulation and decompose it using Dantzig-Wolfe decomposition into a master problem ...
- 593
0
votes
1
answer
65
views
Branch-and-Price for VRPs: Enforcing branching on arcs
The following is based on my understanding, which may have flaws, so please correct me if I claim something wrong.
When solving VRPs with Branch-and-Price, one can enforce integrality by branching on ...
- 668
0
votes
0
answers
53
views
Local Branching in Branch-And-Price
Is it somehow possible to apply local branching in branch-and-price?
In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution.
...
- 1
2
votes
1
answer
198
views
How to evaluate the quality of a solution obtained using the price-and-branch method for an IP problem?
I have solved an integer programming problem using the price-and-branch (not branch-and-price) approach exactly as same as described in this question and obtained a feasible solution. As this approach ...
- 35
1
vote
0
answers
72
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
634
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
443
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
191
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
454
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
321
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
408
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
93
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,133
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
630
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
294
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
1k
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
461
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
345
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
214
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 } \...
- 13.7k
14
votes
1
answer
775
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