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

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

### 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, ...
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 ...
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) \...

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

### Automating the column generation decomposition process

Or, if you want a commercial implementation - SAS/OR has a Decomposition feature.
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-...

### 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. ...
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)...
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,...
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 ...

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

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