The Decomposition Algorithm

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.

  • 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.

  • 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.