Matroidal relaxations for 0-1 knapsack problems

DOI10.1016/0167-6377(93)90026-DzbMath0802.90076OpenAlexW1995917458MaRDI QIDQ1319682

Paulo Barcia, Lígia Amado

Publication date: 12 April 1994

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

Full work available at URL: https://doi.org/10.1016/0167-6377(93)90026-d

zbMATH Keywords

Lagrangean relaxationmatroidindependence system

Mathematics Subject Classification ID

Boolean programming (90C09) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Knapsack polytopes: a survey ⋮ Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis ⋮ New polynomial bounds for matroidal knapsacks

Cites Work

• The matroidal knapsack: A class of (often) well-solvable problems
• Heuristic algorithms for the multiple knapsack problem
• Faces for a linear inequality in 0–1 variables