An algorithm for the solution of the 0-1 knapsack problem

DOI10.1007/BF02241754zbMath0468.90045OpenAlexW1492845317MaRDI QIDQ1156694

Didier Fayard, Gérard Plateau

Publication date: 1982

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02241754

zbMATH Keywords

computational resultsimplementation0-1 knapsack problemimplicit enumeration algorithmbinary knapsackFPK 79

Mathematics Subject Classification ID

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 (49)

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

• Quicksort
• Algorithm 37

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

This page was built for publication: An algorithm for the solution of the 0-1 knapsack problem