Questions tagged [column-generation]

Questions on algorithms that solve mathematical models by generating columns (variables) in the pricing step during solution on demand.

Filter by
Sorted by
Tagged with
23 votes
9 answers

Reference for column generation applications

When talking about column generation algorithms, the main example is the cutting stock problem. I'm aware that variations of vehicle routing problem (VRP) can be solved using a column generation ...
EhsanK's user avatar
  • 5,864
12 votes
1 answer

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

Suppose you are solving a minimization problem with a column generation procedure, and that you have $2$ sub-problems. At some point, one of the $2$ sub-problems is no longer able to generate a column ...
Kuifje's user avatar
  • 12.9k
26 votes
5 answers

Solving pricing problem heuristically in column generation algorithm for VRP

In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is: Generate some routes. Solve the set covering problem using those ...
LarrySnyder610's user avatar
20 votes
3 answers

Variable bounds in column generation

Consider the set covering problem \[ \begin{align} \min&\ \sum_{j=1}^nc_jx_j\\ s.t.:&\ \sum_{j=1}^na_{ij}x_j\geq 1,\quad \forall i=1,\dots,m\\ &\ 0\leq x_j \leq 1 \end{align} \] ...
Djames's user avatar
  • 1,133
19 votes
3 answers

Column generation stabilisation

Has anyone performed a benchmark of the various stabilisation techniques in column generation? Which ones perform better for set pack/partition/cover problems like VRP? And are there theoretical ...
Edward Lam's user avatar
  • 1,235
6 votes
2 answers

Branch and Price Algorithm

Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP. In the literature, I haven'...
Bhr's user avatar
  • 455
6 votes
1 answer

Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
Bhr's user avatar
  • 455
4 votes
1 answer

Column Generation algorithm

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
Bhr's user avatar
  • 455