Tutorials

In this section, you will find several applicational examples on how Luna can be used to solve real-world problems.

Problem Description

Shipping wholesale products across Germany

Imagine the task of efficiently coordinating the shipment of wholesale products across Germany. You have retailers in the seven largest German cities and aim to deliver all your products at once while taking the shortest route possible to minimize transportation costs.

In technical terms, this challenge is known as the Traveling Salesman Problem (TSP) , one of the most extensively studied optimization problems. It finds applications in various fields like planning, logistics, DNA sequencing, and even astronomy through slightly modified problem formulations.

Luna already allows you to create and solve a TSP without any manual work. You can visit our page on our preimplemented Use Cases to find out more about this problem.

In simple terms, a TSP is fully defined by a weighted graph. Each node represents a city and each edge the distance between two cities.

Creating a TSP instance

To create such a graph for a TSP, you can provide Luna with either a nested dictionary or a graph created using networkx. For simplicity and improved code readability, let's go with the latter approach.

import networkx as nx

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

# Define the cities we want to visit
cities = ['Berlin', 'Hamburg', 'Munich', 'Cologne', 'Frankfurt', 'Stuttgart', 'Düsseldorf']

# Add the cities as nodes in our graph
graph.add_nodes_from(cities)

# Define the distances between each city
edges = [('Berlin', 'Hamburg', 289),
         ('Berlin', 'Munich', 586),
         ('Berlin', 'Cologne', 574),
         ('Berlin', 'Frankfurt', 567),
         ('Berlin', 'Stuttgart', 634),
         ('Berlin', 'Düsseldorf', 565),
         ('Hamburg', 'Munich', 796),
         ('Hamburg', 'Cologne', 425),
         ('Hamburg', 'Frankfurt', 493),
         ('Hamburg', 'Stuttgart', 656),
         ('Hamburg', 'Düsseldorf', 401),
         ('Munich', 'Cologne', 589),
         ('Munich', 'Frankfurt', 392),
         ('Munich', 'Stuttgart', 233),
         ('Munich', 'Düsseldorf', 632),
         ('Cologne', 'Frankfurt', 190),
         ('Cologne', 'Stuttgart', 377),
         ('Cologne', 'Düsseldorf', 42),
         ('Frankfurt', 'Stuttgart', 205),
         ('Frankfurt', 'Düsseldorf', 257),
         ('Stuttgart', 'Düsseldorf', 416)]

# Add the distances as the edges in our graph
graph.add_weighted_edges_from(edges)

With this, we have defined our graph and, as a result, have already provided all the necessary specifications for a TSP. However, to actually transform this graph into a problem solvable using algorithms, you would typically need a mathematical model that enables communication with these algorithms designed to tackle such optimization problems. The good news is that we have already taken care of implementing this mathematical model for you, so you don't need to handle it yourself.

Now, you can proceed to send our graph to Luna and generate a TSP instance.

# Load the luna package
from luna_sdk import LunaSolve
from luna_sdk.schemas.use_cases import TravellingSalesmanProblem

# Create a LunaSolve object and set your credentials
luna = LunaSolve(email="YOUREMAIL", password="YOURPASSWORD")

# Convert the networkx graph to a digestible format for Luna
graph_data = nx.to_dict_of_dicts(graph)

# Define that we want to create a TSP with the corresponding graph data
use_case = TravellingSalesmanProblem(graph=graph_data)

# Create a TSP instance and retrieve the corresponding ID
created_optimization = luna.optimization.create_from_use_case(
  name="a name",
  use_case=use_case,
)

This covers all that is needed to create a TSP instance using Luna. We can now proceed to the step of selecting an appropriate algorithm to solve our specific problem.

Choosing an Algorithm

Within Luna, you have access to a diverse range of pre-implemented algorithms, which are designed to solve various types of optimization problems. You can either manually choose an algorithm that best fits your needs, or take advantage of our Recommendation Engine. This engine will provide you with a recommendation on the most efficient algorithm, along with suggestions for the most suitable hardware to achieve optimal results.

Please note that the current version of our recommendation engine focuses on selecting from our available classical algorithms. However, we are actively working on introducing quantum algorithms in future versions.

Accessing the Recommendation Engine is straightforward – it's an integral part of LunaSolve, our dedicated service designed to efficiently solve real-world optimization challenges.

To receive a recommendation, all you need to do is instruct LunaSolve to provide you with one. You'll need to supply the ID of the TSP instance we previously created.

from luna_sdk.schemas.recommendation import Recommendation

# Query the recommendation engine with our TSP instance
optimization_instance_id = created_optimization.id
recommendation = luna.optimization.optimization.get_recommendation(optimization_instance_id)

With the recommendation in hand, you can now proceed directly to solving the problem using the suggested algorithm. If you're curious about the details of the recommendation, you can take a look before moving forward.

print(recommendation)

{
  "solver": "tabu_search",
  "solver_params": {
    "num_reads": 1
  }
}

This will display all the relevant information about the chosen algorithm and its corresponding parameters. However, it's not necessary for you to delve into these details in order to simply apply the algorithm.

Solving the Problem Instance

With our TSP instance created and a recommended algorithm obtained, we can now proceed to solve the problem. Thanks to Luna's interface, this can be achieved with just a single line of code.

# Solve the TSP instance using our recommended algorithm and retrieve a solution url
solution = luna.optimization.create_solution(
    optimization_id=optimization_instance_id,
    solver_name=recommendation.solver,
    solver_parameters=recommendation.solver_params,
)

Since certain algorithms, particularly those executed on quantum hardware, may require some time for completion, we have designed the process to be asynchronous. When you request a solution, Luna will manage all the necessary steps in the background. You're free to continue with other tasks while the computation is underway, returning at your convenience when it's finished.

As the raw output generated by these algorithms might not be immediately intuitive, especially if you're not well-versed in optimization methods, Luna offers a solution. We provide the capability to translate this raw output back into the context of your initial problem formulation. In the case of a TSP, this translation could simply involve generating a list of cities in the order they should be visited.

from luna_sdk.schemas.solution import Solution
from luna_sdk.schemas.enums.status import StatusEnum

# Check solution status. The status will be "DONE" once the solution is ready.
while solution.status != StatusEnum.DONE:
    # wait for 10 seconds before checking the status again 
    sleep(10)
    solution = luna.optimization.get_solution(solution_id=solution.id)

# After the execution of your algorithm has been finished, retrieve your transformed solution
solution = luna.optimization.get(solution_id=solution.id)

# Print the solution and check the order in which we should visit the cities
print(solution)

[
  'Hamburg',
  'Berlin',
  'Munich',
  'Stuttgart',
  'Frankfurt',
  'Cologne',
  'Düsseldorf'
]

And with that, we've completed the process. As you've observed, Luna efficiently guides you through all the essential steps required to solve your optimization problems. Even if you're not well-versed in quantum computing or optimization techniques, you can seamlessly navigate the process. However, if you're interested in delving deeper into each step and customizing the process, you can explore our intermediate or experts tutorials.

The following chapters might use the term QUBO (Quadratic Unconstrained Binary Optimization), which is a mathematical formulation used to represent optimization problems. If you are unfamiliar with QUBOs, we link you a tutorial here.