Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

DOI10.1287/OPRE.45.5.768zbMATH Open0902.90125OpenAlexW2130350796MaRDI QIDQ4393124FDOQ4393124

Authors: Silvano Martello, Paolo Toth 

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

Recommendations

• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• New trends in exact algorithms for the \(0-1\) knapsack problem
• A new Lagrangian based branch and bound algorithm for the 0-1 knapsack problem
• A new class of hard problem instances for the 0-1 knapsack problem
• A New Algorithm for the 0-1 Knapsack Problem

zbMATH Keywords

valid inequalitiesbranch-and-boundoptimal Lagrangian multipliers

Mathematics Subject Classification ID

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

Cited In (32)

• Some thoughts on combinatorial optimisation
• Title not available (Why is that?)
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Solving a class of multiplicative programs with 0-1 knapsack constraints
• A new class of hard problem instances for the 0-1 knapsack problem
• The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design
• Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
• A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem
• The knapsack problem with generalized upper bounds
• A family of composite discrete bivariate distributions with uniform marginals for simulating realistic and challenging optimization-problem instances
• Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
• Lower Bounds on Time-Accuracy Trade-Offs for the 0-1 Knapsack Problem
• Where are the hard knapsack problems?
• A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem
• Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
• A fast algorithm for strongly correlated knapsack problems
• Analysis of divide-and-conquer strategies for the \(0-1\) minimization knapsack problem
• A hard knapsack problem
• Tree knapsack approaches for local access network design
• A rigorous method for solving 0-1 polynomial knapsack problem
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• Robust efficiency measures for linear knapsack problem variants
• A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem
• New trends in exact algorithms for the \(0-1\) knapsack problem
• The multidimensional 0-1 knapsack problem: an overview.
• Hard Equality Constrained Integer Knapsacks
• Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• A new lower bound for the linear knapsack problem with general integer variables
• An exact algorithm for the knapsack sharing problem
• A novel reformulation for the single-sink fixed-charge transportation problem
• Some computational results on real 0-1 knapsack problems

This page was built for publication: Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393124)