Skip to content

Longest Path Example

Download Notebook

The Longest Path problem finds the maximum-weight path between two nodes in a weighted graph, visiting a given number of nodes. It is NP-hard for general graphs, contrasting with the polynomial-time shortest path problem.

import getpass
import os

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

from luna_usecases.longest_path import (
    LongestPathCollection,
    LongestPathData,
    LongestPathFormulation,
    LongestPathInstance,
)

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 5-node graph and search for the longest path from A to E.

adj = np.array(
    [
        [0, 2, 1, 0, 0, 0],
        [2, 0, 1, 1, 0, 0],
        [1, 1, 0, 0, 2, 0],
        [0, 1, 0, 0, 1, 2],
        [0, 0, 2, 1, 0, 1],
        [0, 0, 0, 2, 1, 0],
    ]
)
node_names = ["A", "B", "C", "D", "E", "F"]
data = LongestPathData.from_adjacency_matrix(
    adjacency_matrix=adj,
    node_names=node_names,
    start_node="A",
    terminal_node="F",
    path_length=4,
)
print(data.to_string())

Longest Path Data:
  Nodes: 6
  Edges: 8
  Start: A
  Terminal: F
  Path length: 4

Plot Data

Visualize the graph with start and end nodes.

data.plot()


<Axes: title={'center': 'Longest Path — 6 nodes, A→F, length=4'}>
png

Create Formulation

Find the longest simple path between the designated start and end nodes.

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

Longest Path Formulation:
  Nodes: 6
  Path length: 4
  Start node: A (fixed constant at position 0)
  Terminal node: F (fixed constant at position 3)

Decision Variables:
  x[i,p] in {0,1} for i = 0, ..., 5, p = 0, ..., 3
  x[i,p] = 1 if node i is at position p in the path
  x[start, 0] = 1 and x[terminal, 3] = 1 are treated as constants (not model variables)
  Total: 22 binary variables

Objective:
  maximize sum_p sum_False w_ij * x[i,p] * x[j,p+1]

Constraints:
  1. Each position has exactly one node (4 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 3
  2. Each node used at most once (6 constraints):
     sum_p x[i,p] <= 1  for all i = 0, ..., 5
  3. Consecutive nodes must be connected (42 constraints):
     x[i,p] + x[j,p+1] <= 1  for all non-edges (i,j), p = 0, ..., 2

  Note: Start/terminal equality constraints are eliminated by substitution.

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Longest Path Data:
  Nodes: 6
  Edges: 8
  Start: A
  Terminal: F
  Path length: 4
Formulation:Longest Path Formulation:
  Nodes: 6
  Path length: 4
  Start node: A (fixed constant at position 0)
  Terminal node: F (fixed constant at position 3)

Decision Variables:
  x[i,p] in {0,1} for i = 0, ..., 5, p = 0, ..., 3
  x[i,p] = 1 if node i is at position p in the path
  x[start, 0] = 1 and x[terminal, 3] = 1 are treated as constants (not model variables)
  Total: 22 binary variables

Objective:
  maximize sum_p sum_False w_ij * x[i,p] * x[j,p+1]

Constraints:
  1. Each position has exactly one node (4 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 3
  2. Each node used at most once (6 constraints):
     sum_p x[i,p] <= 1  for all i = 0, ..., 5
  3. Consecutive nodes must be connected (42 constraints):
     x[i,p] + x[j,p+1] <= 1  for all non-edges (i,j), p = 0, ..., 2

  Note: Start/terminal equality constraints are eliminated by substitution.

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')













Longest Path Solution:
  Path: ['A', 'B', 'D', 'F']
  Total weight: 5.0
  Valid: True



Plot Solution


Visualize the optimal solution.


uc_solution.path



['A', 'B', 'D', 'F']



uc_solution.plot(data)



<Axes: title={'center': 'Longest Path — weight=5.0, valid=True'}>


png


Collections


Generate a benchmark collection of random instances for batch processing.


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



Model: longest_path<longest_path>
Maximize
  4 * x_0_1 * x_1_0 + 3 * x_0_1 * x_2_0 + 9 * x_1_1 * x_3_0 + 9 * x_1_0
  + 4 * x_1_1 + 3 * x_2_1
Subject To
  one_node_per_pos_0: x_1_0 + x_2_0 + x_3_0 == 0
  one_node_per_pos_1: x_0_1 + x_1_1 + x_2_1 == 0
  node_at_most_once_0: x_0_1 <= 0
  node_at_most_once_1: x_1_0 + x_1_1 <= 1
  node_at_most_once_2: x_2_0 + x_2_1 <= 1
  node_at_most_once_3: x_3_0 <= 0
  connected_1_2_pos_0: x_1_0 + x_2_1 <= 1
  connected_2_1_pos_0: x_1_1 + x_2_0 <= 1
  connected_2_3_pos_0: x_2_0 <= 0
  connected_3_0_pos_0: x_0_1 + x_3_0 <= 1
  connected_3_2_pos_0: x_2_1 + x_3_0 <= 1
Binary
  x_0_1 x_1_0 x_1_1 x_2_0 x_2_1 x_3_0



collection.instances[0].data.plot()



<Axes: title={'center': 'Longest Path — 4 nodes, 0→3, length=2'}>


png