Abstract
A general strategy is advanced for simplifying nonlinear optimization problems, the “ant-lion” method. This approach exploits shape modifications of the cost-function hypersurface which distend basins surrounding low-lying minima (including global minima). By intertwining hypersurface deformations with steepest-descent displacements, the search is concentrated on a small relevant subset of all minima. Specific calculations demonstrating the value of this method are reported for the partitioning of two classes of irregular but nonrandom graphs, the “prime-factor” graphs and the “pi” graphs. We also indicate how this approach can be applied to the traveling salesman problem and to design layout optimization, and that it may be useful in combination with simulated annealing strategies.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. L. Lawler, J. K. Leustra, A. H. G. Rinnooy Kan, and K. B. Shmoys, eds.,The Travelling Salesman Problem (North-Holland, Amsterdam, 1979).
G. Baskaran, Yaotian Fu, and P. W. Anderson,J. Stat. Phys. 45:1 (1986).
H. A. Scheraga,Chem. Rev. 71:195 (1971).
M. Mezard, G. Parisi, and M. Virasoro,Spin Glass Theory and Beyond (World Scientific, Singapore, 1987).
S. Kirkpatrick, C. D. Gelatte, Jr., and M. P. Vecchi,Science 220:671 (1983).
B. Bollabás,Ggaph Theory, An Introductory Course (Springer-Verlag, New York, 1979).
M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
F. H. Stillinger and T. A. Weber,Science 225:983 (1984).
R. A. LaViolette and F. H. Stillinger,J. Chem. Phys. 83:4079 (1985).
Cover design,Math. Intelligencer 7(3) (1985).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Stillinger, F.H., Weber, T.A. Nonlinear optimization simplified by hypersurface deformation. J Stat Phys 52, 1429–1445 (1988). https://doi.org/10.1007/BF01011658
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01011658