# Questions tagged [branch-and-price]

The tag has no usage guidance.

20 questions
Filter by
Sorted by
Tagged with
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
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
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. ...
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 ...
1 vote
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 ...
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
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
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
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
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 ...
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
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
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
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
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
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
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 ...
1 vote
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 ...
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