# Tag Info

12

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 combination of the extreme points of the polygon defined by the constraints of the problem. Column generation : once this change of variables has been done, you ...

11

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 experience. Are you comfortable with branch-and-bound, with the simplex algorithm, with Dantzig-Wolfe decomposition, column generation, etc ? You are hesitating between ...

9

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 applications) computing power what level of solution quality qualifies as good enough See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with ...

5

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 a few things to be aware of for BnB in general, and for BnP specifically: BnB Acceleration heuristics: BnB algorithms only work well if combined with certain ...

5

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 branch-and-price, I suggest you to take a look at them. For any problem at hand, you can use Dantzig-Wolfe decomposition method to generate branch-and-price ...

5

VRPy (v0.3.0) now supports this option : all you have to do is set the minimize_global_span option to True when instantiating the VehicleRoutingProblem object: prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True) prob.solve() Of course, your graph $G$ has to be well defined in the first place. The formulation proposed by @RobPratt is ...

5

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 $i$) with $b_{ijk}$ (route $k$ uses arc $(i,j)$): $a_{ik} = \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk}$ And the conditions (22) and (23) are equivalent ...

4

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].

4

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 (global) dual bound, and SCPgetPrimalbound will give you the best primal bound. -Leon Will delete this CW if Leon posts answer here.

4

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 vertex, removing the vertex gives another path which is both feasible for the sub-problem and which corresponds to a master problem column with smaller reduced ...

4

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 that come to mind are BCP and Symphony.

2

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 approach to your problem. One other main idea of our solver is that once you found out that B&P is a good approach then you can just use GCG to do the job for ...

Only top voted, non community-wiki answers of a minimum length are eligible