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.
$\begingroup$
$\endgroup$
1
-
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übbeckeNov 8, 2019 at 4:43
Add a comment
|
9 Answers
$\begingroup$
$\endgroup$
1
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)
-
3$\begingroup$ @MarcoLübbecke probably has some more exciting examples. $\endgroup$– JakobSJun 7, 2019 at 10:58
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Jun 7, 2019 at 0:54
$\begingroup$
$\endgroup$
Column Generation is one of the best method to solve the classical Graph Coloring Problem, see:
Mehrotra, A. and Trick, M.A., 1996. A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4), pp.344-354.
Gualandi, S. and Malucelli, F., 2012. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing, 24(1), pp.81-100.
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, ...):
- Gualandi, S. and Malucelli, F., 2013. Constraint programming-based column generation. Annals of Operations Research, 204(1), pp.11-32.
answered Jun 28, 2019 at 6:30
$\begingroup$
$\endgroup$
There are also several papers on column generation for location problems:
- Capacitated facility location problem
- Single source capacitated facility location problem
- $p$-median problem (this method works on the original variables, and the columns are then generated on an "as needed" basis)
$\begingroup$
$\endgroup$
Column generation is widely used in airline applications. For instance :
The aircraft routing problem. The crew pairing problem. The crew rostering problem.
$\begingroup$
$\endgroup$
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
