Methods for Solving Subset Sum Problems

R.J.W. James

Department of Management, University of Canterbury,

Private Bag 4800, Christchurch, New Zealand

R.H. Storer

Department of Industrial and Systems Engineering, Lehigh University,

Mohler Laboratory, 200 West Packer Ave, Bethlehem, PA 18015, USA

Abstract

The subset sum problem is a simple and fundamental NP-hard problem that

is found in many real world applications. For the particular

application motivating this paper (combination weighers) a solution is

required to the subset sum problem that is within a small tolerance

level, and can be computed quickly. We propose five techniques for

solving this problem. The first is an enumeration technique that is

capable of solving small problems very efficiently. The next two

techniques are based on an efficient number partitioning algorithm.

These techniques can solve small problems very efficiently when the

solution uses approximately half the available elements (numbers) and

outperforms dynamic programming approaches proposed in the literature.

The last two techniques use a direct approach of improving a solution.

These techniques were found to perform very efficiently on large

problems and outperform heuristic techniques currently proposed in the

literature.