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

References

References:
1. Padberg, M.W. "On the facial structure of set packing polyhedral", Mathematical Programming, 5, pp. 199- 215 (1973). DOI: 10.1007/BF01580121.
2. Balas E. "Facets of the knapsack polytope", Mathematical Programming, 8, pp. 146-164 (1975). DOI:10.1007/BF01580440.
3. Wolsey, L.A. "Faces for a linear inequality in 0-1 variables", Mathematical Programming, 8, pp. 165-178 (1975). DOI: 10.1007/BF01580441.
4. Zemel, E. "Lifting the facets of zero-one polytopes", Mathematical Programming, 15, pp. 268-277 (1978). DOI: 10.1007/BF01609032.
5. Zemel, E. "Easily computable facets of the knapsack polytope", Mathematics of Operations Research, 14, pp. 760-764 (1989). DOI: 10.1287/moor.14.4.760.
6. Balas, E. and Zemel, E. "Facets of the knapsack polytope from minimal covers", SIAM Journal on Applied Mathematics, 34, pp. 119-148 (1978). DOI: 10.1137/0134010.
7. Gottlieb, E.S. and Rao, M. "Facets of the knapsack polytope derived from disjoint and overlapping index configurations", Operations Research Letters, 7, pp. 95-100 (1988). DOI: 10.1016/0167-6377(88)90073-9.
8. Escudero, L.F., Garin, A., and Perez, G. "An O(n log n) procedure for identifying facets of the knapsack polytope", Operations Research Letters, 31, pp. 211- 218 (2003). DOI: 10.1016/S0167-6377(02)00221-3.
9. Escudero, L.F., Garin, A., Perez, G. "O(n log n) procedures for tightening cover inequalities", European Journal of Operational Research, 113, pp. 676-687 (1999). DOI: 10.1016/S0377-2217(98)00100-3.
10. Easton, T. and Hooker, K. "Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes", Discrete Optimization, 5, pp. 254-261 (2008). DOI: 10.1016/j.disopt.2007.05.003.
11. Atamturk, A. and Bhardwaj, A. "Supermodular covering knapsack polytope", Discrete Optimization, 18, pp. 74-86 (2015). DOI: 10.1016/j.disopt.2015.07.003.
12. Hickman, R. and Easton, T. "On merging cover inequalities for multiple knapsack problems", Open Journal of Optimization, 4, p. 141 (2015). DOI: 10.4236/ojop.2015.44014.
13. Zhao, M., Huang, K., and Zeng, B. "A polyhedral study on chance constrained program with random right-hand side", Mathematical Programming, 166, pp. 19-64 (2017). DOI: 10.1007/s10107-016-1103-6.
14. Talamantes, A. and Easton, T. "Lifted equailty cuts for the knapsack equality problem", In IIE Annual Conference Proceedings, 1, pp. 1571-1576 (2017).
15. Dey, S.S. and Molinaro, M. "Theoretical challenges towards cutting-plane selection", Mathematical Programming, 170, pp. 237-266 (2018). DOI:10.48550/arXiv.1805.02782.
16. Hojny, C., Gally, T., Habeck, O., et al. "Knapsack polytopes: a survey", Annals of Operations Research, 1, pp. 1-49 (2019).
17. Bienstock, D. and Zuckerberg, M. "Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets", arXiv preprint arXiv:1806.07435(2018). DOI: 10.48550/arXiv.1806.07435.
18. Fischetti, M., Ljubic, I., Monaci, M., et al. "Interdiction games and monotonicity, with application to knapsack problems", INFORMS Journal on Computing, 31, pp. 390-410 (2019). DOI: 10.1287/ijoc.2018.0831.
19. Chen, W.K. and Dai, Y.H. "On the complexity of sequentially lifting cover inequalities for the knapsack polytope", Science China Mathematics, 64, pp. 211- 220 (2021). DOI: 10.1007/s11425-019-9538-1.
20. Abdi, A. and Fukasawa, R. "On the mixing set with a knapsack constraint", Mathematical Programming, 157, pp. 191-217 (2016). DOI: 10.1007/s10107-016- 0979-5.
21. Del Pia, A., Linderoth, J., and Zhu, H., Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets, arXiv preprint arXiv:2106.00301 (2021). DOI: 10.1007/s10107-022-01817-4.
22. Bazzi, A., Fiorini, S., Huang, S., et al. "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). DOI:
10.1137/1.9781611974782.153.
23. Vitor, F. and Easton, T. "Approximate and exact merging of knapsack constraints with cover inequalities", Optimization, 70, pp. 437-460 (2021).
24. Bienstock, D., Faenza, Y., Malinovic, I., et al. "On inequalities with bounded coefficients and pitch for the min knapsack polytope", Discrete Optimization, 1, pp. 100567-100570 (2020). DOI:10.1016/j.disopt.2020.100567.
25. Shim, S., Chopra, S., and Cao, W. "The worst case analysis of strong knapsack facets", Mathematical Programming, 162, pp. 465-493 (2017). DOI: 10.1007/s10107-016-1050-2.
26. Chopra, S., Shim, S., and Steffy, D.E. "A concise characterization of strong knapsack facets", Discrete Applied Mathematics, 1, pp. 136-152 (2019). DOI: 10.1016/j.dam.2018.05.006.
27. Letchford, A.N. and Souli, G. "On lifted cover inequalities: A new lifting procedure with unusual properties", Operations Research Letters, 47, pp. 83-87 (2019). DOI: 10.1016/j.orl.2018.12.005.
28. Letchford, A.N. and Souli, G. "Lifting the knapsack cover inequalities for the knapsack polytope", Operations Research Letters, 48, pp. 607-611 (2020). DOI: 10.1016/j.orl.2020.07.010.
Scientia Iranica
Volume 31, Issue 6 - Serial Number 6
Transactions on Industrial Engineering (E)
March and April 2024
Pages 535-539

Files

History

  • Receive Date: 04 January 2020
  • Revise Date: 02 April 2021
  • Accept Date: 31 January 2022

Share

How to cite

Statistics