22
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. ...
- 6,063
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 ...
- 2,737
21
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 ...
- 2,856
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 ...
- 6,352
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 ...
- 1,549
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 ...
- 5,909
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, ...
- 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 ...
- 12.9k
13
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) \...
- 4,068
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. ...
- 521
12
votes
Automating the column generation decomposition process
Or, if you want a commercial implementation - SAS/OR has a Decomposition feature.
- 516
12
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-...
- 1,394
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. ...
- 1,235
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)...
- 5,864
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,...
- 1,394
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
10
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 \...
- 6,063
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 ...
- 1,740
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 ...
- 2,098
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.
...
- 13.1k
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
9
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 ...
- 4,068
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 ...
- 2,305
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 ...
- 683
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 ...
- 2,936
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} =...
- 30.5k
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
8
votes
Column generation: decreasing value of restricted master problem
The reduced cost is the instantaneous rate of change as you increase the value of the new variable from 0. The actual impact of the new variable on the objective function is piecewise linear and ...
- 37.9k
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 ...
- 1,394
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 ...
- 2,305
Only top scored, non community-wiki answers of a minimum length are eligible