17
$\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$
17
$\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)

$\endgroup$
  • 3
    $\begingroup$ @MarcoLübbecke probably has some more exciting examples. $\endgroup$ – JakobS Jun 7 at 10:58
10
$\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.

$\endgroup$
10
$\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.

$\endgroup$
7
$\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.

$\endgroup$
7
$\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, ...):

$\endgroup$
6
$\begingroup$

Every two years there is an international Column Generation conference (e.g. in 2018, 2016, etc.), sometimes with a school program as well.

You can find plenty of applications there.

$\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.