A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
From MaRDI portal
Publication:3220352
DOI10.1287/mnsc.30.6.765zbMath0555.90073WikidataQ56050294 ScholiaQ56050294MaRDI QIDQ3220352
Publication date: 1984
Published in: Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/mnsc.30.6.765
branch and bound; knapsack problem; randomly generated test problems; depth-first tree search algorithm; large sized problems; mixed algorithm; Subset-Sum Problem
65K05: Numerical mathematical programming methods
90C10: Integer programming
90C39: Dynamic programming
90C09: Boolean programming
Related Items
An exact algorithm for the subset sum problem, Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds, Subset-sum problems with different summands: Computation, A hybrid algorithm for the unbounded knapsack problem, Approximation schemes for the subset-sum problem: Survey and experimental analysis, Solving dense subset-sum problems by using analytical number theory, A polynomial approximation scheme for the subset sum problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Efficient reformulation for 0-1 programs -- methods and computational results, An efficient pruning algorithm for value independent knapsack problem using a DAG structure, Two linear approximation algorithms for the subset-sum problem, Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem