22
$\begingroup$

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 approach. What are some other problems where column generation-based approaches have been applied successfully? References are really appreciated.

$\endgroup$
  • 4
    $\begingroup$ remark: when people say "solved by column generation" they really mean solved by branch-and-price -- the former only solves the LP relaxation... $\endgroup$ – Marco Lübbecke Nov 8 '19 at 4:43
21
$\begingroup$

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 Constraints
  • Vehicle Routing Problem with Time Windows
  • Cutting Stock Problems
  • Large-Scale Models in the Airline Industry
  • Robust Inventory Ship Routing by Column Generation
  • Ship Scheduling with Recurring Visits and Visit Separation Requirements
  • Job Shop Scheduling
  • Machine Scheduling

Also the paper Selected Topics in Column Generation has some examples on page 3. (DOI link)

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ @MarcoLübbecke probably has some more exciting examples. $\endgroup$ – JakobS Jun 7 '19 at 10:58
13
$\begingroup$

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, workshop in 2016, etc.),

You can find plenty of applications there.

| improve this answer | |
$\endgroup$
12
$\begingroup$

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. (2019)

Reference:

Parmentier, Axel. “Algorithms for shortest path and airline problems.” Université Paris-Est, 2016.

Feillet, Dominique. “A Tutorial on Column Generation and Branch-and-Price for Vehicle Routing Problems.” 4OR 8, no. 4 (December 2010): 407–24.

Pessoa, Artur, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. “A Generic Exact Solver for Vehicle Routing and Related Problems.” In Integer Programming and Combinatorial Optimization, edited by Andrea Lodi and Viswanath Nagarajan, 11480:354–69. Cham: Springer International Publishing, 2019.

| improve this answer | |
$\endgroup$
12
$\begingroup$

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. The paper and code (!) is available on my web page ed-lam.com.

| improve this answer | |
$\endgroup$
9
$\begingroup$

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. Transportation Science, 37:1, 40-55, 2003.

| improve this answer | |
$\endgroup$
8
$\begingroup$

Column Generation is one of the best method to solve the classical Graph Coloring Problem, see:

Another survey you can have a look is about Constraint Programming-based Column Generation, where typically the pricing subproblem is solved using a Constraint Programming solver (with applications in Airline plannig, Travelling tournament problem, Employee timetabling, Wireless Mesh Networks, ...):

| improve this answer | |
$\endgroup$
5
$\begingroup$

There are also several papers on column generation for location problems:

  1. Capacitated facility location problem
  2. Single source capacitated facility location problem
  3. $p$-median problem (this method works on the original variables, and the columns are then generated on an "as needed" basis)
| improve this answer | |
$\endgroup$
4
$\begingroup$

Column generation is widely used in airline applications. For instance :

The aircraft routing problem. The crew pairing problem. The crew rostering problem.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Column generation has been used for beam angle selection for radiation treatment planning (specifically for non-coplanar IMRT). Here's an example:

Feasibility of prostate robotic radiation therapy on conventional C-arm linacs

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.