A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem

Ali Eshragh, Jerzy Filar, Michael Haythorpe

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)

    Abstract

    In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes the probability of the event "this arc is located on the shortest tour." Those probabilities are then updated as in cross entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However, for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear program).

    Original languageEnglish
    Pages (from-to)103-125
    Number of pages23
    JournalAnnals of Operations Research
    Volume189
    Issue number1
    DOIs
    Publication statusPublished - Sep 2011

    Keywords

    • Cross-entropy method
    • Hamiltonian cycle problem
    • Markov decision process

    Fingerprint Dive into the research topics of 'A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem'. Together they form a unique fingerprint.

    Cite this