IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v292y2020i1d10.1007_s10479-019-03380-2.html
   My bibliography  Save this article

Knapsack polytopes: a survey

Author

Listed:
  • Christopher Hojny

    (Technische Universität Darmstadt)

  • Tristan Gally

    (Technische Universität Darmstadt)

  • Oliver Habeck

    (Technische Universität Darmstadt)

  • Hendrik Lüthen

    (Technische Universität Darmstadt)

  • Frederic Matter

    (Technische Universität Darmstadt)

  • Marc E. Pfetsch

    (Technische Universität Darmstadt)

  • Andreas Schmitt

    (Technische Universität Darmstadt)

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.

Suggested Citation

  • Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    • Handle: RePEc:spr:annopr:v:292:y:2020:i:1:d:10.1007_s10479-019-03380-2
    DOI: 10.1007/s10479-019-03380-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03380-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-019-03380-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Eitan Zemel, 1989. "Easily Computable Facets of the Knapsack Polytope," Mathematics of Operations Research, INFORMS, vol. 14(4), pages 760-764, November.
    2. Robert Weismantel, 1996. "Hilbert Bases and the Facets of Special Knapsack Polytopes," Mathematics of Operations Research, INFORMS, vol. 21(4), pages 886-904, November.
    3. DE FARIAS, Ismael R. & NEMHAUSER, Georges L., 2003. "A polyhedral study of the cardinality constrained knapsack problem," LIDAM Reprints CORE 1634, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. MARCHAND, Hugues & WOLSEY, Laurence A., 2001. "Aggregation and mixed integer rounding to solve mips," LIDAM Reprints CORE 1513, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. POCHET, Yves & WEISMANTEL, Robert, 1998. "The sequential knapsack polytope," LIDAM Reprints CORE 1313, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Pasquale Avella & Maurizio Boccia & Igor Vasilyev, 2010. "A computational study of exact knapsack separation for the generalized assignment problem," Computational Optimization and Applications, Springer, vol. 45(3), pages 543-555, April.
    7. Karla L. Hoffman & Manfred Padberg, 1991. "Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 121-134, May.
    8. MARCHAND, Hugues & MARTIN, Alexander & WEISMANTEL, Robert & WOLSEY, Laurence, 2002. "Cutting planes in integer and mixed integer programming," LIDAM Reprints CORE 1567, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. E. K. Lee, 1997. "On Facets of Knapsack Equality Polytopes," Journal of Optimization Theory and Applications, Springer, vol. 94(1), pages 223-239, July.
    10. Dietrich, B. L. & Escudero, L. F., 1992. "On tightening cover induced inequalities," European Journal of Operational Research, Elsevier, vol. 60(3), pages 335-343, August.
    11. Zonghao Gu & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Sequence Independent Lifting in Mixed Integer Programming," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 109-129, March.
    12. Hsieh, Yu-Wei & Shi, Xiaoxia & Shum, Matthew, 2022. "Inference on estimators defined by mathematical programming," Journal of Econometrics, Elsevier, vol. 226(2), pages 248-268.
    13. Harlan Crowder & Ellis L. Johnson & Manfred Padberg, 1983. "Solving Large-Scale Zero-One Linear Programming Problems," Operations Research, INFORMS, vol. 31(5), pages 803-834, October.
    14. Pochet, Y. & Wolsey, L. A., 1995. "Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation," LIDAM Reprints CORE 1149, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. VAN VYVE, Matthieu & WOLSEY, Laurence A., 2006. "Approximate extended formulations," LIDAM Reprints CORE 1807, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Randal Hickman & Todd Easton, 2015. "Merging valid inequalities over the multiple knapsack polyhedron," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 24(2), pages 214-227.
    17. Kaparis, Konstantinos & Letchford, Adam N., 2008. "Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 186(1), pages 91-103, April.
    18. E. Andrew Boyd, 1994. "Fenchel Cutting Planes for Integer Programs," Operations Research, INFORMS, vol. 42(1), pages 53-64, February.
    19. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    20. CERIA, Sebastian & CORDIER, Cécile & MARCHAND, Hugues & WOLSEY, Laurence A., 1998. "Cutting planes for integer programs with general integer variables," LIDAM Reprints CORE 1334, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    21. R. Kipp Martin & Ronald L. Rardin & Brian A. Campbell, 1990. "Polyhedral Characterization of Discrete Dynamic Programming," Operations Research, INFORMS, vol. 38(1), pages 127-138, February.
    22. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    23. Michele Conforti & Monique Laurent, 1988. "On the Facial Structure of Independence System Polyhedra," Mathematics of Operations Research, INFORMS, vol. 13(4), pages 543-555, November.
    24. Michael A. Trick, 1992. "A linear relaxation heuristic for the generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 137-151, March.
    25. repec:spr:pharme:v:21:y:2003:i:12:p:839-851 is not listed on IDEAS
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wei-Kun Chen & Liang Chen & Yu-Hong Dai, 2023. "Lifting for the integer knapsack cover polyhedron," Journal of Global Optimization, Springer, vol. 86(1), pages 205-249, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alper Atamtürk, 2005. "Cover and Pack Inequalities for (Mixed) Integer Programming," Annals of Operations Research, Springer, vol. 139(1), pages 21-38, October.
    2. Wei-Kun Chen & Liang Chen & Yu-Hong Dai, 2023. "Lifting for the integer knapsack cover polyhedron," Journal of Global Optimization, Springer, vol. 86(1), pages 205-249, May.
    3. Santanu S. Dey & Jean-Philippe Richard, 2009. "Linear-Programming-Based Lifting and Its Application to Primal Cutting-Plane Algorithms," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 137-150, February.
    4. Wei-Kun Chen & Liang Chen & Mu-Ming Yang & Yu-Hong Dai, 2018. "Generalized coefficient strengthening cuts for mixed integer programming," Journal of Global Optimization, Springer, vol. 70(1), pages 289-306, January.
    5. Xiaoyi Gu & Santanu S. Dey & Jean-Philippe P. Richard, 2024. "Solving Sparse Separable Bilinear Programs Using Lifted Bilinear Cover Inequalities," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 884-899, May.
    6. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    7. Zonghao Gu & George L. Nemhauser & Martin W. P. Savelsbergh, 1999. "Lifted Cover Inequalities for 0-1 Integer Programs: Complexity," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 117-123, February.
    8. Tobias Achterberg & Robert E. Bixby & Zonghao Gu & Edward Rothberg & Dieter Weninger, 2020. "Presolve Reductions in Mixed Integer Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 473-506, April.
    9. Robert Bixby & Edward Rothberg, 2007. "Progress in computational mixed integer programming—A look back from the other side of the tipping point," Annals of Operations Research, Springer, vol. 149(1), pages 37-41, February.
    10. Agostinho Agra & Cristina Requejo & Eulália Santos, 2016. "Implicit cover inequalities," Journal of Combinatorial Optimization, Springer, vol. 31(3), pages 1111-1129, April.
    11. R. Lougee-Heimer & W. Adams, 2005. "A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs," Annals of Operations Research, Springer, vol. 139(1), pages 289-320, October.
    12. Patrick Gemander & Wei-Kun Chen & Dieter Weninger & Leona Gottwald & Ambros Gleixner & Alexander Martin, 2020. "Two-row and two-column mixed-integer presolve using hashing-based pairing methods," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 205-240, October.
    13. Amitabh Basu & Pierre Bonami & Gérard Cornuéjols & François Margot, 2011. "Experiments with Two-Row Cuts from Degenerate Tableaux," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 578-590, November.
    14. Quentin Louveaux & Laurence Wolsey, 2007. "Lifting, superadditivity, mixed integer rounding and single node flow sets revisited," Annals of Operations Research, Springer, vol. 153(1), pages 47-77, September.
    15. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.
    16. Richard Laundy & Michael Perregaard & Gabriel Tavares & Horia Tipi & Alkis Vazacopoulos, 2009. "Solving Hard Mixed-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 304-313, May.
    17. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    18. Shanshan Wang & Jinlin Li & Sanjay Mehrotra, 2021. "Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1661-1677, October.
    19. Escudero, L. F. & Garin, A. & Perez, G., 1999. "O(n log n) procedures for tightening cover inequalities," European Journal of Operational Research, Elsevier, vol. 113(3), pages 676-687, March.
    20. Alper Atamtürk, 2004. "Sequence Independent Lifting for Mixed-Integer Programming," Operations Research, INFORMS, vol. 52(3), pages 487-490, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:292:y:2020:i:1:d:10.1007_s10479-019-03380-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.