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
-
5$\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übbeckeCommented Nov 8, 2019 at 4:43
Add a comment
|
11 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$– JakobSCommented Jun 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$
Recently, a new reference, Branch-and-Price, was published by J. Desrosiers, M. L¨ubbecke, G. Desaulniers, J. B. Gauthier.
They expect the reader to have modeling experience with network, linear and integer linear programs. Essentials are presented in Chapter 1 (Linear and Integer Linear Programming). Column Generation is an algorithm for solving large scale linear programs: as such, there is the dedicated Chapter 2 in which we see the similarities and differences with the primal simplex algorithm. The Dantzig-Wolfe decomposition is, in fact, a reformulation method: Chapter 3 presents the classical way for linear programs; this is based on the convexification approach of a sub-domain. Chapter 4 goes further, adapting it to integer linear programs, and also presenting the reformulation based on the discretization approach. Chapter 5 (Vehicle Routing and Crew Scheduling Problems) follows and gives access to important applications. Chapter 6 explores the Dual Point of View: it notably presents another decomposition method, the Lagrangian relaxation approach. We see its relationships with the Dantzig-Wolfe reformulation. A better understanding of duality leads to stabilization approaches. Chapter 7 (Branch-Price-and-Cut) presents how to handle various branching and cutting decisions to get integer solutions, indeed, to solving the original model.
$\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
$\begingroup$
$\endgroup$
Another recently published reference by Eduardo Uchoa, Artur Pessoa, and Lorenza Moreno is Optimizing with Column Generation.
We are excited to present the early release of Part I of our book “Optimizing with Column Generation: advanced Branch-Cut-and-Price Algorithms”. While the book’s ultimate goal, as suggested by its subtitle, is to describe cutting-edge techniques in these algorithms, this objective is primarily addressed in the forthcoming Part II. However, we feel that the completed first part, covering the fundamentals of Column Generation and representing nearly two years of dedicated work, is already a valuable contribution to the community.