Skip to content

Solve Your First Optimization Problem with LunaSolve

In this tutorial, you'll learn how to set up and solve an optimization problem using LunaSolve and the Quantum Approximate Optimization Algorithm (QAOA). We will specifically tackle the classic Traveling Salesman Problem (TSP) to demonstrate how this problem can be solved through an end-to-end process, covering all necessary steps from modeling to result interpretation.

🌟 What You'll Learn

By the end of this tutorial, you will:
✅ Create an optimization model for the TSP using AqModels
✅ Solve the problem using a QAOA algorithm and run it on a simulator or real quantum hardware.
✅ Analyze the optimization results.

Setup

Before starting, make sure that the following dependencies are installed:

pip install networkx matplotlib luna_quantum

Next, to start authenticate with your personal API key (LUNA_API_KEY) to securely access LunaSolve's services. If this feels unfamiliar to you, you can make a quick revision in the Get Started Guide.

from luna_quantum import LunaSolve
import getpass
import os

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: ")

ls = LunaSolve()

from luna_quantum import Logging
import logging

Logging.set_level(logging.WARNING)

🗺️ Step 1: Define the Traveling Salesman Problem (TSP)

The first step is to define the problem we are considering.

Imagine you’re responsible for delivering packages across the seven largest cities in Germany. Your goal is to find the shortest route that visits each city exactly once using the shortest path possible, to minimize your total transport costs. This type of problem is known as the Traveling Salesman Problem (TSP), a classic example of optimization and logistics. Solving it efficiently can lead to significant cost savings and improved operational efficiency.

The TSP problem can be represented as a weighted graph using the networkx package. Let's define a TSP graph, where each node represents one of the seven largest cities in Germany, and the edges are the distances between them.

import networkx as nx

# Create an empty graph
graph = nx.Graph()

# Define the cities
cities = ['Berlin', 'Hamburg', 'Munich', 'Cologne', 'Frankfurt', 'Stuttgart', 'Dresden']

# Add cities as nodes
graph.add_nodes_from(cities)

# Define distances between all cities
edges = [
 ('Berlin', 'Hamburg', 290),
 ('Berlin', 'Munich', 590),
 ('Berlin', 'Cologne', 570),
 ('Berlin', 'Frankfurt', 550),
 ('Berlin', 'Dresden', 200),
 ('Hamburg', 'Cologne', 420),
 ('Hamburg', 'Frankfurt', 490),
 ('Munich', 'Cologne', 590),
 ('Munich', 'Frankfurt', 390),
 ('Munich', 'Stuttgart', 220),
 ('Cologne', 'Frankfurt', 190),
 ('Cologne', 'Stuttgart', 350),
 ('Frankfurt', 'Stuttgart', 200),
 ('Frankfurt', 'Dresden', 460),
 ('Stuttgart', 'Dresden', 510),
]

# Add weighted edges
graph.add_weighted_edges_from(edges)

# Graph visualization
pos = nx.circular_layout(graph)
nx.draw(graph, pos, with_labels=True, node_color='lightblue', node_size=700, font_weight='bold')
nx.draw_networkx_edge_labels(graph, pos, edge_labels=nx.get_edge_attributes(G, 'weight'))
plt.title("Traveling Salesman Problem")
plt.axis('off')
plt.show()

🧩 Step 2: Create an AqModel

Now that we have defined our TSP problem with a graph we can move on to the next step. This involves creating a model representing the TSP based on the created network graph. The process of creating a model includes defining the decision variables, the objective function, and the model constraints. For the TSP, the decision variables are binary \(x_{ij}\) variables and encode which city \(i\) is assigned to each position \(j\) in the path. In other words, if \(x_{ij}\) is equal to one, city \(i\) is placed at position \(j\) in the graph. Further, the objective function aims to minimize the total traveled distance, while the constraints ensure each city is visited exactly once and each position in the route is assigned to exactly one city.

For a more detailed explanation of the TSP encoding, please visit the Modeling-Complex-Optimization-Problems documentation.

If you already have a model, you can use the .to_aq() method available in the LpTranslator, QuboTranslator, CqmTranslator, and BqmTranslator classes provided by the Translator class to translate and upload it right away.

from luna_quantum import LunaSolve
from luna_quantum import Model, Variable, Vtype, Sense

# Create the model
model = Model(name="Travelin Salesperson Problem")
# Set the Model to minimize the objective function
model.set_sense(Sense.Min)

# Declare decision variables within the model's environment
variables = {}
with model.environment:
    for node in graph.nodes():
        for path_order in range(len(graph.nodes())):
 variables[f"{node}_{path_order}"] = Variable(
 name=var_name, vtype=Vtype.Binary
 )

# Define the objective function of the TSP
model.objective = sum(
 variables[f"{node1}_{path_order}"]
 * variables[f"{node2}_{(path_order + 1) % len(graph.nodes())}"]
 * weight
    for node1, node2, weight in graph.edges(data="weight")
    for path_order in range(len(graph.nodes()))
)

# Define the city constraint.
# Every city must be visited exactly once
for node in graph.nodes():
 city_expression = sum(
 variables[f"{node}_{path_order}"] for path_order in range(len(graph.nodes()))
 )
 model.constraints += city_expression == 1, f"city_constraint_{node}"

# Define the path constraint.
# To every order in the path, exactly one city must be assigned
for path_order in range(len(graph.nodes())):
 position_expression = sum(variables[f"{node}_{path_order}"] for node in graph.nodes())
 model.constraints += position_expression == 1, f"path_order_constraint_{path_order}"

⚙️ Step 3: Choose a Solver

We have now successfully created the TSP input data and created out of it an optimization model. Now we must choose a solver to optimize our model. For this, we will choose the Quantum Approximate Optimization Algorithm (QAOA), which is among the most widely used quantum algorithms for solving combinatorial optimization problems. It is also particularly suitable for quadratic optimization problems, making it ideal for addressing the TSP.

In this tutorial, we run QAOA on IBM’s quantum simulator. The first step involves importing all necessary components, including the QAOA algorithm itself, the IBM backend, and parameter classes for both the QAOA algorithm and the classical optimizer. To initialize the algorithm, we need to specify the chosen parameters along with the backend interface and the optimizer.

Let's instantiate our QAOA algorithm. First, we set the backend parameter to IBM.SimulatorBackend. Next, we define the algorithmic parameters for QAOA. We set the number of repetitions, representing the total number of mixer and problem Hamiltonians layers, to five and the number of shots to 1024. A higher number of repetitions enables a more thorough exploration of the solution space but increases computational time. The number of shots determines how many times the algorithm runs, thus affecting the number of sampled measurements. Lastly, we select the optimization method to be the classical optimizer cobyla, and set the number of iterations to 100.

from luna_quantum.solve.parameters.algorithms import QAOA
from luna_quantum.solve.parameters.backends import IBM
from luna_quantum.solve.parameters.algorithms.base_params import (
 ScipyOptimizerParams
)

algorithm = QAOA(
    backend=IBM(
        backend=IBM.SimulatorBackend(
        backend_type='simulator',
        backend_name='aer',
        ),
    ),
    reps=5,
    shots=1024,
    optimizer=ScipyOptimizerParams(
        method='cobyla',
        tol=None,
        bounds=None,
        jac=None,
        hess=None,
        maxiter=100,
        options={},
        ),
    )

🚩 Step 4: Solve the TSP

Now it’s time to execute the optimization by creating an outbound job. This is done by executing the algorithm.run() method and passing the model along with a descriptive job name. Once submitted, LunaSolve creates a request, forwards it to the provider specified via the backend, and retrieves a set of sampled solutions once the computation has been completed.

# Execute an outbound solve request.
job = algorithm.run(model, name="TSP QAOA")

📊 Step 5: Retrieve and Interpret your Results

Once the optimization job is complete, it's time to inspect the results. Retrieve your solution using job.result(). This method returns a Solution object containing comprehensive information about the sampled solutions and relevant metadata. For an in-depth explanation of the Solution object, refer to our detailed Solution documentation.

solution = job.result()

The Solution object allows you to access all solution related information and metadata after the optimization is complete. Central to this is the solution.samples method, which lists all sampled solutions. The object also includes additional useful information such as the count (how often each sample occurred), the obj_values, raw_energies of each sample, and the total runtime.

To identify the solution with the best objective value, you can retrieve its index and then select the corresponding sample along with its objective value.

best_idx = solution.best_sample_idx
best_sample = solution.samples[best_idx]
best_value = solution.obj_values[best_idx]

Alternatively, you can identify the sample with the highest occurrence count by finding the index of the highest count and selecting the corresponding sample.

counts = solution.counts()
highest_count_idx = counts.index(max(counts))
highest_count_sample = solution.samples[highest_count_idx]

These results return the solutions for all binary decision variables \(x_{ij}\) which we defined earlier. To interpret these results meaningfully, we must decode the TSP solution's binary variable to identify the optimal path found. From the given solutions, you can reconstruct the routes by tracing the cities connected through variables where \(x_{ij}\) = 1, allowing you to visualize the sequence of cities in the best sampled tours.

However, at first glance, the results from this encoding might seem complex and non-intuitive. In this case, the TSP also happens to be one of many use cases pre-built in the use case library. These classes not only create the optimization model for you but also provide methods to decode your solutions. This enables an immediate interpretation of the encoded solutions we are given here. Visit the use case library to determine if your next model is included, and benefit from an accelerated workflow in your model definition and interpretation process.

Well done! 🚀 You’ve successfully solved your first optimization problem with LunaSolve using a quantum algorithm. You have now created a model, optimized it using the QAOA algorithm, and retrieved the results. You can now experiment further with your own models!

Next Steps

🎯 Want to try this on real quantum hardware? Update the backend to use a real QPU!

🔎 Explore more optimization problems using LunaSolve’s use case library in the Max-Cut tutorial!