A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem

DOI10.1016/j.endm.2010.05.079zbMath1237.90215OpenAlexW2045625203MaRDI QIDQ2883626

Alexandre Salles da Cunha, Laura Bahiense, Abilio Lucena, Cid Carvalho De Souza

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.079

zbMATH Keywords

Lagrangian relaxationbranch and bound0-1 knapsack problems

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Lagrangian heuristics for the quadratic knapsack problem

Uses Software

• Knapsack

Cites Work

• Non delayed relax-and-cut algorithms
• Efficient cuts in Lagrangean `relax-and-cut' schemes
• Where are the hard knapsack problems?
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item