A very fast method for guaranteed generation of one facet for 0-1 knapsack polyhedron

Document Type : Research Note

Authors

1 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

2 Department of Industrial and Systems Engineering, Texas A&M University, College Station,TX, 77843-3131

Abstract

The 0-1 knapsack polyhedron as the most basic relaxation of a 0-1 integer program has attracted attention of many researchers over the years.We present a very fast method that is guaranteed to generate one facet for the 0-1 knapsack polyhedron. Unlike lifting of cover inequlities, our method does not require an initial minimal cover or a predetermined lifting sequencing, and its worst-case complexity is linear in number of variables. Therefore, it is suitable for incorporation into mixed interger programming(MIP) solvers, in order to generate, with negligible computational burden, one strong cut based on any 0-1 knapsack relaxation of a general MIP.

Keywords


  1. Padberg M.W. “On the facial structure of set packing polyhedral”, Mathematical programming, 5, pp. 199-215 (1973).
  2. Balas E. “Facets of the knapsack polytope”, Mathematical programming, 8, pp. 146-164 (1975).
  3. Wolsey LA. “Faces for a linear inequality in 0–1 variables”, Mathematical Programming, 8, pp. 165-178 (1975).
  4. Zemel E. “Lifting the facets of zero–one polytopes”, Mathematical Programming, 15, pp. 268-277 (1978).
  5. Zemel E. “Easily computable facets of the knapsack polytope”, Mathematics of Operations Research, 14, pp. 760-764 (1989).
  6. Balas E, Zemel E. “Facets of the knapsack polytope from minimal covers”, SIAM Journal on Applied Mathematics, 34, pp. 119-148 (1978).
  7. Gottlieb E.S, Rao M. “Facets of the knapsack polytope derived from disjoint and overlapping index configurations”, Operations research letters, 7, pp. 95-100 (1988).
  8. Escudero L.F, Garı́n A, Pérez G. “An o (n log n) procedure for identifying facets of the knapsack polytope” Operations Research Letters, 31, pp. 211-218 (2003).
  9. Escudero L.F, Garı́n A, Pérez G. “O (n log n) procedures for tightening cover inequalities”, European journal of operational research, 113, pp. 676-687 (1999).
  10. Easton T, Hooker K. “Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes”, Discrete Optimization, 5, pp. 254-261 (2008).
  11. Atamtürk, A., & Bhardwaj, A. “Supermodular covering knapsack polytope”, Discrete Optimization, 18, pp. 74-86 (2015).
  12. Hickman, R., & Easton, T. “On Merging Cover Inequalities for Multiple Knapsack Problems”, Open Journal of Optimization, 4, pp. 141 (2015).
  13. Zhao, M., Huang, K., & Zeng, B. “A polyhedral study on chance constrained program with random right-hand side”, Mathematical Programming, 166, pp. 19-64 (2017).
  14. Talamantes, A., & Easton, T. “Lifted Equailty Cuts for the Knapsack Equality Problem”, In IIE Annual Conference Proceedings,1, pp. 1571-1576 (2017).
  15. Dey, S. S., & Molinaro, M. “Theoretical challenges towards cutting-plane selection”, Mathematical Programming, 170, pp. 237-266 (2018).
  16. Hojny, C., Gally, T., Habeck, O., Lüthen, H., Matter, F., Pfetsch, M. E., & Schmitt, A. “Knapsack polytopes: a survey”, Annals of Operations Research, 1, pp. 1-49 (2019).
  17. Bienstock, D., & Zuckerberg, M. “Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets”, arXiv preprint arXiv:1806.07435 (2018).
  18. Fischetti, M., Ljubić, I., Monaci, M., & Sinnl, M. “Interdiction games and monotonicity, with application to knapsack problems”, INFORMS Journal on Computing, 31, pp. 390-410 (2019).
  19. Chen, W. K., & Dai, Y. H. “On the complexity of sequentially lifting cover inequalities for the knapsack polytope”, Science China Mathematics, 64, pp. 211-220 (2021).
  20. Abdi, A., & Fukasawa, R. “On the mixing set with a knapsack constraint”, Mathematical Programming, 157, pp. 191-217 (2016).
  21. Del Pia, A., Linderoth, J., & Zhu, H. “Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets”. arXiv preprint arXiv:2106.00301 (2021).
  22. Bazzi, A., Fiorini, S., Huang, S., & Svensson, O. “Small extended formulation for knapsack cover inequalities from monotone circuits”, In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1, pp. 2326-2341(2017).
  23. Vitor, F., & Easton, T. “Approximate and exact merging of knapsack constraints with cover inequalities”, Optimization, 70, pp. 437-460 (2021).
  24. Bienstock, D., Faenza, Y., Malinović, I., Mastrolilli, M., Svensson, O., & Zuckerberg, M. “On inequalities with bounded coefficients and pitch for the min knapsack polytope”, Discrete Optimization, 1, pp. 100567-100570 (2020).
  25. Shim, S., Chopra, S., & Cao, W. “The worst case analysis of strong knapsack facets”, Mathematical Programming, 162, pp. 465-493 (2017).
  26. Chopra, S., Shim, S., & Steffy, D. E. “A concise characterization of strong knapsack facets”, Discrete Applied Mathematics, 1, pp. 136-152 (2019).
  27. Letchford, A. N., & Souli, G. “On lifted cover inequalities: A new lifting procedure with unusual properties”, Operations Research Letters, 47, pp. 83-87 (2019).
  28. Letchford, A. N., & Souli, G. “Lifting the knapsack cover inequalities for the knapsack polytope”, Operations Research Letters, 48, pp. 607-611 (2020).