Knapsack polytopes: a survey
Author
Abstract
Suggested Citation
DOI: 10.1007/s10479-019-03380-2
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- 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).
- Eitan Zemel, 1989. "Easily Computable Facets of the Knapsack Polytope," Mathematics of Operations Research, INFORMS, vol. 14(4), pages 760-764, November.
- 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).
- Robert Weismantel, 1996. "Hilbert Bases and the Facets of Special Knapsack Polytopes," Mathematics of Operations Research, INFORMS, vol. 21(4), pages 886-904, November.
- 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.
- 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.
- E. Andrew Boyd, 1994. "Fenchel Cutting Planes for Integer Programs," Operations Research, INFORMS, vol. 42(1), pages 53-64, February.
- 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).
- George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
- 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).
- 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).
- POCHET, Yves & WEISMANTEL, Robert, 1998. "The sequential knapsack polytope," LIDAM Reprints CORE 1313, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- 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.
- 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.
- 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).
- E. K. Lee, 1997. "On Facets of Knapsack Equality Polytopes," Journal of Optimization Theory and Applications, Springer, vol. 94(1), pages 223-239, July.
- 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.
- Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
- 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.
- 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.
- 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.
- 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.
- Yu-Wei Hsieh & Xiaoxia Shi & Matthew Shum, 2017. "Inference on Estimators defined by Mathematical Programming," Papers 1709.09115, arXiv.org.
- 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.
- 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.
- repec:spr:pharme:v:21:y:2003:i:12:p:839-851 is not listed on IDEAS
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- 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.- Alper Atamtürk, 2005. "Cover and Pack Inequalities for (Mixed) Integer Programming," Annals of Operations Research, Springer, vol. 139(1), pages 21-38, October.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Agostinho Agra & Cristina Requejo & Eulália Santos, 2016. "Implicit cover inequalities," Journal of Combinatorial Optimization, Springer, vol. 31(3), pages 1111-1129, April.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
- 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.
- 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.
- Alper Atamtürk, 2004. "Sequence Independent Lifting for Mixed-Integer Programming," Operations Research, INFORMS, vol. 52(3), pages 487-490, June.
More about this item
Keywords
Knapsack polytope; Cover inequality; Lifting; Separation problem; Complete linear description; Independence systems;All these keywords.
Statistics
Access and download statisticsCorrections
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.