Easily searched encodings for number partitioning

Easily searched encodings for number partitioning

DSpace/Manakin Repository

Easily searched encodings for number partitioning

dc.contributor.author	Shieber, Stuart
dc.contributor.author	Marks, Joe
dc.contributor.author	Ngo, J. Thomas
dc.contributor.author	Ruml, Wheeler
dc.date.accessioned	2008-08-25T14:23:22Z
dc.date.issued	1996
dc.identifier.citation	Wheeler Ruml, J. Thomas Ngo, Joe Marks, and Stuart M. Shieber. Easily searched encodings for number partitioning. Journal of Optimization Theory and Applications, 89(2):251-291, July 1996. The original publication is available at www.springerlink.com.	en
dc.identifier.issn	0022-3239	en
dc.identifier.issn	1573-2878	en
dc.identifier.uri	http://nrs.harvard.edu/urn-3:HUL.InstRepos:2031717
dc.description.abstract	Can stochastic search algorithms outperform existing deterministic heuristics for the NP-hard problem Number Partitioning if given a sufficient, but practically realizable amount of time? In a thorough empirical investigation using a straightforward implementation of one such algorithm, simulated annealing, Johnson et al. (Ref. 1) concluded tentatively that the answer is negative. In this paper, we show that the answer can be positive if attention is devoted to the issue of problem representation (encoding). We present results from empirical tests of several encodings of Number Partitioning with problem instances consisting of multiple-precision integers drawn from a uniform probability distribution. With these instances and with an appropriate choice of representation, stochastic and deterministic searches can—routinely and in a practical amount of time—find solutions several orders of magnitude better than those constructed by the best heuristic known (Ref. 2), which does not employ searching. We thank David S. Johnson of AT&T Bell Labs for generously and promptly sharing his test instances. For stimulating discussions, we thank members of the Harvard Animation/Optimization Group (especially Jon Christensen), the Computer Science Department at the University of New Mexico, the Santa Fe Institute, and the Berkeley CAD Group. The anonymous referees made numerous constructive suggestions. We thank Rebecca Hayes for comments concerning the figures. The second author is grateful for a Graduate Fellowship from the Fannie and John Hertz Foundation. We thank the Free Software Foundation for making the GNU Multiple Precision package available. The research described in this paper was conducted mostly while the third author was at Digital Equipment Corporation Cambridge Research Lab. This work was supported in part by the National Science Foundation, principally under Grants IRI-9157996 and IRI-9350192 to the fourth author, and by matching grants from Digital Equipment Corporation and Xerox Corporation.	en
dc.description.sponsorship	Engineering and Applied Sciences	en
dc.language.iso	en_US	en
dc.publisher	Springer	en
dc.relation.isversionof	http://dx.doi.org/10.1007/BF02192530	en
dash.license	LAA
dc.title	Easily searched encodings for number partitioning	en
dc.relation.journal	Journal of Optimization Theory and Applications	en
dash.depositing.author	Shieber, Stuart