Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem

Michael Haythorpe () and Walter Murray ()
Additional contact information
Michael Haythorpe: Flinders University
Walter Murray: Stanford University

Computational Optimization and Applications, 2022, vol. 81, issue 1, No 11, 309-336

Abstract: Abstract It has been shown that a global minimizer of a smooth determinant of a matrix function corresponds to the largest cycle of a graph. When it exists, this is a Hamiltonian cycle. Finding global minimizers even of a smooth function is a challenge. The difficulty is often exacerbated by the existence of many global minimizers. One may think this would help, but in the case of Hamiltonian cycles the ratio of the number of global minimizers to the number of local minimizers is typically astronomically small. There are various equivalent forms of the problem and here we report on two. Although the focus is on finding Hamiltonian cycles, and this has an interest in and of itself, this is just a proxy for a class of problems that have discrete variables. The solution of relaxations of these problems is typically at a degenerate vertex, and in the neighborhood of the solution the Hessian is indefinite. The form of the Hamiltonian cycle problem we address has the virtue of being an ideal test problem for algorithms designed for discrete nonlinear problems in general. It is easy to generate problems of varying size and varying character, and they have the advantage of being able to determine if a global solution has been found. A feature of many discrete problems is that there are many solutions. For example, in the frequency assignment problem any permutation of a solution is also a solution. A consequence is that a common characteristic of the relaxed problems is that they have large numbers of global minimizers and even larger numbers of both local minimizers, and saddle points whose reduced Hessian has only a single negative eigenvalue. Efficient algorithms that seek to find global minimizers for this type of problem are described. Results using BONMIN, a solver for nonlinear problems with continuous and discrete variables, are also included.

Keywords: Global optimization; Discrete optimization; Binary variables; Negative curvature; Barrier functions; Hamiltonian cycles (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00326-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:81:y:2022:i:1:d:10.1007_s10589-021-00326-y

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00326-y

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().