article

The Integer Knapsack Cover Polyhedron

Author:

Hande YamanAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 21, Issue 3

Pages 551 - 572

https://doi.org/10.1137/050639624

Published: 01 July 2007 Publication History

Abstract

We study the integer knapsack cover polyhedron which is the convex hull of the set of vectors $x\in \mathbb{Z}_{+}^{n}$ that satisfy $C^{T}x\geq b$, with $C\in \mathbb{Z}_{++}^{n}$ and $b\in \mathbb{Z}_{++}$. We present some general results about the nontrivial facet-defining inequalities. Then we derive specific families of valid inequalities, namely, rounding, residual capacity, and lifted rounding inequalities, and identify cases where they define facets. We also study some known families of valid inequalities called 2-partition inequalities and improve them using sequence-independent lifting.

Cited By

View all

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
Chung KRichard JTawarmalani M(2014)Lifted inequalities for $$0\mathord {-}1$$ mixed-integer bilinear covering setsMathematical Programming: Series A and B10.1007/s10107-013-0652-1145:1-2(403-450)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10107-013-0652-1
Altın AYaman HPınar M(2011)The Robust Network Loading Problem Under Hose Demand UncertaintyINFORMS Journal on Computing10.1287/ijoc.1100.038023:1(75-89)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1287/ijoc.1100.0380

Index Terms

The Integer Knapsack Cover Polyhedron
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
  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

Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions

In this paper we present a class of valid inequalities as well as a class of facets for the cut-polytope of the complete graph. It is shown that many of the known classes of valid inequalities, e.g., triangle, hypermetric and cycle inequalities, belong ...
On the facets of the mixed---integer knapsack polyhedron

We study the mixed---integer knapsack polyhedron, that is, the convex hull of the mixed---integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet---defining inequalities of this polyhedron that can be ...
Easily Computable Facets of the Knapsack Polytope

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 21, Issue 3

July 2007

271 pages

ISSN:0895-4801

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 July 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Chung KRichard JTawarmalani M(2014)Lifted inequalities for $$0\mathord {-}1$$ mixed-integer bilinear covering setsMathematical Programming: Series A and B10.1007/s10107-013-0652-1145:1-2(403-450)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10107-013-0652-1
Altın AYaman HPınar M(2011)The Robust Network Loading Problem Under Hose Demand UncertaintyINFORMS Journal on Computing10.1287/ijoc.1100.038023:1(75-89)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1287/ijoc.1100.0380

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions

On the facets of the mixed---integer knapsack polyhedron

Easily Computable Facets of the Knapsack Polytope

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations