2,305
Views
2
CrossRef citations to date
0
Altmetric
Research Article

Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm

& | (Reviewing Editor)
Article: 1162372 | Received 20 Oct 2015, Accepted 27 Feb 2016, Published online: 31 Mar 2016

References

  • Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch and price column generation for solving huge integer programs. Operations Research, 46, 316–329.
  • Barnhart, C., Hane, C. A., & Vance, P. H. (2010). Using branch-and-price-and-cut to solve origin--destination integer multicommodity flow problems. Operations Research, 48, 318–326.
  • Bealie, E. M. L. (1979). Branch and bound methods for mathematical programming systems. Annals of Discrete Mathematics, 5, 201–219.
  • Beasley, J. E. (Ed.). (1996). Advances in linear and integer programming. New York, NY: Oxford University Press.
  • Benders, J. F. (1962). Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 4, 238–252.
  • Brunetta, L., Conforti, M., & Rinaldi, G. (1997). A branch and cut algorithm for the equicut problem. Mathematical Programming, 78, 243–263.
  • Chinneck, J. W. (2004). Practical optimization: A gentle introduction lecture notes. Retrieved from http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf
  • Dakin, R. J. (1965). A tree search algorithm for mixed integer programming problems. The Computer Journal, 8, 250–255.
  • Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragao, M., Uchoa, E., & Werneck, R. F. (2006). Robust branch-and-cut-price for the capacitated vehicle routing problem. Mathematical Programming Series A, 106, 491–511.
  • Kumar, S., Munapo, E., & Jones, B. C. (2007). An integer equation controlled descending path to a protean pure integer program. Indian Journal of Mathematics, 49, 211–237.
  • Land, A. H., & Doig, A. G. (1960). An automatic method for solving discrete programming problems. Econometrica, 28, 497–520.
  • Ladanyi, L., Ralphs, T. K., & Trotter, L. E. (2001). Branch, cut and price: Sequential and parallel. In N. Naddef & M. Jenger (Eds.), Computational combinatorial optimization (p. 223–260). Berlin: Springer.
  • Mitchell, J. E., & Lee, E. K. (2001). Branch and bound methods for integer programming. In C. A. Floudas & P. M. Pardalos (Eds.), Encyclopedia of optimization. Dordrecht: Kluwer Academic Publishers.
  • Mitchell, J. E. (2001). Branch and cut algorithms for integer programming. In C. A. Floudas & P. M. Pardalos (Eds.), Encyclopedia of optimization. Kluwer Academic Publishers.
  • Padberg, M., & Rinaldi, G. (1991). A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33, 60–100.
  • Savelsbergh, M. W. P. (1994). Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6, 445–454.
  • Salvelsbergh, M. W. P. (1997). A branch and price algorithm to solve the generalized assignment problem. Operations Research, 45, 381–841.
  • Taha, H. A. (2004). Operations research: An introduction (7th ed.).Upper Saddle River, NJ: Pearson Educators.
  • Winston, W. L. (2004). Operations research applications and algorithms (4th ed.).Belmont, CA: Duxbury Press.