Facet defining inequalities for the dichotomous knapsack problem

DOI10.1016/0167-6377(90)90036-5MaRDI QIDQ911989zbMATH OpenOpenAlexFDO

Authors Elsie Sterbin Gottlieb

Publication date 1990

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(90)90036-5

zbMATH Keywords

dichotomous knapsack problemfacet defining inequalitieslinear relaxation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05) Boolean programming (90C09) Integer programming (90C10)

Review text

For a special case of the dichotomous knapsack problem the class of facets is characterized which means that the corresponding linear relaxation has an integer optimal solution.

Cites work

• (1,k)-configurations and facets for packing problems
• Bottleneck extrema
• Covering, Packing and Knapsack Problems
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Facets of the Knapsack Polytope From Minimal Covers
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Technical Note—A Note on Zero-One Programming

Cited in

(2)

• A concise characterization of strong knapsack facets
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting

This page was built for publication: Facet defining inequalities for the dichotomous knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911989)