Questions tagged [branch-and-price]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
50 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 ...
gmn's user avatar
  • 666
0 votes
0 answers
45 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. ...
GeoRie's user avatar
  • 1
2 votes
1 answer
185 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 ...
Sina_Alef's user avatar
1 vote
0 answers
69 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 ...
Shuyang Zhang's user avatar
5 votes
3 answers
607 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:...
BD26's user avatar
  • 51
4 votes
1 answer
379 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 ...
133crem's user avatar
  • 41
7 votes
1 answer
171 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 ...
Victor Hugo's user avatar
10 votes
1 answer
418 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 ...
pele's user avatar
  • 123
9 votes
1 answer
295 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 ...
Dr. Soomin Woo PhD's user avatar
6 votes
1 answer
404 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}\\ ...
pozyavas's user avatar
7 votes
1 answer
87 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 ...
Alberto Santini's user avatar
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 ...
Best_fit's user avatar
  • 567
6 votes
2 answers
586 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'...
Bhr's user avatar
  • 455
5 votes
1 answer
282 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 ...
Bhr's user avatar
  • 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 ...
A.A's user avatar
  • 233
2 votes
1 answer
436 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 ...
prakash gawas's user avatar
1 vote
1 answer
322 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 ...
User123456789's user avatar
6 votes
1 answer
210 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 } \...
Kuifje's user avatar
  • 13.3k
14 votes
1 answer
659 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 ...
vulpith's user avatar
  • 383