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

From MaRDI portal





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.




Cited in
(23)








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)