# 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. ...
• 6,212

### 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,767
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,866
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,562
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,574
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,929
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,183

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

### Automating the column generation decomposition process

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

• 32.7k