13
votes
Accepted
Branch and Price algorithm is exact?
To answer your question, it is good to have in mind the following concepts:
Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex ...
- 12.9k
11
votes
Accepted
Integer column generation without branch & price
This approach is sometimes referred to as price-and-branch (vs branch-and-price), or solving the restricted master, and it does not guarantee optimality.
It is equivalent to the following question: is ...
- 12.9k
11
votes
How to implement branch and price?
Before starting implementation, I would make sure I am comfortable with all the theoretical aspects, which are somewhat tricky as well. This is quite an advanced topic in OR and requires some ...
- 12.9k
9
votes
Branch and Price Algorithm
Being a good or bad approach will depend on several factors, for example:
the size of the instances
time available to find a solution (this tends to be an important matter in vehicle routing ...
- 1,667
8
votes
Odd behavior in the branch bound and price algorithm with column generation
There can be many reasons why a branch-cut-and-price algorithm fails to solve an instance to optimality in a reasonable time.
A large primal-dual gap because a heuristic solution is absent or of a ...
- 1,394
7
votes
Accepted
A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet
Note that (as is asserted in the cited tutorial):
The cost of a route is the addition of the arcs that compose it: $c_k = \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij}$
Relate $a_{ik}$ ($r_k$ visits customer ...
- 1,667
5
votes
How to implement branch and price?
Using a framework like SCIP may be a good
idea for starting. By doing so, you can quickly implement your formulation. It has interfaces on both C++ and Python. The documentation contains examples of ...
- 61
5
votes
Branch and Price Algorithm
VRPy (v0.3.0) now supports this option : all you have to do is set the minimize_global_span option to True when instantiating ...
- 12.9k
5
votes
Puzzles of branch and price algorithm
At each node, you need to ensure that the initial LP is feasible. For example, for the Bin Packing problem, you can add a column for each item or group of items that must be in the same bin ...
- 2,495
5
votes
How to implement branch and price?
Nah. Building an ASL interface is hard, BnP is OK. Assuming you are familiar with its building blocks (just like with any other algorithm), the challenge lies in the implementation details.
There are ...
- 11.9k
4
votes
How to implement branch and price?
If you want to look at C++ source code, there are some COIN-OR projects that provide frameworks for "branch price and cut" or "branch cut and price" as it's sometimes known. Two ...
- 37.9k
4
votes
Accepted
Branch and price with two sets of exponential variables
A common case where you would see 2 or more exponentially large sets of variables, is in:
VRPs with heterogeneous vehicles: some vehicles have special equipment or larger capacity and can serve ...
- 3,396
4
votes
Puzzles of branch and price algorithm
The columns of the child can be initialized by the subset of columns of the parent that also satisfy the branching conditions. For each child node, you would perform column generation to solve the ...
- 30.5k
4
votes
C++ code for branch and price
Out of the multiple options, the open-source option is Coin-OR's BCP (Branch-Cut-Price) [github]. SCIP also offers branch-and-price via its GCG (generic branch-cut-and-price) solver [link].
- 668
4
votes
Accepted
Branch-and-Price: return gap using SCIP
Accepted answer from the cross-post: Stop Branch-and-Price tree and return gap
You can easily compute this yourself: SCIPgetDualbound will return you
the best (...
4
votes
Accepted
When using column generation, can I delete a node with negative reduced cost from my subproblem?
If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a ...
- 2,073
3
votes
Tools to implement branch-and-price algorithms
You can check out the MINOTAUR codebase, it's pretty well written and designed for people to create their own algorithms.
Last time I checked (a few years ago), it wasn't very well documented, but the ...
- 11.9k
3
votes
Puzzles of branch and price algorithm
After branching, where do the columns of child node come from before new column being added by sub-problem?
It is very common to use previously generated columns because they could both be of high ...
- 2,073
2
votes
Dual of a model to obtain reduced costs
It's a bit tricky to sort out what is going on here. Given a dual solution ($\lambda,\gamma,\theta$) to the LP relaxation of the master problem, your subproblem will need to solve for $a_{ir}$ and $\...
- 37.9k
2
votes
How do we branch a Cutting Stock problem using Branch and Price?
At this stage you have the following options :
you could solve the restricted master problem with integer variables (this is also called price-and-branch). In this case you are using classical branch-...
- 12.9k
2
votes
Accepted
Name of graph algorithm arising while using the Ryan Foster Branching
Let $U$ be the universe (e.g. total set of elements). Then, if I understand your post correctly, you are looking for a function which given two elements $e_1,e_2\in U, e_1\neq e_2$, tells you if they ...
- 66
2
votes
How to implement branch and price?
One of the main ideas behind our decomposition solver GCG (gcg.or.rwth-aachen.de/dev) is to save you the time experimenting with your own B&P code only to find out that B&P is not the right ...
- 5,909
Only top scored, non community-wiki answers of a minimum length are eligible