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 ProblemGeneralized 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
- 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, University of Bologna, Department of Electronics, Computer Science, and Systems.
-
Dantzig, G. B. and Wolfe, P. (1960), “Decomposition Principle for Linear Programs,” Operations Research, 8, 101–111.
URL 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. D., 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.
URL 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.
-
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.
-
Willingham, V. (2009), “Massive Transplant Effort Pairs 13 Kidneys to 13 Patients,” CNN Health, http://www.cnn.com/2009/HEALTH/12/14/kidney.transplant/index.html, accessed March 16, 2011.