A characterization of knapsacks with the max-flow--min-cut property

DOI10.1016/0167-6377(92)90041-ZzbMath0773.90053MaRDI QIDQ1197887

Monique Laurent, Antonio Sassano

Publication date: 16 January 1993

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

zbMATH Keywords

knapsack problemsmax-flow-min-cut propertyclutter of minimal coversminimal cover cuts

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items

Knapsack polytopes: a survey, Reliability, covering and balanced matrices, Convex hull characterizations of lexicographic orderings, Binary extended formulations of polyhedral mixed-integer sets, Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation, Convex hulls of superincreasing knapsacks and lexicographic orderings, Lexicographical polytopes, On Dantzig figures from graded lexicographic orders, Strong IP formulations need large coefficients, Continuous knapsack sets with divisible capacities

Cites Work

• Unnamed Item
• Unnamed Item
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• An O(m n) algorithm for regular set-covering problems
• Facets of the knapsack polytope derived from disjoint and overlapping index configurations
• The matroids with the max-flow min-cut property
• Solving Large-Scale Zero-One Linear Programming Problems
• (1,k)-configurations and facets for packing problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Facets of the knapsack polytope
• Covering, Packing and Knapsack Problems
• Canonical Cuts on the Unit Hypercube