More Web Proxy on the site http://driver.im/

article

Easily Computable Facets of the Knapsack Polytope

Author:

Eitan ZemelAuthors Info & Claims

Mathematics of Operations Research, Volume 14, Issue 4

Pages 760 - 764

https://doi.org/10.1287/moor.14.4.760

Published: 01 November 1989 Publication History

Abstract

It is known that facets and valid inequalities for the knapsack polytope P can be obtained by lifting a simple inequality derived from each minimal cover. We study the computational complexity of such lifting. In particular, we show that the task of computing a lifted facet can be accomplished in Ons where s ≤ n is the cardinality of the minimal cover. Also, for a lifted inequality with integer coefficients, we show that the dual tasks of recognizing whether the inequality is valid for P or is a facet of P can be done within the same time bound.

References

[1]

Balas, E. (1975). Facets of the Knapsack Polytope. Math. Programming 8 146-164.

Digital Library

[2]

Balas, E. and Zemel, E. (1978). Facets of the Knapsack Polytope from Minimal Covers, SIAM J. Appl. Math. 34, 1 119-148.

Digital Library

[3]

Balas, E. and Zemel, E. (1984). Lifting and Complementing Yields all the Facets of Positive Zero-One Programming Polytopes. R. W. Cottle, H. L. Kelmanson, and B. Korte (Eds), Mathematical Programming. Elsevier Science Publishers. North Holland, Amsterdam.

[4]

Crowder, H., Johnson, E. L. and Padberg, M. (1983). Solving Large Scale Zero-One Linear Programming Problems. Oper. Res. 5 803-834.

[5]

Grotschel, M. (1985). Polyhedral Combinatorics. M. O'hEigeartaigh, J. K. Lenstra and A. H. G. Rinnooy Kan (Eds.), Combinatorial Optimization--Annotated Bibliographies. Wiley (Interscience Publication), New York.

[6]

Grotschel, M. and Padberg, M. W. (1985). Polyhedral Algorithms. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (Eds.), The Travelling Salesman Problem. Wiley, Chichester.

[7]

Hammer, P. L., Johnson, E. L. and Peled, U. N. (1975). Facets or Regular 0-1 Polytopes. Math. Programming 8 179-206.

Digital Library

[8]

Hartvigsen, D. and Zemel, E. (1987). On the Computational Complexity of Lifted Inequalities for the Knapsack Problem. Northwestern University working paper.

[9]

Nemhauser, G. L. and Trotter, Jr., L. E. (1974). Properties of Vertex Packing and Independence System Polyhedra. Math. Programming 6 48-61.

Digital Library

[10]

Padberg, M. W. (1973). On the Facial Structure of Set Packing Polyhedra. Math Programming 5 198-216.

Digital Library

[11]

Padberg, M. W. (1975). A Note on Zero-One Programming. Oper. Res. 3 833-837.

[12]

Papadimitriou, C. H. and Wolfe, D. (1985). The Complexity of Facets Resolved. 26th Annual Sympos. Foundations Computer Sci., Portland, OR, October, 74-78.

[13]

Papadimitriou, C. H. and Yananakis, M. (1982). The Complexity of Facets (and Some Facets of Complexity). J. Comput. System Sci. 2 244-259.

[14]

Peled, U. N. (1977). Properties of Facets of Binary Polytopes. Ann. Discrete Math. 1 435-456.

[15]

Pollatschek, M. A., (1970). Algorithms for Weighted Graphs. PH.D thesis. Technion-Israel Institute of Technology.

[16]

Pulleyblank, W. R. (1982). Polyhedral Combinatorics. A. Bachem. M. Grotschel, B. Korte (Eds). Mathematical Programming: The Stale of the Art. Bonn. Springer, Berlin.

[17]

Wolsey, L. A. (1975). Faces of Linear Inequalities in 0-1 Variables. Math. Programming 8 165-178.

Digital Library

[18]

Zemel, E. (1978). Lifting the Facets of 0-1 Polytopes. Math. Programming 15 268-277.

Digital Library

Cited By

Chen WChen LDai Y(2022)Lifting for the integer knapsack cover polyhedronJournal of Global Optimization10.1007/s10898-022-01252-x86:1(205-249)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/s10898-022-01252-x
Castro MCire ABeck J(2022)A combinatorial cut-and-lift procedure with an application to 0–1 second-order conic programmingMathematical Programming: Series A and B10.1007/s10107-021-01699-y196:1-2(115-171)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10107-021-01699-y
Wang SLi JMehrotra S(2021)Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room PlanningINFORMS Journal on Computing10.1287/ijoc.2020.101033:4(1661-1677)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.1287/ijoc.2020.1010
Show More Cited By

Index Terms

Easily Computable Facets of the Knapsack Polytope
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Mathematical analysis
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Mixed discrete-continuous optimization
        Integer programming

Recommendations

Lifting the facets of zero---one polytopes

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero---one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into ...
Lifting facets of the cut polytope

The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G ...
A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope

We develop a framework for characterizing classes of facets for the Boolean quadric polytope obtainable through a simultaneous lifting procedure. In particular, we begin with a class of product-form facets that subsume Padberg's clique, cut, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 14, Issue 4

November 1989

190 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 November 1989

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen WChen LDai Y(2022)Lifting for the integer knapsack cover polyhedronJournal of Global Optimization10.1007/s10898-022-01252-x86:1(205-249)Online publication date: 7-Dec-2022
https://dl.acm.org/doi/10.1007/s10898-022-01252-x
Castro MCire ABeck J(2022)A combinatorial cut-and-lift procedure with an application to 0–1 second-order conic programmingMathematical Programming: Series A and B10.1007/s10107-021-01699-y196:1-2(115-171)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10107-021-01699-y
Wang SLi JMehrotra S(2021)Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room PlanningINFORMS Journal on Computing10.1287/ijoc.2020.101033:4(1661-1677)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.1287/ijoc.2020.1010
Letchford ASouli G(2019)On lifted cover inequalitiesOperations Research Letters10.1016/j.orl.2018.12.00547:2(83-87)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1016/j.orl.2018.12.005
Ben Salem MTaktak RMahjoub ABen-Abdallah H(2018)Optimization algorithms for the disjunctively constrained knapsack problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2465-722:6(2025-2043)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s00500-016-2465-7
Zhao MHuang KZeng B(2017)A polyhedral study on chance constrained program with random right-hand sideMathematical Programming: Series A and B10.1007/s10107-016-1103-6166:1-2(19-64)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10107-016-1103-6
Cañavate RLandete M(2016)A polyhedral study on 0-1 knapsack problems with set packing constraintsOperations Research Letters10.1016/j.orl.2016.01.01144:2(243-249)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.orl.2016.01.011
Agra ARequejo CSantos E(2016)Implicit cover inequalitiesJournal of Combinatorial Optimization10.1007/s10878-014-9812-331:3(1111-1129)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10878-014-9812-3
Côté JGendreau MPotvin J(2014)An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading ConstraintsOperations Research10.1287/opre.2014.130762:5(1126-1141)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1287/opre.2014.1307
(2014)Chance-Constrained Binary Packing ProblemsINFORMS Journal on Computing10.1287/ijoc.2014.059526:4(735-747)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1287/ijoc.2014.0595
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents