A polyhedral study on 0-1 knapsack problems with set packing constraints
Pages 243 - 249
Abstract
We investigate the 0-1 knapsack problem with additional set packing constraints. First, we introduce a family of facet-defining clique inequalities. Then, we focus on lifted cover inequalities and we define upper and lower bounds on the lifting coefficients. We also introduce a family of lifted cover inequalities where some of the lifting coefficients are set to their upper bound, and the remaining ones are set at their lower bound. Finally, we specialize our results to the knapsack problem with generalized upper bound constraints, where the set packing constraints must be non-overlapping.
References
[1]
E. Balas, Facets of the Knapsack Polytope, Math. Program., 8 (1975) 146-164.
[2]
E. Balas, E. Zemel, Facets of the knapsack polytope from minimum covers, SIAM J. Appl. Math., 34 (1978) 119-148.
[3]
L. Cánovas, M. Landete, A. Marín, New facets for the set packing polytope, Oper. Res. Lett., 27 (2000) 156-161.
[4]
L. Cánovas, M. Landete, A. Marín, Facet obtaining procedures for set packing problems, SIAM J. Discrete Math., 16 (2003) 127-155.
[5]
E. Cheng, W.H. Cunningham, Wheel inequalities for stable set polytopes, Math. Program., 77 (1997) 389-421.
[6]
J. Ebery, M. Krishnamoorthy, A. Ernst, N. Boland, The capacitated multiple allocation hub location problem: Formulations and algorithms, European J. Oper. Res., 120 (2000) 614-631.
[7]
L.F. Escudero, A. Garín, G. Pérez, An O ( n log n ) procedure for identifying facets of the knapsack polytope, Oper. Res. Lett., 31 (2003) 211-218.
[8]
L.F. Escudero, M. Landete, A.M. Rodríguez-Chía, Stochastic set packing problem, European J. Oper. Res., 211 (2011) 232-240.
[9]
Z. Gu, G.L. Nemhauser, M.N.P Savelsberg, Lifted cover inequalities for 0-1 integer programs II: Complexity. Report 94-10, Computational Optimization Center, Georgia Institute of Technology, 1994.
[10]
M. Landete, 0-1 Knapsack problems with set packing constraints: examples, 2015. http://gestionderecursosyoptimizacion.edu.umh.es/data-library/.
[11]
G.L. Nemhauser, P.H. Vance, Lifted cover facets of the 0-1 knapsack polytope with GUB constraints, Oper. Res. Lett., 16 (1994) 255-263.
[12]
G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, in: Wiley-Interscience Series in Discrete Mathematics and Optimization, 1988.
[13]
M.W. Padberg, On the facial structure of set packing polyhedra, Math. Program., 5 (1973) 199-215.
[14]
M.W. Padberg, ( 1 - k ) -configuration and facets for packing problems, Math. Program., 18 (1980) 94-99.
[15]
L.E. Trotter, A class of facet producing graphs for vertex packing polyhedra, Discrete Math., 12 (1975) 373-388.
[16]
S. De Vries, R.V. Vohra, Combinatorial auctions: a survey, INFORMS J. Comput., 15 (2003) 284-309.
[17]
R. Weismantel, On the 0/1 knapsack polytope, Math. Program., 77 (1997) 49-68.
[18]
L.A. Wolsey, Valid inequalities for 0-1 knapsacks and mips with generalized uppper bound constraints, Discrete Appl. Math., 29 (1990) 251-261.
[19]
E. Zemel, Easily computable facets of the knapsack polytope, Math. Oper. Res., 14 (1989) 760-764.
[20]
B. Zeng, J.P. Richard, A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence independent lifting, Discrete Optim., 8 (2011) 259-276.
[21]
B. Zeng, J.P. Richard, A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Discrete Optim., 8 (2011) 277-301.
- A polyhedral study on 0-1 knapsack problems with set packing constraints
Recommendations
A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting
In this paper, we study the polyhedral structure of the set of 0-1 integer solutions to a single knapsack constraint and multiple disjoint cardinality constraints (MCKP). This set is a generalization of the classical 0-1 knapsack polytope (KP) and the 0-...
A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting
We study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0-1 knapsack polytope and the 0-1 knapsack polytope with generalized upper bounds. We ...
On the 0/1 knapsack polytope
This paper deals with the 0/1 knapsack polytope. In particular, we introduce the class ofweight inequalities. This class of inequalities is needed to describe the knapsack polyhedron when the weights of the items lie in certain intervals. A ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 March 2016
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Jan 2025