Hamiltonian Cycle Example

Download Notebook

The Hamiltonian Cycle problem determines whether a cycle exists that visits every vertex of a graph exactly once and returns to the start. It is NP-complete and closely related to the Travelling Salesman Problem.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.hamiltonian_cycle import (
    HamiltonianCycleCollection,
    HamiltonianCycleData,
    HamiltonianCycleFormulation,
    HamiltonianCycleInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a connected 5-node graph that contains a Hamiltonian cycle.

adj = np.array(
    [
        [0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0],
        [1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1],
        [0, 0, 1, 1, 0],
    ]
)
node_names = ["A", "B", "C", "D", "E"]
data = HamiltonianCycleData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Hamiltonian Cycle Data:
  Nodes: 5
  Edges: 6

Plot Data

Visualize the graph structure.

data.plot()

<Axes: title={'center': 'Hamiltonian Cycle — 5 nodes, 6 edges'}>

Create Formulation

Set up constraints for a cycle visiting each node exactly once.

formulation = HamiltonianCycleFormulation()
print(formulation.to_string(data))

Hamiltonian Cycle Formulation:
  Nodes: 5

Index:
  i, j -- node indices, i = 0, ..., 4
  p    -- position index, p = 0, ..., 4

Decision Variables:
  x[i,p] in {0,1} for all i, p
  x[i,p] = 1 if node i is at position p in the cycle
  Total: 25 binary variables

Objective:
  minimize 0 (feasibility problem)

Constraints:
  1. Each node assigned to exactly one position (5 constraints):
     sum_p x[i,p] == 1  for all i = 0, ..., 4
  2. Each position assigned to exactly one node (5 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 4
  3. Consecutive nodes must be connected (40 constraints):
     x[i,p] + x[j,next(p)] <= 1  for all non-edges (i,j), p = 0, ..., 4

Create Instance

Combine data and formulation into a solvable instance.

instance = HamiltonianCycleInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Hamiltonian Cycle Data:
  Nodes: 5
  Edges: 6
Formulation:Hamiltonian Cycle Formulation:
  Nodes: 5

Index:
  i, j -- node indices, i = 0, ..., 4
  p    -- position index, p = 0, ..., 4

Decision Variables:
  x[i,p] in {0,1} for all i, p
  x[i,p] = 1 if node i is at position p in the cycle
  Total: 25 binary variables

Objective:
  minimize 0 (feasibility problem)

Constraints:
  1. Each node assigned to exactly one position (5 constraints):
     sum_p x[i,p] == 1  for all i = 0, ..., 4
  2. Each position assigned to exactly one node (5 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 4
  3. Consecutive nodes must be connected (40 constraints):
     x[i,p] + x[j,next(p)] <= 1  for all non-edges (i,j), p = 0, ..., 4

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Hamiltonian Cycle Solution:
  Cycle length: 5
  Valid: True
  Cycle: ['D', 'B', 'A', 'C', 'E']

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'Hamiltonian Cycle — length=5, valid=True'}>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = HamiltonianCycleCollection.from_random(min_nodes=4, max_nodes=6, edge_prob=0.7, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: hamiltonian_cycle<hamiltonian_cycle>
Minimize

Subject To
  node_0_one_pos: x_0_0 + x_0_1 + x_0_2 + x_0_3 == 1
  node_1_one_pos: x_1_0 + x_1_1 + x_1_2 + x_1_3 == 1
  node_2_one_pos: x_2_0 + x_2_1 + x_2_2 + x_2_3 == 1
  node_3_one_pos: x_3_0 + x_3_1 + x_3_2 + x_3_3 == 1
  pos_0_one_node: x_0_0 + x_1_0 + x_2_0 + x_3_0 == 1
  pos_1_one_node: x_0_1 + x_1_1 + x_2_1 + x_3_1 == 1
  pos_2_one_node: x_0_2 + x_1_2 + x_2_2 + x_3_2 == 1
  pos_3_one_node: x_0_3 + x_1_3 + x_2_3 + x_3_3 == 1
  edge_1_2_pos_0: x_1_0 + x_2_1 <= 1
  edge_2_1_pos_0: x_1_1 + x_2_0 <= 1
  edge_1_2_pos_1: x_1_1 + x_2_2 <= 1
  edge_2_1_pos_1: x_1_2 + x_2_1 <= 1
  edge_1_2_pos_2: x_1_2 + x_2_3 <= 1
  edge_2_1_pos_2: x_1_3 + x_2_2 <= 1
  edge_1_2_pos_3: x_1_3 + x_2_0 <= 1
  edge_2_1_pos_3: x_1_0 + x_2_3 <= 1
Binary
  x_0_0 x_0_1 x_0_2 x_0_3 x_1_0 x_1_1 x_1_2 x_1_3 x_2_0 x_2_1 x_2_2 x_2_3 x_3_0
  x_3_1 x_3_2 x_3_3