[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Knapsack polytopes: a survey

  • Original - Survey or Exposition
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, and connections to independence systems. We also discuss the generalization to (mixed-)integer knapsack polytopes and variants.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. It is easy to construct examples in which \(a^\top x \le \beta \) does not support \(P^{a,\beta }\) (defines a face of dimension \(-1\)), e.g., \(2\, x_1 + 2\, x_2 \le 3\).

  2. We could not access this reference online.

  3. The thesis Ferreira (1994) is cited Ferreira et al. (1996), but we could not access it online.

  4. We could not access Boccia’s article online.

  5. This question has already been posed by Van Vyve and Wolsey (2006).

  6. http://www.ist.tugraz.at/staff/aichholzer/research/rp/rcs/info01poly/.

  7. Johnson and Padberg also treat the related case of \(K_{\mathrm {GUB}}\) with continuous variables.

  8. Note that complementing variables does not necessarily yield a set \(K_{\mathrm {GUB}}\) with the same \(Q_i\).

References

  • Achterberg, T., & Wunderling, R. (2013). Mixed integer programming: Analyzing 12 years of progress. In M. Jünger & G. Reinelt (Eds.), Facets of combinatorial optimization (pp. 449–481). Berlin: Springer.

    Google Scholar 

  • Aichholzer, O. (2000). Extremal properties of 0/1-polytopes of dimension 5. In G. Ziegler & G. Kalai (Eds.), Polytopes—Combinatorics and computation (pp. 111–130). Basel: Birkhäuser.

    Google Scholar 

  • Amado, L., & Barcia, P. (1993). Matroidal relaxations for 0–1 knapsack problems. Operations Research Letters, 14, 147–152.

    Google Scholar 

  • Aráoz, J., Evans, L., Gomory, R. E., & Johnson, E. L. (2003). Cyclic group and knapsack facets. Mathematical Programming, 96, 377–408.

    Google Scholar 

  • Atamtürk, A. (2003). On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming, 98, 145–175.

    Google Scholar 

  • Atamtürk, A. (2005). Cover and pack inequalities for (mixed) integer programming. Annals of Operations Research, 139, 21–38.

    Google Scholar 

  • Avella, P., Boccia, M., & Vasilyev, I. L. (2010). A computational study of exact knapsack separation for the generalized assignment problem. Computational Optimization and Applications, 45, 543–555.

    Google Scholar 

  • Avella, P., Boccia, M., & Vasilyev, I. L. (2013). Computational testing of a separation procedure for the knapsack set with a single continuous variable. INFORMS Journal on Computing, 24, 165–171.

    Google Scholar 

  • Bader, J., Hildebrand, R., Weismantel, R., & Zenklusen, R. (2018). Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix. Mathematical Programming, 169, 565–584.

    Google Scholar 

  • Balas, E. (1975). Facets of the knapsack polytope. Mathematical Programming, 8, 146–164.

    Google Scholar 

  • Balas, E., & Ng, S. M. (1989). On the set covering polytope. I. All the facets with coefficients in \(\{0,1,2\}\). Mathematical Programming, 43, 57–69.

    Google Scholar 

  • Balas, E., & Zemel, E. (1978). Facets of the knapsack polytope from minimal covers. SIAM Journal on Applied Mathematics, 34, 119–148.

    Google Scholar 

  • Balas, E., & Zemel, E. (1984). Lifting and complementing yields all the facets of positive zero–one programming polytopes. In R. Cottle, M. L. Kelmanson, & B. Korte (Eds.), Mathematical programming: Proceedings of the international congress on mathematical programming, Rio de Janeiro, Brazil, 1981 (pp. 13–24). Amsterdam: North-Holland.

    Google Scholar 

  • Bektas, T., & Oğuz, O. (2007). On separating cover inequalities for the multidimensional knapsack problem. Computers & Operations Research, 34, 1771–1776.

    Google Scholar 

  • Bienstock, D. (1996). Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming, 74, 121–140.

    Google Scholar 

  • Bienstock, D. (2008). Approximate formulations for 0–1 knapsack sets. Operations Research Letters, 36, 317–320.

    Google Scholar 

  • Boccia, M. (2006). Using exact knapsack separation for the single-source capacitated facility location problem. Technical Report, Department of Engineering, University of Sannio.

  • Boyd, E. A. (1992). A pseudopolynomial network flow formulation for exact knapsack separation. Networks, 22, 503–514.

    Google Scholar 

  • Boyd, E. A. (1993a). Generating Fenchel cutting planes for knapsack polyhedra. SIAM Journal on Optimization, 3, 734–750.

    Google Scholar 

  • Boyd, E. A. (1993b). Polyhedral results for the precedence-constrained knapsack problem. Discrete Applied Mathematics, 41, 185–201.

    Google Scholar 

  • Boyd, E. A. (1994). Fenchel cutting planes for integer programs. Operations Research, 42, 53–64.

    Google Scholar 

  • Bradley, G. H. (1971). Transformation of integer programs to knapsack problems. Discrete Mathematics, 1, 29–45.

    Google Scholar 

  • Bradley, G. H., Hammer, P. L., & Wolsey, L. A. (1974). Coefficient reduction for inequalities in 0–1 variables. Mathematical Programming, 7, 263–282.

    Google Scholar 

  • Cerdeira, J. O., & Barcia, P. (1995). When is a 0–1 knapsack a matroid? Portugaliae Mathematica, 52, 475–480.

    Google Scholar 

  • Ceria, S., Cordier, C., Marchand, H., & Wolsey, L. A. (1998). Cutting planes for integer programs with general integer variables. Mathematical Programming, 81, 201–214.

    Google Scholar 

  • Chen, W.-K., & Dai, Y.-H. (2019). On the complexity of sequentially lifting cover inequalities for the knapsack polytope. Technical Report 1811.10010v2, arXiv.

  • Chvátal, V., & Hammer, P. L. (1975). Aggregation of inequalities in integer programming. Technical Report, Stanford University, Stanford, CA, USA.

  • Conforti, M., Cornuéjols, G., & Zambelli, G. (2010). Extended formulations in combinatorial optimization. 4OR: A Quarterly Journal of Operations Research, 8, 1–48.

    Google Scholar 

  • Conforti, M., & Laurent, M. (1988). On the facial structure of independence system polyhedra. Mathematics of Operations Research, 13, 543–555.

    Google Scholar 

  • Crowder, H., Johnson, E. L., & Padberg, M. (1983). Solving large-scale zero-one linear programming problems. Operations Research, 31, 803–834.

    Google Scholar 

  • Dahl, G., & Foldnes, N. (2003). Complete description of a class of knapsack polytopes. Operations Research Letters, 31, 335–340.

    Google Scholar 

  • Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5, 266–288.

    Google Scholar 

  • de Farias Jr, I. R., & Nemhauser, G. L. (2003). A polyhedral study of the cardinality constrained knapsack problem. Mathematical Programming, 96, 439–467.

    Google Scholar 

  • Dietrich, B., & Escudero, L. (1992). On tightening cover induced inequalities. European Journal of Operational Research, 60, 335–343.

    Google Scholar 

  • Dyer, M. (2003). Approximate counting by dynamic programming. In: Proceedings of the 35th ACM symposium on theory of computing (pp. 693–699). New York: ACM.

  • Easton, T., & Gutierrez, T. (2015). Sequential lifting of general integer variables for integer programs. Industrial Engineering and Management, 4, 158.

    Google Scholar 

  • Easton, T., & Hooker, K. (2008). Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes. Discrete Optimization, 5, 254–261.

    Google Scholar 

  • Easton, T., Hooker, K., & Lee, E. K. (2003). Facets of the independent set polytope. Mathematical Programming, 98, 177–199.

    Google Scholar 

  • Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1, 127–136.

    Google Scholar 

  • Faenza, Y., & Sanità, L. (2015). On the existence of compact \(\varepsilon \)-approximated formulations for knapsack in the original space. Operations Research Letters, 43, 339–342.

    Google Scholar 

  • Ferreira, C. E. (1994). On combinatorial optimization problems arising in computer systems design. Ph.D. thesis, TU Berlin.

  • Ferreira, C. E., Martin, A., & Weismantel, R. (1996). Solving multiple knapsack problems by cutting planes. SIAM Journal on Optimization, 6, 858–877.

    Google Scholar 

  • Fukasawa, R. (2008). Single-row mixed-integer programs: Theory and computations. Ph.D. thesis, Georgia Institute of Technology.

  • Fukasawa, R., & Goycoolea, M. (2011). On the exact separation of mixed integer knapsack cuts. Mathematical Programming, 128, 19–41.

    Google Scholar 

  • Gabrel, V., & Minoux, M. (2002). A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems. Operations Research Letters, 30, 252–264.

    Google Scholar 

  • Gawrilow, E., & Joswig, M. (2000). polymake: A framework for analyzing convex polytopes. In G. Kalai & G. M. Ziegler (Eds.), Polytopes—Combinatorics and computation (Oberwolfach, 1997). DMV seminars (Vol. 29, pp. 43–73). Basel: Birkhäuser.

    Google Scholar 

  • Geist, D., & Rodin, E. Y. (1992). Adjacency of the 0–1 knapsack problem. Computers & Operations Research, 19, 797–800.

    Google Scholar 

  • Giles, R., & Kannan, R. (1980). A characterization of threshold matroids. Discrete Mathematics, 30, 181–184.

    Google Scholar 

  • Gillmann, R., & Kaibel, V. (2006). Revlex-initial 0/1-polytopes. Journal of Combinatorial Theory, Series A, 113, 799–821.

    Google Scholar 

  • Glover, F. (1973). Unit coefficient inequalities for zero-one programming. Technical Report, University of Colorado.

  • Glover, F., & Sherali, H. D. (2008). Second-order cover inequalities. Mathematical Programming, 114, 207–234.

    Google Scholar 

  • Glover, F., Sherali, H. D., & Lee, Y. (1997). Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming. Computational Optimization and Applications, 8, 151–172.

    Google Scholar 

  • Gokce, E. I., & Wilhelm, W. E. (2015). Valid inequalities for the multi-dimensional multiple-choice 0–1 knapsack problem. Discrete Optimization, 17, 25–54.

    Google Scholar 

  • Gottlieb, E. S., & Rao, M. R. (1988). Facets of the knapsack polytope derived from disjoint and overlapping index configurations. Operations Research Letters, 7, 95–100.

    Google Scholar 

  • Gottlieb, E. S., & Rao, M. R. (1990a). \((1, k)\)-configuration facets for the generalized assignment problem. Mathematical Programming, 46, 53–60.

    Google Scholar 

  • Gottlieb, E. S., & Rao, M. R. (1990b). The generalized assignment problem: Valid inequalities and facets. Mathematical Programming, 46, 31–52.

    Google Scholar 

  • Goycoolea, M. (2006). Cutting planes for large mixed integer programming models. Ph.D. thesis, Georgia Institute of Technology.

  • Gu, Z. (1995). Lifted cover inequalities for 0–1 and mixed 0–1 integer programs. Ph.D. thesis, Georgia Institute of Technology.

  • Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (1998). Lifted cover inequalities for 0–1 integer programs: Computation. INFORMS Journal on Computing, 10, 427–437.

    Google Scholar 

  • Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (1999a). Lifted cover inequalities for 0–1 integer programs: Complexity. INFORMS Journal on Computing, 11, 117–123.

    Google Scholar 

  • Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (1999b). Lifted flow cover inequalities for mixed 0–1 integer programs. Mathematical Programming, 85, 439–467.

    Google Scholar 

  • Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (2000). Sequence independent lifting in mixed integer programming. Journal of Combinatorial Optimization, 4, 109–129.

    Google Scholar 

  • Gupte, A. (2016). Convex hulls of superincreasing knapsacks and lexicographic orderings. Discrete Applied Mathematics, 201, 150–163.

    Google Scholar 

  • Hammer, P. L., Johnson, E. L., & Peled, U. N. (1975). Facet of regular 0–1 polytopes. Mathematical Programming, 8, 179–206.

    Google Scholar 

  • Hammer, P. L., Johnson, E. L., & Peled, U. N. (1977). The role of master polytopes in the unit cube. SIAM Journal on Applied Mathematics, 32, 711–716.

    Google Scholar 

  • Hammer, P. L., & Peled, U. N. (1982). Computing low-capacity 0–1 knapsack polytopes. Zeitschrift für Operations Research, 26, 243–249.

    Google Scholar 

  • Hartmann, M. (1994). Cutting planes and the sequential knapsack problem. Technical Report, TR-94/10, University of North Carolina.

  • Hartvigsen, D., & Zemel, E. (1992). The complexity of lifted inequalities for the knapsack problem. Discrete Applied Mathematics, 39, 113–123.

    Google Scholar 

  • Hayes, A. C., & Larman, D. G. (1982). The vertices of the knapsack polytope. Discrete Applied Mathematics, 6, 135–138.

    Google Scholar 

  • Hickman, R., & Easton, T. (2015a). Merging valid inequalities over the multiple knapsack polyhedron. International Journal of Operational Research, 24, 214–227.

    Google Scholar 

  • Hickman, R., & Easton, T. (2015b). On merging cover inequalities for multiple knapsack problems. Open Journal of Optimization, 4, 141–155.

    Google Scholar 

  • Hoffman, K. L., & Padberg, M. (1991). Improving LP-representations of zero-one linear programs for branch-and-cut. INFORMS Journal on Computing, 3, 121–134.

    Google Scholar 

  • Hojny, C. (2018). Symmetries in binary programs—A polyhedral perspective. Ph.D. thesis, TU Darmstadt.

  • Hojny, C., & Pfetsch, M. E. (2019). Polytopes associated with symmetry handling. Mathematical Programming, 175, 197–240.

    Google Scholar 

  • Hunsaker, B., & Tovey, C. A. (2005). Simple lifted cover inequalities and hard knapsack problems. Discrete Optimization, 2, 219–228.

    Google Scholar 

  • Johnson, E. L., & Padberg, M. W. (1981). A note of the knapsack problem with special ordered sets. Operations Research Letters, 1, 18–22.

    Google Scholar 

  • Kaibel, V. (2011). Extended formulations in combinatorial optimization. Optima, 85, 2–7.

    Google Scholar 

  • Kaibel, V., & Loos, A. (2011). Finding descriptions of polytopes via extended formulations and liftings. In A. R. Mahjoub (Ed.), Progress in combinatorial optimization. Hoboken: Wiley.

    Google Scholar 

  • Kaparis, K., & Letchford, A. N. (2008). Local and global lifted cover inequalities for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 186, 91–103.

    Google Scholar 

  • Kaparis, K., & Letchford, A. N. (2010). Separation algorithms for 0–1 knapsack polytopes. Mathematical Programming, 124, 69–91.

    Google Scholar 

  • Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer.

    Google Scholar 

  • Klabjan, D., Nemhauser, G., & Tovey, C. (1998). The complexity of cover inequality separation. Operations Research Letters, 23, 35–40.

    Google Scholar 

  • Korte, B., & Vygen, J. (2012). Combinatorial optimization. Theory and algorithms, Vol. 21 of Algorithms and Combinatorics. Heidelberg: Springer.

    Google Scholar 

  • Laurent, M. (1989). A generalization of antiwebs to independence systems and their canonical facets. Mathematical Programming, 45, 97–108.

    Google Scholar 

  • Laurent, M., & Sassano, A. (1992). A characterization of knapsacks with the max-flow–min-cut property. Operations Research Letters, 11, 105–110.

    Google Scholar 

  • Lee, E. K. (1997). On facets of knapsack equality polytopes. Journal of Optimization Theory and Applications, 94, 223–239.

    Google Scholar 

  • Lee, K. (2012). Separation heuristic for the rank-1 Chvatal–Gomory inequalities for the binary knapsack problem. Journal of the Korean Institute of Industrial Engineering, 38, 74–79.

    Google Scholar 

  • Letchford, A. N., & Souli, G. (2019). On lifted cover inequalities: A new lifting procedure with unusual properties. Operations Research Letters, 47, 83–87.

    Google Scholar 

  • Loos, A. (2010) Describing orbitopes by linear inequalities and projection based tools. Ph.D. thesis, University of Magdeburg.

  • Loos, A. (2011). Describing orbitopes by linear inequalities and projection based tools. Ph.D. thesis, Universität Magdeburg.

  • Louveaux, Q., & Weismantel, R. (2008). Polyhedral properties for the intersection of two knapsacks. Mathematical Programming, 113, 15–37.

    Google Scholar 

  • Marchand, H., Martin, A., Weismantel, R., & Wolsey, L. (2002). Cutting planes in integer and mixed integer programming. Discrete Applied Mathematics, 123, 397–446.

    Google Scholar 

  • Marchand, H., & Wolsey, L. A. (1999). The 0–1 knapsack problem with a single continuous variable. Mathematical Programming, 85, 15–33.

    Google Scholar 

  • Marchand, H., & Wolsey, L. A. (2001). Aggregation and mixed integer rounding to solve MIPs. Operations Research, 49, 363–371.

    Google Scholar 

  • Marcotte, O. (1985). The cutting stock problem and integer rounding. Mathematical Programming, 33, 82–92.

    Google Scholar 

  • Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Chichester: Wiley.

    Google Scholar 

  • Martin, A. (1998). Integer programs with block structure. Habilitation thesis, TU Berlin.

  • Martin, A., & Weismantel, R. (1997) Contributions to general mixed integer knapsack problems. Technical Report SC-97-38, Zuse Institute Berlin.

  • Martin, A., & Weismantel, R. (1998). The intersection of knapsack polyhedra and extensions. In R. E. Bixby, E. A. Boyd, & R. Z. Ríos-Mercado (Eds.), Integer programming and combinatorial optimization (pp. 243–256). Berlin: Springer.

    Google Scholar 

  • Martin, R. K., Rardin, R. L., & Campbell, B. A. (1990). Polyhedral characterization of discrete dynamic programming. Operations Research, 38, 127–138.

    Google Scholar 

  • Mazur, D. R., & Hall, L. A. (2002). Facets of a polyhedron closely related to the integer knapsack-cover problem. Technical Report, Optimization Online. Retrieved 01, 2019, from http://www.optimization-online.org/DB_FILE/2002/10/542.pdf.

  • Nemhauser, G. L., & Vance, P. H. (1994). Lifted cover facets of the 0–1 knapsack polytope with GUB constraints. Operations Research Letters, 16, 255–263.

    Google Scholar 

  • Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and combinatorial optimization. New York: Wiley.

    Google Scholar 

  • Padberg, M. W. (1975). A note on zero–one programming. Operations Research, 23, 833–837.

    Google Scholar 

  • Padberg, M. W. (1980). \((1, k)\)-configurations and facets for packing problems. Mathematical Programming, 18, 94–99.

    Google Scholar 

  • Papadimitriou, C., & Yannakakis, M. (1984). The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28, 244–259.

    Google Scholar 

  • Papadimitriou, C. H., & Wolfe, D. (1988). The complexity of facets resolved. Journal of Computer and System Sciences, 37, 2–13.

    Google Scholar 

  • Park, K., & Lee, K. (2011). On the separation of the rank-1 Chvatal–Gomory inequalities for the fixed-charge 0–1 knapsack polytope. Journal of the Korean OR/MS Society, 36, 43–50.

    Google Scholar 

  • Park, K., & Park, S. (1997). Lifting cover inequalities for the precedence-constrained knapsack problem. Discrete Applied Mathematics, 72, 219–241.

    Google Scholar 

  • Peled, U. N. (1977). Properties of facets of binary polytopes. In P. Hammer, E. Johnson, B. Korte, & G. Nemhauser (Eds.), Studies in integer programming, Vol. 1 of Annals of Discrete Mathematics (pp. 435–456). Amsterdam: Elsevier.

    Google Scholar 

  • Pochet, Y., & Weismantel, R. (1998). The sequential knapsack polytope. SIAM Journal on Optimization, 8, 248–264.

    Google Scholar 

  • Pochet, Y., & Wolsey, L. A. (1995). Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation. Discrete Applied Mathematics, 59, 57–74.

    Google Scholar 

  • Pokutta, S., & Vyve, M. V. (2013). A note on the extension complexity of the knapsack polytope. Operations Research Letters, 41, 347–350.

    Google Scholar 

  • Richard, J.-P. P., de Farias Jr, I. R., & Nemhauser, G. L. (2003a). Lifted inequalities for 0–1 mixed integer programming: Basic theory and algorithms. Mathematical Programming, 98, 89–113.

    Google Scholar 

  • Richard, J.-P. P., de Farias Jr, I. R., & Nemhauser, G. L. (2003b). Lifted inequalities for 0–1 mixed integer programming: Superlinear lifting. Mathematical Programming, 98, 115–143.

    Google Scholar 

  • Roy, T. J. V., & Wolsey, L. A. (1986). Valid inequalities for mixed 0–1 programs. Discrete Applied Mathematics, 14, 199–213.

    Google Scholar 

  • Sassano, A. (1989). On the facial structure of the set covering polytope. Mathematical Programming, 44, 181–202.

    Google Scholar 

  • Schrijver, A. (1986). Theory of linear and integer programming. Chichester: Wiley.

    Google Scholar 

  • Sherali, H. D., & Glover, F. (2008). Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities. Discrete Optimization, 5, 270–289.

    Google Scholar 

  • Sherali, H. D., & Lee, Y. (1995). Sequential and simultaneous liftings of minimal cover inequalities for generalized upper bound constrained knapsack polytopes. SIAM Journal on Discrete Mathematics, 8, 133–153.

    Google Scholar 

  • Shim, S., Chopra, S., & Cao, W. (2017). The worst case analysis of strong knapsack facets. Mathematical Programming, 162, 465–493.

    Google Scholar 

  • Stallaert, J. I. (1997). The complementary class of generalized flow cover inequalities. Discrete Applied Mathematics, 77, 73–80.

    Google Scholar 

  • Trick, M. A. (1992). A linear relaxation heuristic for the generalized assignment problem. Naval Research Logistics (NRL), 39, 137–151.

    Google Scholar 

  • Tyber, S., & Johnson, E. L. (2010). A polyhedral study of the mixed integer cut. In F. Eisenbrand & F. B. Shepherd (Eds.), Integer programming and combinatorial optimization (pp. 124–134). Berlin: Springer.

    Google Scholar 

  • van de Leensel, R. L. M. J., van Hoesel, C. P. M., & van de Klundert, J. J. (1999). Lifting valid inequalities for the precedence constrained knapsack problem. Mathematical Programming, 86, 161–185.

    Google Scholar 

  • Van Vyve, M., & Wolsey, L. A. (2006). Approximate extended formulations. Mathematical Programming, 105, 501–522.

    Google Scholar 

  • Vasilyev, I. L. (2009). A cutting plane method for knapsack polytope. Journal of Computer and Systems Sciences International, 48, 70–77.

    Google Scholar 

  • Vasilyev, I. L., Boccia, M., & Hanafi, S. (2016). An implementation of exact knapsack separation. Journal of Global Optimization, 66, 127–150.

    Google Scholar 

  • Weismantel, R. (1996). Hilbert bases and the facets of special knapsack polytopes. Mathematics of Operations Research, 21, 886–904.

    Google Scholar 

  • Weismantel, R. (1997). On the 0/1 knapsack polytope. Mathematical Programming, 77, 49–68.

    Google Scholar 

  • Wolsey, L. A. (1975). Faces for a linear inequality in 0–1 variables. Mathematical Programming, 8, 165–178.

    Google Scholar 

  • Wolsey, L. A. (1976a). Technical note—Facets and strong valid inequalities for integer programs. Operations Research, 24, 367–372.

    Google Scholar 

  • Wolsey, L. A. (1976b). Technical note—Facets and strong valid inequalities for integer programs. Operations Research, 24, 367–372.

    Google Scholar 

  • Wolsey, L. A. (1977). Valid inequalities and superadditivity for 0–1 integer programs. Mathematics of Operations Research, 2, 66–77.

    Google Scholar 

  • Wolsey, L. A. (1990). Valid inequalities for 0–1 knapsacks and MIPs with generalised upper bound constraints. Discrete Applied Mathematics, 29, 251–261.

    Google Scholar 

  • Wolter, K. (2006). Implementation of cutting plane separators for mixed integer programs. Diploma thesis, TU Berlin. Retrieved 01, 2019, from https://www.zib.de/groetschel/students/Diplom-Wolter-2006.pdf.

  • Yaman, H. (2007). The integer knapsack cover polyhedron. SIAM J. Discrete Math., 21, 551–572.

    Google Scholar 

  • Yan, X.-Q., & Boyd, E. A. (1998). Cutting planes for mixed-integer knapsack polyhedra. Mathematical Programming, 81, 257–262.

    Google Scholar 

  • Zemel, E. (1978). Lifting the facets of zero-one polytopes. Mathematical Programming, 15, 268–277.

    Google Scholar 

  • Zemel, E. (1989). Easily computable facets of the knapsack polytope. Mathematics of Operations Research, 14, 760–765.

    Google Scholar 

  • Zeng, B., & Richard, J.-P. P. (2011a). A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting. Discrete Optimization, 8, 277–301.

    Google Scholar 

  • Zeng, B., & Richard, J.-P. P. (2011b). A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting. Discrete Optimization, 8, 259–276.

    Google Scholar 

Download references

Acknowledgements

We thank two anonymous referees for pointing out additional references as well as useful comments that helped to improve the paper’s structure. The authors also thank Oswin Aichholzer for making his code for accessing all equivalence classes of 0/1 polytopes in small dimensions available. Moreover, we thank Andreas Paffenholz for providing code to test whether a 0/1 polytope is a knapsack polytope as well as Michel Reiffert for fruitful discussions.

Funding

Funding was provided by DFG (SFB 666, SFB 805, TRR 154, SPP 1798).

Author information

Authors and Affiliations

  1. Discrete Optimization Group, Department of Mathematics, Technische Universität Darmstadt, Dolivostr. 15, 64293, Darmstadt, Germany

    Christopher Hojny, Tristan Gally, Oliver Habeck, Hendrik Lüthen, Frederic Matter, Marc E. Pfetsch & Andreas Schmitt

Authors
  1. Christopher Hojny
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tristan Gally
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Oliver Habeck
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hendrik Lüthen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Frederic Matter
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Marc E. Pfetsch
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Andreas Schmitt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marc E. Pfetsch.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hojny, C., Gally, T., Habeck, O. et al. Knapsack polytopes: a survey. Ann Oper Res 292, 469–517 (2020). https://doi.org/10.1007/s10479-019-03380-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-019-03380-2

Keywords

Search

Navigation