The Decomposition Algorithm
- Overview
-
Getting Started
-
SyntaxDecomposition Algorithm Options in the PROC OPTLP Statement or the SOLVE WITH LP Statement in PROC OPTMODELDecomposition Algorithm Options in the PROC OPTMILP Statement or the SOLVE WITH MILP Statement in PROC OPTMODELDECOMP StatementDECOMP_MASTER StatementDECOMP_MASTER_IP StatementDECOMP_SUBPROB Statement
-
Details
-
ExamplesMulticommodity Flow Problem and METHOD=NETWORKGeneralized Assignment ProblemBlock-Diagonal Structure and METHOD=CONCOMP in Single-Machine ModeBlock-Diagonal Structure and METHOD=CONCOMP in Distributed ModeBlock-Angular Structure and METHOD=AUTOBin Packing ProblemResource Allocation ProblemVehicle Routing ProblemATM Cash Management in Single-Machine ModeATM Cash Management in Distributed ModeKidney Donor Exchange and METHOD=SET
- References
References
-
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.
-
Dantzig, G. B., and Wolfe, P. (1960). “Decomposition Principle for Linear Programs.” Operations Research 8:101–111. http://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.
-
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R. E., Danna, E., Gamrath, G., Gleixner, A. M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D. E., and Wolter, K. (2011). “MIPLIB 2010.” Mathematical Programming Computation 3:103–163. 10.1007/s12532-011-0025-9. http://mpc.zib.de/index.php/MPC/article/view/56/28.
-
Ralphs, T. K., and Galati, M. V. (2006). “Decomposition and Dynamic Cut Generation in Integer Linear Programming.” Mathematical Programming 106:261–285. 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. 10.1016/j.orl.2005.05.009.
-
Willingham, V. (2009). “Massive Transplant Effort Pairs 13 Kidneys to 13 Patients.” CNN Health. Accessed March 16, 2011. http://www.cnn.com/2009/HEALTH/12/14/kidney.transplant/index.html.