Skip to content

Solving the Longest Path Problem

Download Notebook

In this notebook, we will describe how to solve the Longest Path problem with LunaSolve. We will begin by defining, explaining and giving an example for the Longest Path problem. We will then continue by modeling a problem instance, optimize it and implement the solution using LunaSolve. Finally, we will also take a further look at the interpretation of the answer we are returned from Luna.

Table of Contents

  1. Introduction
  2. A Real World Example
  3. Solving the Longest Path problem with Luna

1. Longest Path Problem

The Longest Path problem is a well-known combinatorial optimization challenge in graph theory and computer science. The task is to find the longest possible path between a specified start and end node in a graph \(G\), without visiting any vertex more than once.

The length of a path can be measured in two ways: by the number of edges (in unweighted graphs) or by the sum of edge weights (in weighted graphs).

Formally, given a graph \(G = (V, E)\), where \(V = \{ v_1, v_2, \ldots, v_n \}\) is the set of vertices, \(E\) is the set of edges, and \(v_s\) and \(v_e\) are the designated start and end vertices. A longest path in \(G\) is a sequence of vertices \((v_{p(1)}, v_{p(2)}, \ldots)\) such that:

  1. The total number of edges (or total weight, in a weighted graph) along the path is maximized.
  2. Every pair of consecutive vertices in the sequence is connected by an edge: \((v_{p(i)}, v_{p(i+1)}) \in E\).
  3. The first and last vertices in the sequence are \(v_s\) and \(v_e\), respectively.

2. Description of a Real World Example

One key use case of the Longest Path problem is in scheduling and planning, especially in project management, where tasks often depend on one another.

In such settings, tasks are represented as vertices, and dependencies are represented as directed edges. The edge weights can correspond to task durations. The longest path through this network reveals the critical path, the sequence of tasks that determines the minimum time required to complete the entire project. Delays in any task on the critical path will delay the whole project.

Let’s walk through an example project:

Tasks: A, B, C, D, E
Durations: - A: 2 days - B: 4 days - C: 3 days - D: 2 days - E: 5 days

Dependencies (Edges): - A must be completed before B and C can start. - B and C must both finish before D can start. - D must be completed before E begins.

In this case, A is the starting task and E is the final task. The graph structure captures task relationships and durations as edge weights. By finding the longest path from A to E, we identify the critical path of the project.

3. Solving the Longest Path problem with Luna

To follow along with the next steps, you'll need the following libraries: 1. luna_usecases for modeling our optimization problem, 2. luna_quantum for solving it, 3. matplotlib for visualizing the results, and 4. networkx for creating and displaying the graphs.

Run the cell below to install these libraries automatically if they aren't already installed.

%%capture
# Install the python packages that are needed for the notebook
%pip install --upgrade pip
%pip install luna_quantum luna_usecases --upgrade
%pip install matplotlib networkx

3.1 Setting Up the Luna Client

Now let's dive into solving the Longest Path problem using LunaSolve. First, you'll instantiate a LunaSolve object and configure your credentials. The API key identifies your account and grants access to Luna's services. You can find your API key in your Aqarios account settings.

import os
import getpass

os.environ["LUNA_LOG_DEFAULT_LEVEL"] = "WARNING"
os.environ["LUNA_LOG_DISABLE_SPINNER"] = "true"

if "LUNA_API_KEY" not in os.environ:
    # Prompt securely for the key if not already set
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

from luna_quantum import LunaSolve

LunaSolve.authenticate(os.environ["LUNA_API_KEY"])
ls = LunaSolve()

If you haven't yet configured a QPU token for your account, or if you'd like to add a new one, you can do so using the ls.qpu_token.create() method. However, in this tutorial we will be using a classical solver from Dwave, which does not require one.

3.2 Create a Longest Path problem

The Longest Path use case works on an undirected, weighted graph together with a start node, a terminal node and the number of nodes the path should visit. In this notebook, we will create a graph representing the task dependencies. Each task is a node of the graph, a connection between two nodes symbolizes a dependency between the two tasks, and the edge weight is the duration of that step.

After defining the graph, we will visualize it for better comprehension.

# Import the necessary packages
import matplotlib.pyplot as plt
import networkx as nx

# Create the graph
longest_path_graph = nx.Graph()

# Define and add nodes of the graph that represent the tasks
tasks = ["A", "B", "C", "D", "E"]
longest_path_graph.add_nodes_from(tasks)

# Define and add the edges (dependencies between tasks) with weights equal to the duration of the starting task
edges = [("A", "B", 2), ("A", "C", 2), ("B", "D", 4), ("C", "D", 3), ("D", "E", 2)]
for u, v, w in edges:
    longest_path_graph.add_edge(u, v, weight=w)

# Draw the Graph
pos = nx.spring_layout(longest_path_graph, seed=42)

nx.draw_networkx_nodes(longest_path_graph, pos, node_color="lightblue", node_size=1000)
nx.draw_networkx_edges(longest_path_graph, pos, edge_color="gray")
nx.draw_networkx_labels(longest_path_graph, pos, font_size=12, font_weight="bold")
edge_labels = nx.get_edge_attributes(longest_path_graph, "weight")
nx.draw_networkx_edge_labels(
    longest_path_graph, pos, edge_labels=edge_labels, font_size=12
)
plt.title("Project Tasks as a Weighted Graph")
plt.axis("off")
plt.show()

3.3 Defining the Longest Path Data

The luna_usecases library ships the Longest Path problem as a ready-made use case. Every use case in the library follows the same five-part contract — Data, Formulation, Instance, Solution and Collection — so once you have worked through one use case, all the others work the same way.

We start with the Data class, which holds the problem instance itself.

LongestPathData takes the weighted adjacency matrix of the graph and the matching node names, which nx.to_numpy_array() gives us directly. On top of that it needs the start_node, the terminal_node and the path_length, i.e. the number of nodes the path has to visit. Our project starts with task "A" and ends with task "E", and we are looking for the longest chain that touches four of the five tasks.

# Import the Longest Path data class from the luna_usecases library
from luna_usecases.longest_path import LongestPathData

# Turn the NetworkX graph into a weighted adjacency matrix
adjacency_matrix = nx.to_numpy_array(longest_path_graph, nodelist=tasks, weight="weight")

# Describe the problem instance
data = LongestPathData.from_adjacency_matrix(
    adjacency_matrix=adjacency_matrix,
    node_names=tasks,
    start_node="A",
    terminal_node="E",
    path_length=4,
)
print(data.to_string())

3.4 Building the Optimization Model

Next we choose a Formulation. The formulation is the recipe that turns the data into decision variables, an objective function and constraints. Printing it is a quick way to check what the resulting model will look like before it is built.

Data and formulation are then combined into an Instance, and instance.formulate() returns the optimization Model — the very same model object you would otherwise have to write by hand, ready to be handed to any Luna algorithm.

from luna_usecases.longest_path import (
    LongestPathFormulation,
    LongestPathInstance,
)

# Choose the formulation and inspect how the problem will be modeled
formulation = LongestPathFormulation()
print(formulation.to_string(data))

# Combine data and formulation, then build the optimization model
instance = LongestPathInstance(data=data, formulation=formulation)
model = instance.formulate()

3.5 Choose an Algorithm and Run It

The final step is to create a job request, sending our optimization task to the hardware provider to solve. In order to successfully create a job, we must first select an algorithm from LunaSolve's collection for the optimization, specify the algorithm's parameters and select a backend for the algorithm to run on.

In this instance, we solve the Longest Path problem using simulated annealing (sa) and choose D-Wave (dwave) as the hardware provider. Simulated annealing has multiple parameters which can be adjusted to fine-tune the exact optimization. Here we are only going to set the num_reads equal to 1000. This means that the annealing process is done 1000 times, returning 1000 sampled results.

Lastly, we execute the job by calling the algorithm.run() method and passing the model together with a chosen namefor the job for easy identification.

from luna_quantum.algorithms import SimulatedAnnealing
from luna_quantum.backends import DWave

# Select the SimulatedAnnealingSolver algorithm.
algorithm = SimulatedAnnealing(
    backend=DWave(),
    num_reads=1000,
)

# Execute an outbound solve request.
job = algorithm.run(model, name="Longest-Path with SA")

3.6 Retrieving the Solution

In step 3.4, we built the optimization model, and in step 3.5, we sent it to Luna to be solved. Luna automatically manages the subsequent background processes. This includes preparing the optimization problem, converting it into the correct format for the quantum hardware provider, submitting the problem to the quantum computer, and finally retrieving and translating the solution back into a user-friendly format.

Now let's discuss the final stages: retrieving the solution, converting it back to our original problem representation, and interpreting the results.

First, we'll use the job.result() method to fetch our results. The returned Solution object contains several attributes related to the optimization, including metadata such as the runtime, the count (how often each sample occurred), the objective_value and raw_energies of each sample. To learn more about the Solution Object visit Luna's thorough documentation.

solution = job.result()
print(solution)

3.7 Interpreting the Solution

The Solution object above reports the samples in the raw decision variables of the model. Reading a schedule out of a table of \(x_{i,j}\) values is possible, but tedious.

This is where the Instance pays off a second time: instance.interpret() decodes a raw Solution back into the language of the use case. For the Longest Path problem, this returns a LongestPathSolution holding the path itself, its total_weight — the duration of the critical chain we were looking for — and an is_valid flag.

# Decode the raw solution back into the language of the use case
lp_solution = instance.interpret(solution)
print(lp_solution.to_string())

Every use case solution can also draw itself. Passing the original problem data lets the solution highlight the result on top of the problem it belongs to.

lp_solution.plot(data)
plt.show()

Next Steps

  • Browse the full catalogue of ready-made problems in the use case library.
  • Generate whole benchmark sets of random instances with LongestPathCollection.from_random().
  • Swap SimulatedAnnealing for any other Luna algorithm — the model and the interpretation stay exactly the same.