The computational problem of finding

the minimum-weight Hamiltonian cycle ¹

in a weighted graph.

---

• Intuition
• Decision version
• Complexity
• Sample instances
• Sample instance (pr76)
• Computation in Python
• Computation: Python, Nearest neighbor heuristic (NN)
• Computation: Python, SAT + NN, permutation
• Computation: Python, SAT, MTZ
• Computation: Python, SAT, MTZ (with NN)
• Optimal solution