# Tag Info

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. ...
• 5,893

### 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,677
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,685
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 ...
• 5,445
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,519
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,809

### 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
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 ...
• 10.4k

### 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. ...
• 511

### Automating the column generation decomposition process

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

### 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,225
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) \...
• 3,333
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,756
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,244
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,244

### 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 ...
• 10.4k

• 22.7k

### 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,244

### 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 ...
• 3,333

### 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,244

### 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,254