The Dantzig-Wolfe Decomposition Algorithm

Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice-Hall.

Augerat, P., Belenguer, J. M., Benavent, E., Corberán, A., Naddef, D., and Rinaldi, G. (1995). Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem. Technical Report 949-M, Université Joseph Fourier, Grenoble.

Aykanat, C., Pinar, A., and Çatalyürek, Ü. V. (2004). “Permuting Sparse Rectangular Matrices into Block-Diagonal Form.” SIAM Journal on Scientific Computing 25:1860–1879.

Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., and Vance, P. H. (1998). “Branch-and-Price: Column Generation for Solving Huge Integer Programs.” Operations Research 46:316–329.

Caprara, A., Furini, F., and Malaguti, E. (2010). Exact Algorithms for the Temporal Knapsack Problem. Technical Report OR-10-7, Department of Electronics, Computer Science, and Systems, University of Bologna.

CNN (2012). “Record Kidney Transplant Chain.” CNN Health. Video. Accessed April 2, 2019. https://www.cnn.com/videos/health/2012/02/20/dnt-kidney-transplant-chain.wls.

Dantzig, G. B., and Wolfe, P. (1960). “Decomposition Principle for Linear Programs.” Operations Research 8:101–111. https://www.jstor.org/stable/167547.

Galati, M. V. (2009). “Decomposition in Integer Linear Programming.” Ph.D. diss., Lehigh University.

Gamrath, G. (2010). “Generic Branch-Cut-and-Price.” Diploma thesis, Technische Universität Berlin.

Grcar, J. F. (1990). Matrix Stretching for Linear Equations. Technical Report SAND90-8723, Sandia National Laboratories.

Khaniyev, T., Elhedhli, S., and Erenay, F. S. (2018). “Structure Detection in Mixed-Integer Programs.” INFORMS Journal on Computing 30:570–587.

Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R. E., Danna, E., et al. (2011). “MIPLIB 2010: Mixed Integer Programming Library Version 5.” Mathematical Programming Computation 3:103–163. https://link.springer.com/article/10.1007/s12532-011-0025-9.

Ralphs, T. K., and Galati, M. V. (2006). “Decomposition and Dynamic Cut Generation in Integer Linear Programming.” Mathematical Programming 106:261–285. http://dx.doi.org/10.1007/S10107-005-0606-3.

Vanderbeck, F., and Savelsbergh, M. W. P. (2006). “A Generic View of Dantzig-Wolfe Decomposition in Mixed Integer Programming.” Operations Research Letters 34:296–306. http://dx.doi.org/10.1016/j.orl.2005.05.009.