New trends in exact algorithms for the \(0-1\) knapsack problem

DOI10.1016/S0377-2217(99)00260-XzbMath0961.90090WikidataQ58826490 ScholiaQ58826490MaRDI QIDQ1569935

David Pisinger, Paolo Toth, Silvano Martello

Publication date: 9 July 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

dynamic programming; branch-and-bound; knapsack problem; state-of-the-art

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90C09: Boolean programming

Related Items

A time-dependent multiple criteria single-machine scheduling problem, Random knapsack in expected polynomial time, Exact solution of a class of nonlinear knapsack problems, The multidimensional 0-1 knapsack problem -- bounds and computational aspects, Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem, Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem, The 0-1 knapsack problem with fuzzy data, Lagrangean relaxation for the capacitated hub location problem with single assignment, A successive approximation algorithm for the multiple knapsack problem, A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem, Heuristics for the 0-1 multidimensional knapsack problem, Average performance of greedy heuristics for the integer knapsack problem., The computation of the worst conditional expectation., The multidimensional 0-1 knapsack problem: an overview., Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Heuristic allocation based on a dynamic programming state-space representation, Where are the hard knapsack problems?, Outbound supply chain network design with mode selection, lead times and capacitated vehicle distribution centers, An experimental study of random knapsack problems, Solving the Knapsack problem with imprecise weight coefficients using genetic algorithms, A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem, A survey of recent developments in multiobjective optimization, An exact algorithm for the knapsack sharing problem, Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls, Tree knapsack approaches for local access network design, Approximate and exact algorithms for the fixed-charge knapsack problem, An improved typology of cutting and packing problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for the solution of the 0-1 knapsack problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A New Algorithm for the 0-1 Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• Resolution of the 0–1 knapsack problem: Comparison of methods
• Computing Partitions with Applications to the Knapsack Problem
• An Efficient Algorithm for the 0-1 Knapsack Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• Discrete-Variable Extremum Problems