Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

DOI10.1287/opre.45.5.768zbMath0902.90125OpenAlexW2130350796MaRDI QIDQ4393124

Paolo Toth, Silvano Martello

Publication date: 10 August 1998

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

Full work available at URL: https://doi.org/10.1287/opre.45.5.768

zbMATH Keywords

branch-and-boundvalid inequalitiesoptimal Lagrangian multipliers

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Boolean programming (90C09)

Related Items

The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design, A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances, Robust efficiency measures for linear knapsack problem variants, Some thoughts on combinatorial optimisation, A novel reformulation for the single-sink fixed-charge transportation problem, Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem, The multidimensional 0-1 knapsack problem: an overview., A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem, A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem, An exact algorithm for the knapsack sharing problem, Where are the hard knapsack problems?, Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers, Tree knapsack approaches for local access network design, Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis, A fast algorithm for strongly correlated knapsack problems, New trends in exact algorithms for the \(0-1\) knapsack problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, The multidimensional 0-1 knapsack problem -- bounds and computational aspects