An algorithm for the solution of the 0-1 knapsack problem
From MaRDI portal
Publication:1156694
DOI10.1007/BF02241754zbMath0468.90045MaRDI QIDQ1156694
Publication date: 1982
Published in: Computing (Search for Journal in Brave)
computational results; implementation; 0-1 knapsack problem; implicit enumeration algorithm; binary knapsack; FPK 79
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C09: Boolean programming
90-04: Software, source code, etc. for problems pertaining to operations research and mathematical programming
Related Items
An exact algorithm for the subset sum problem, Random knapsack in expected polynomial time, A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems, A comparison of heuristics and relaxations for the capacitated plant location problem, Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem, A Lagrangean dual ascent algorithm for simple plant location problems, An exact algorithm for large unbounded knapsack problems, Improved Lagrangean decomposition: An application to the generalized assignment problem, Single-vendor multi-buyer inventory coordination under private information, Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes, Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem, Heuristics and reduction methods for multiple constraints 0-1 linear programming problems, Exact methods for the knapsack problem and its generalizations, A new enumeration scheme for the knapsack problem, Constructive dual methods for discrete programming, UGC: An algorithm for two-stage unconstrained guillotine cutting, An approximation algorithm for solving unconstrained two-dimensional knapsack problems, A constrained Steiner tree problem, An improved bounding procedure for the constrained assignment problem, An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem, A set partitioning heuristic for the generalized assignment problem, An exact algorithm for the 0-1 collapsing knapsack problem, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, A surrogate heuristic for set covering problems, A minimal algorithm for the multiple-choice knapsack problem, The bottleneck generalized assignment problem, An expanding-core algorithm for the exact \(0-1\) knapsack problem, The multidimensional 0-1 knapsack problem: an overview., New trends in exact algorithms for the \(0-1\) knapsack problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Efficient reformulation for 0-1 programs -- methods and computational results, A Lagrangian heuristic for the capacitated plant location problem with single source constraints, Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem, Core problems in bi-criteria \(\{0,1\}\)-knapsack problems, An exact algorithm for the knapsack sharing problem, An efficient algorithm for the collapsing knapsack problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
- Fast Approximation Algorithms for Knapsack Problems
- An Algorithm for Large Zero-One Knapsack Problems
- Resolution of the 0–1 knapsack problem: Comparison of methods
- A Direct Descent Binary Knapsack Algorithm
- Implementing Quicksort programs
- A Branch Search Algorithm for the Knapsack Problem
