Exact methods for the knapsack problem and its generalizations

DOI10.1016/0377-2217(87)90165-2zbMath0603.90097OpenAlexW2009443800MaRDI QIDQ1083032

Stanisław Walukiewicz, Krzysztof Dudzinski

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0377-2217(87)90165-2

zbMATH Keywords

Lagrangean relaxationreductionlinear programming relaxationsdual methodsexact methodsbranch-and- boundmultiple-choice knapsackbinary knapsack problemnested knapsack

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Related Items

Knapsack allocation of multiple resources in benefit-cost analysis by way of the analytic hierarchy process, Binary Optimal Control of Single-Flux-Quantum Pulse Sequences, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, A surrogate heuristic for set covering problems, A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem, A versatile algorithm for assembly line balancing, Robust efficiency measures for linear knapsack problem variants, Models for planning capacity expansion of convenience stores under uncertain demand and the value of information, Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem, Bounds for nested knapsack problems, A minimal algorithm for the multiple-choice knapsack problem, An expanding-core algorithm for the exact \(0-1\) knapsack problem, Relaxation techniques applied to some loading problems, Unnamed Item, Improved Lagrangean decomposition: An application to the generalized assignment problem, Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design, A moment based metric for 2-D and 3-D packing, Nonconvex piecewise linear knapsack problems, A note on sequencing jobs with deadlines problem, A survey of algorithms for the generalized assignment problem, An exact approach for scheduling jobs with regular step cost functions on a single machine, Unnamed Item, Asignacion de recuerdos max-min: Propiedades y algoritmos, A multi-criteria approach to approximate solution of multiple-choice knapsack problem, On the approximability of the two-phase knapsack problem, The Fixed-Charge Shortest-Path Problem, Lagrangean/surrogate relaxation for generalized assignment problems, On a cardinality constrained linear programming knapsack problem, Relaxation heuristics for a generalized assignment problem, A typology of cutting and packing problems, A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem, A class of exponential neighbourhoods for the quadratic travelling salesman problem, The capacity expansion problem in the service industry, The discrete forward-reserve problem -- allocating space, selecting products, and area sizing in forward order picking, Maximum coverage with cluster constraints: an LP-based approximation technique

Uses Software

• Algorithm 37

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dynamic programming approach to solving the multiple choice knapsack problem
• A fast algorithm for the linear multiple-choice knapsack problem
• Dynamic programming algorithms for the zero-one knapsack problem
• An algorithm for the solution of the 0-1 knapsack problem
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• A note on the knapsack problem with special ordered sets
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• An improved upper bound for the zero-one knapsack problem. A note on the paper by Martello and Toth
• The 0-1 knapsack problem with multiple choice constraints
• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• AnO (n)-algorithm for LP-knapsacks with a fixed number of GUB constraints
• An O(n) algorithm for the multiple-choice knapsack linear program
• A computational study of a multiple-choice knapsack algorithm
• Solving Large-Scale Zero-One Linear Programming Problems
• Hard Knapsack Problems
• The Linear Multiple Choice Knapsack Problem
• Worst-Case Analysis of Heuristic Algorithms
• An Algorithm for Large Zero-One Knapsack Problems
• Technical Note—The Multiperiod Knapsack Problem
• The Multiple-Choice Nested Knapsack Model
• Reduction Algorithm for Zero-One Single Knapsack Problems
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Branch-and-Bound Strategies for Dynamic Programming
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• Combinatorial Problems: Reductibility and Approximation
• The Multiple-Choice Knapsack Problem
• Covering, Packing and Knapsack Problems
• The Theory and Computation of Knapsack Functions
• Integer Programming Algorithms: A Framework and State-of-the-Art Survey