A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem

DOI10.1007/s10479-009-0565-9zbMath1233.90270OpenAlexW2070593991MaRDI QIDQ666352

Ali Eshragh, Michael Haythorpe, Jerzy A. Filar

Publication date: 8 March 2012

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-009-0565-9

zbMATH Keywords

Markov decision processHamiltonian cycle problemcross-entropy method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

On transition matrices of Markov chains corresponding to Hamiltonian cycles ⋮ A new heuristic for detecting non-Hamiltonicity in cubic graphs ⋮ Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem ⋮ Markov chains, Hamiltonian cycles and volumes of convex bodies ⋮ Hamiltonian Cycles and Subsets of Discounted Occupational Measures ⋮ Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem ⋮ Feasible Bases for a Polytope Related to the Hamilton Cycle Problem

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting
• Optimization of computer simulation models with rare events
• The cross-entropy method for combinatorial and continuous optimization
• Convergence properties of the cross-entropy method for discrete optimization
• On the convergence of the cross-entropy method
• Constrained Discounted Markov Decision Processes and Hamiltonian Cycles
• Refined MDP-Based Branch-and-Fix Algorithm for the Hamiltonian Cycle Problem
• Determinants and Longest Cycles of Graphs
• Hamiltonian Cycles and Markov Chains
• Controlled Markov Chains, Graphs, and Hamiltonicity

This page was built for publication: A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem