21 votes
Accepted

Solving pricing problem heuristically in column generation algorithm for VRP

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. ...
user avatar
21 votes

Reference for column generation applications

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 ...
user avatar
  • 2,677
20 votes
Accepted

Automating the column generation decomposition process

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 ...
user avatar
18 votes
Accepted

Variable bounds in column generation

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 ...
user avatar
  • 5,445
17 votes
Accepted

Column generation stabilisation

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 ...
user avatar
16 votes
Accepted

When using column generation, can a sub-problem be ignored once and for all once it fails to generate a new column?

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 ...
user avatar
13 votes

Reference for column generation applications

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, ...
user avatar
  • 131
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 ...
user avatar
  • 10.4k
12 votes

Reference for column generation applications

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. ...
user avatar
  • 511
12 votes

Automating the column generation decomposition process

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

Reference for column generation applications

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. ...
user avatar
  • 1,225
12 votes
Accepted

Column generation for a linear optimization problem

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) \...
user avatar
  • 3,333
11 votes
Accepted

Online Education for OR and Developing Decision Support Systems

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)...
user avatar
  • 5,756
11 votes
Accepted

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

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,...
user avatar
11 votes
Accepted

Stabilization techniques in column generation when subproblems are not solved optimally

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-...
user avatar
10 votes

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 ...
user avatar
  • 10.4k
9 votes

Variable bounds in column generation

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 \...
user avatar
9 votes

Reference for column generation applications

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 ...
user avatar
9 votes

Column generation stabilisation

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 ...
user avatar
  • 2,052
9 votes

Reference for column generation applications

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. ...
user avatar
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 ...
user avatar
  • 1,587
8 votes

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

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 ...
user avatar
8 votes

Solving pricing problem heuristically in column generation algorithm for VRP

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 ...
user avatar
  • 613
8 votes
Accepted

Column generation for TSP

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 ...
user avatar
  • 2,717
8 votes
Accepted

Column generation when intractable variables appear in the objective function

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} =...
user avatar
  • 22.7k
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 ...
user avatar
8 votes

Why is the tailing off effect only a problem in column generation?

"Tailing-off effect" is a generic term that refers to an something like "the algorithm is hitting a plateau and progress becomes very slow towards the end". In other words: after ...
user avatar
  • 3,333
7 votes

Column generation stabilisation

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 ...
user avatar
7 votes

Optimality in a simultaneous column and row generation procedure

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 ...
user avatar
7 votes
Accepted

General question regarding column generation

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, ...
user avatar
  • 10.4k

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