An algorithm for the solution of the 0-1 knapsack problem
From MaRDI portal
Publication:1156694
DOI10.1007/BF02241754zbMath0468.90045OpenAlexW1492845317MaRDI QIDQ1156694
Publication date: 1982
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02241754
computational resultsimplementation0-1 knapsack problemimplicit enumeration algorithmbinary knapsackFPK 79
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Boolean programming (90C09) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)
Related Items
An exact algorithm for the 0-1 collapsing knapsack problem, An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Sensitivity Analysis to Perturbations of the Weight of a Subset of Items: The Single Knapsack Case Study, Dantzig-Wolfe reformulations for binary quadratic problems, Exact methods for the knapsack problem and its generalizations, A Lagrangian heuristic for the capacitated plant location problem with single source constraints, A surrogate heuristic for set covering problems, A new enumeration scheme for the knapsack problem, Constructive dual methods for discrete programming, Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem, UGC: An algorithm for two-stage unconstrained guillotine cutting, An approximation algorithm for solving unconstrained two-dimensional knapsack problems, A constrained Steiner tree problem, 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, A general purpose exact solution method for mixed integer concave minimization problems, Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem, On Bilevel Optimization with Inexact Follower, 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, The multidimensional 0-1 knapsack problem: an overview., Single-vendor multi-buyer inventory coordination under private information, Essential particle swarm optimization queen with tabu search for MKP resolution, An improved bounding procedure for the constrained assignment problem, Core problems in bi-criteria \(\{0,1\}\)-knapsack problems, 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, Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem, Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem, A multi-level search strategy for the 0-1 multidimensional knapsack problem, An exact algorithm for the knapsack sharing problem, An efficient algorithm for the collapsing knapsack problem, Probability of unique integer solution to a system of linear equations, An exact algorithm for the subset sum problem, Random knapsack in expected polynomial time, Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study, Efficient reformulation for 0-1 programs -- methods and computational results, CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem, New trends in exact algorithms for the \(0-1\) knapsack problem, A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem, Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems, An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem, Heuristics and reduction methods for multiple constraints 0-1 linear programming problems, A set partitioning heuristic for the generalized assignment problem, A comparison of heuristics and relaxations for the capacitated plant location 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
