Easily searched encodings for number partitioning

DSpace/Manakin Repository

Easily searched encodings for number partitioning

Show simple item record

dc.contributor.author Shieber, Stuart ORCID 0000-0002-7733-8195
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

Files in this item

Files Size Format View
Number Partitioning.pdf 662.4Kb PDF View/Open

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7501]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Show simple item record

 
 

Search DASH


Advanced Search
 
 

Submitters