21

Generating routes heuristically, or heuristic pricing, is very common in the vehicle routing literature. Even when the pricing problem can be solved exactly, heuristic pricing is often tried first. Only when no more routes can be generated by heuristics, the exact pricing algorithm is run. When heuristic pricing is used in this way, the overall method is ...


21

A nice comprehensive collection on applications can be found in the book by Desaulniers, Desrosiers and Solomon: Column Generation. It features articles about Shortest Path Problems with Resource Constraints Vehicle Routing Problem with Time Windows Cutting Stock Problems Large-Scale Models in the Airline Industry Robust Inventory Ship Routing by Column ...


19

You should take a look at GCG, a plugin for SCIP and part of the SCIP Optimization Suite. After the standard presolving process of SCIP, GCG performs a Dantzig-Wolfe decomposition of the problem to obtain an extended formulation of the problem. The decomposition is based on a structure either provided by the user or automatically detected by one of the ...


18

Assuming that the $a_{ij}$'s are either zero or one, and the $c_j$'s are positive, you do not need the upper bound on the variables. To see this, if $x_j=1$ for some $j$, then column $j$ covers all items, $i$, where $a_{ij}=1$ and it does not cover any other items. Increasing $x_j$ to $1+\varepsilon$, for some $\varepsilon>0$, will increase the cost, and ...


17

Stabilization methods are tricky. Dual optimal inequalities are you best chance to obtain significant speed ups. Basically they prevent a bunch of useless dual values by exploiting problem-specific structures to impose constraints on the dual space. They reduce the number of pricing iterations without compromising the complexity. Unfortunately, they are ...


15

You can only stop when all subproblems fail to find a negative reduced cost column. So, no, when one subproblem does not find a column in one iteration you cannot conclude that you need not call it again. Below you see an instance with 40+ subproblems (one for each color). Over the iterations, in fact most subproblems are unsuccessful, but later still find ...


13

Every four years (year mod 4 = 0) there is an international Column Generation conference, alternated with a school on column generation, also every four years (year mod 4 = 2), (e.g. school in 2018, workshop in 2016, etc.), You can find plenty of applications there.


13

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


12

Axel Parmentier's thesis discuss about application in some airline operations problems. You didn't really ask for it, but for reference about VRP related problem, see Feillet (2010) and Pessoa et al. (2019) Reference: Parmentier, Axel. “Algorithms for shortest path and airline problems.” Université Paris-Est, 2016. Feillet, Dominique. “A Tutorial on ...


12

Multi-agent pathfinding is a classical artificial intelligence problem that I recently solved using column generation. This implementation is substantially faster than the previous state-of-the-art. The paper and code (!) is available on my web page ed-lam.com.


12

TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem. Equivalence between primal and dual form Consider the (primal) LP problem \begin{align} (P) \ \ \ \min_{x \in \mathbb{R}^{n}} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & \sum_{j=1}^{n} a_{i, j} x_{j} \geq b_{i}, & i = 1, ..., M, \end{...


11

Check Coursera, edX, Udemy, or any other online courses (such as those of Stanford). For example: Free: Discrete Optimization course on Coursera, covers column generation and an introduction to (meta)heuristic Optimization with Metaheuristics in Python on Udemy Lectures of Introduction to Meta-heuristics Artificial Intelligence: Reinforcement Learning in ...


11

You are right. If you solve the pricing heuristically, you do not have a valid lower bound. One approach to obtain a lower bound would be to solve a relaxation of the pricing problem exactly. Usually, the faster a relaxation can be solved, the worse in the resulting bound. Another (but still similar) approach is to calculate a lower bound on the pricing ...


11

I am a co-author of this paper. The parameter-less dual price smoothing approach can totally be used even if pricing subproblems are solved heuristically. We do it very often. When calculating the sub-gradient, you just use your best heuristic solutions (in terms of reduced cost) for the pricing subproblems. Of course, the better is your heuristic, the ...


11

Or, if you want a commercial implementation - SAS/OR has a Decomposition feature.


9

When pricing $x_j$, there are two possibilities: $x_j$ is not in the restricted master problem / $x_j$ has not been added before. In this case, $x_j=0$ in the current solution. The constraint $x_j \le 1$ is not active, such that the associated multiplier is equal to 0. It is thus not a problem that the constraint was not added to the restricted master ...


9

I like the column generation algorithm by Shen, et al. (2003) for a location–inventory model. Reference: Shen, Z.-J. M., C. Coullard, and M. S. Daskin. A Joint Location-Inventory Model. Transportation Science, 37:1, 40-55, 2003.


9

Has anyone performed a benchmark of the various stabilization techniques in column generation? ... implemented in SCIP ... The thesis "Generic Branch-Cut-and-Price" (.PDF), by Gerald Gamrath (and supervised by our Marco Lübbecke) is mentioned on the About webpage for the Generic Column Generation (GCG) software. Compare with SCIP's VRP (tiny) example docs. ...


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


8

Even if you solve the pricing heuristically, you can still obtain a valid lower bound in certain cases. However, it depends on your pricing heuristic whether this is possible. You have found the optimal solution to the linear relaxation of the master problem if there are no more columns with negative reduced costs. Suppose you have a heuristic that always ...


8

The general rule is to use dynamic programming (Labeling Algorithm) to solve the VRP pricing problem. It has some advantage over solving the mathematical model. DP can yield many columns in each iteration versus the one column that yielded by solving the model. As @Kevin Dalmeijer mentioned you need to be able to solve the pricing problem exactly even if you ...


8

Column Generation is one of the best method to solve the classical Graph Coloring Problem, see: Mehrotra, A. and Trick, M.A., 1996. A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4), pp.344-354. Gualandi, S. and Malucelli, F., 2012. Exact solution of graph coloring problems via constraint programming and column generation. ...


8

As Marco briefly explained in his comment, TSP is not the ideal problem to teach the column generation approach. TSP is suited for the row generation approach, also known as branch-and-cut, by following the Dantzig–Fulkerson–Johnson formulation that you can easily find on the web (for example, on the Wikipedia page related to TSP). On the other, VRP is a ...


8

Suppose $K$ is the set of columns, where the $k$th column $x^k \in \{0,1\}^n$ satisfies $A(x^k) \le a$. Now express $x$ as a convex combination of the columns $x^k$. Explicitly, substitute $x_{i,j} = \sum_{k\in K} \lambda_k x_{i,j}^k$, where $\sum_{k\in K} \lambda_k = 1$ and $\lambda_k \ge 0$ for all $k\in K$. You then obtain the following master problem ...


7

In our JOC paper (Pessoa et al.) mentioned by Claudio, we have performed comparison (on 9 different problems including VRP) between some penalty function approaches and dual price smoothing (both are described in the Claudio's answer). Penalty function approaches we tried have generally better performance than dual price smoothing. However, the former are ...


7

As you are probably aware of, the standard optimality condition for column generation is not valid if not all constraints are included in the master problem, as the dual information of the missing constraints needs to be taken into account in the computation of the reduced costs. Muter et al. (2013) consider this issue and show that if the formulation ...


7

As suggested by @LarrySnyder610, I am pasting my comment as an answer : Neither one ! It is the linear relaxation of the original integer problem, after applying a Dantzig-Wolfe decomposition, which in essence, consists in reformulating variables as a convex combination of the extreme points of the polytope defined by the constraints of the original ...


7

Let $d_i$ be the demand for customer $i\in N$, let $V=\{1,\dots,K\}$ be the set of vehicles, and let $P$ be the set of columns, where each column corresponds to a feasible subtour starting from the depot, with arc variables $x_{i,j}$ and node variables $y_i$. Let $z$ be the makespan. The master problem over $z$ and $\lambda$ is as follows, with dual ...


7

A greedy heuristic is natural to try here: Declare all groups to be admissible. Find an admissible group $g$ with the largest weight. Set $u_g=1$. Declare all groups $h$ with $N_h \cap N_g \not= \emptyset$ inadmissible. If some $i$ is still uncovered, go to step 2. For your sample data in the linked question, this greedy heuristic returns groups $$\{11,12,...


6

There are two possible situations. 1) You still want to solve your VRP exactly or obtain a valid lower bound. Then heuristic pricing is used only to speed up column generation (and it is always used nowadays). At the end, you always need to solve the pricing problem (or at least its relaxation) exactly. A standard approach for heuristic pricing is some ...


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