A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
The paper presents a mixed approach to the Subset-Sum Problem such as \[ (P)\quad \max imize\quad \{\sum^{n}_{i=1}w_ ix_ i| \sum^{n}_{i=1}w_ ix_ i\leq W,\quad x_ i=0\quad or\quad 1\}. \] The approach consists of a depth-first tree search algorithm and a dynamic programm. Three algorithms, tree seach [the authors, Eur. J. Oper. Res. 1, 169-175 (1977; Zbl 0374.90050)], dynamic programming [\textit{J. H. Ahrens} and \textit{G. Finke}, Oper. Res. 23, 1099-1109 (1975; Zbl 0324.90047)] and the mixed approach presented here, are applied to randomly generated test problems with values \(w_ i\) in ranges [1,M] (where \(M=10^ 3,10^ 6,10^{12})\) and different values of n from 8 to 40. The results show that the dynamic programm requires a large computational time and space for large n, and that the tree search tends to degenerate to complete enumeration for large M since no feasible solution of the value W exists. On the contrary, the mixed algorithm can also solve some hard problems which have no feasible solution of value W and other hard problems proposed by Todd-Avis or by \textit{V. Chvatal} [ibid. 28, 1402-1411 (1980; Zbl 0447.90063)]. Furthermore, it is shown that a revised mixed approach with Balas-Zemel's reduction [\textit{E. Balas} and \textit{E. Zemel}, ibid. 28, 1130-1154 (1980; Zbl 0449.90064)] can efficiently solve large sized problems of values n from 1,000 to 10,000. The algorithm is based on the following idea. In the dynamic programming phase, the authors consider the following two partial problems: \[ (P1)\quad \max imize\quad \{\sum^{n}_{i=N1+1}w_ ix_ i| \sum^{n}_{i=N1+1}w_ ix_ i\leq W,\quad x_ i=0\quad or\quad 1\},\quad and \] \[ (P2)\quad \max imize\quad \{\sum^{n}_{i=N2+1}w_ ix_ i| \sum^{n}_{i=N2+1}w_ ix_ i\leq \bar W,\quad x_ i=0\quad or\quad 1\} \] for prefixed values such as \(N2<N1<n\) and \(\bar W<W\). Then, for each partial problem of (P1) and (P2), we find all states (V,X) corresponding to all feasible solutions and \(V=\sum_{i\in x}w_ i\). After that, (P) consisting of only the first N1 items is solved by a binary tree search algorithm. At every node of the search tree where the remaining items and total weight are thrown in either of these states, a lower bound is calculated from values of these states. Thus, each node bringing no better solution is fathomed.
- An exact algorithm for the subset sum problem
- An almost linear-time algorithm for the dense subset-sum problem
- Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- Techniques for solving subset sum problems within a given tolerance
- Two linear approximation algorithms for the subset-sum problem
- The subset sum problem
- Solving dense subset-sum problems by using analytical number theory
- A competitive local search heuristic for the subset sum problem
- On the best choice of a branching variable in the subset sum problem
- 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 competitive local search heuristic for the subset sum problem
- A branch bound method for subset sum problem
- A polynomial approximation scheme for the subset sum problem
- Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
- Coordinated lab-clinics: a tactical assignment problem in healthcare
- On the best choice of a branching variable in the subset sum problem
- 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
- Bridging game theory and the knapsack problem: a theoretical formulation
- Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering
- Start Strategies of ACO Applied on Subset Problems
- Sensitivity analysis of ACO start strategies for subset problems
- An exact decomposition algorithm for the generalized knapsack sharing problem
- Probabilistic Model of Ant Colony Optimization for Multiple Knapsack Problem
- Comparison of different ACO start strategies based on InterCriteria analysis
- A framework for tightening 0-1 programs based on extensions of pure 0-1 KP and SS problems
- 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
This page was built for publication: A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3220352)