A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem

DOI10.1287/mnsc.30.6.765zbMath0555.90073OpenAlexW2108088553WikidataQ56050294 ScholiaQ56050294MaRDI QIDQ3220352

Silvano Martello, Paolo Toth

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

zbMATH Keywords

branch and boundknapsack problemrandomly generated test problemsdepth-first tree search algorithmlarge sized problemsmixed algorithmSubset-Sum Problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Dynamic programming (90C39) Boolean programming (90C09)

Related Items (19)

An efficient pruning algorithm for value independent knapsack problem using a DAG structure ⋮ A polynomial approximation scheme for the subset sum problem ⋮ An exact decomposition algorithm for the generalized knapsack sharing problem ⋮ A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems ⋮ Coordinated lab-clinics: a tactical assignment problem in healthcare ⋮ Comparison of Different ACO Start Strategies Based on InterCriteria Analysis ⋮ Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds ⋮ Subset-sum problems with different summands: Computation ⋮ Two linear approximation algorithms for the subset-sum problem ⋮ Bridging game theory and the knapsack problem: a theoretical formulation ⋮ An exact algorithm for the subset sum problem ⋮ Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem ⋮ Start Strategies of ACO Applied on Subset Problems ⋮ Sensitivity Analysis of ACO Start Strategies for Subset Problems ⋮ Efficient reformulation for 0-1 programs -- methods and computational results ⋮ A hybrid algorithm for the unbounded knapsack problem ⋮ Solving dense subset-sum problems by using analytical number theory ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ Approximation schemes for the subset-sum problem: Survey and experimental analysis

This page was built for publication: A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem