Valid inequalities, cutting planes and integrality of the knapsack polytope

DOI10.1080/09720502.2011.10700759zbMath1254.90197OpenAlexW2089438526MaRDI QIDQ3101539

Stefan M. Stefanov

Publication date: 29 November 2011

Published in: Journal of Interdisciplinary Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.connectjournals.com/file_html_pdf/1189104H_03_JIM_T23_14-4_pp389-406A.pdf

zbMATH Keywords

integer programmingcombinatorial optimizationknapsack problemcutting planesvalid inequalitiesintegrality of polytopesdominating inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

On the solution of multidimensional convex separable continuous knapsack problem with bounded variables

Cites Work

• Unnamed Item
• Paroids: A canonical format for combinatorial optimization
• Outline of an algorithm for integer solutions to linear programs
• (1,k)-configurations and facets for packing problems
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra