Solving the Max-Cut Problem with LunaSolve

Download Notebook

In this notebook, we'll explore how to tackle the MaxvCut problem using LunaSolve. First, we'll introduce and explain the Max-Cut problem through a straightforward example. Then, we'll walk step-by-step through modeling a real-world instance, optimizing the solution, and finally interpreting the results provided by LunaSolve.

1. What is Max-Cut?

The Max-Cut problem is a classic problem in combinatorial optimization and graph theory. Simply put, given a graph \(G\), the goal is to divide the nodes of \(G\) into two distinct groups, \(A\) and \(B\), so that the number of connections (edges) between these two groups is maximized.

Let's define this formally:

Suppose we have an undirected graph \(G = (V, E)\), where \(V\) represents vertices (nodes) and \(E\) represents edges (connections). A cut is created when we partition the nodes in \(V\) into two separate subsets, \(A\) and \(B\). The Max-Cut problem seeks the partition that maximizes the number of edges between these two groups.

While this might initially sound abstract, consider it this way: how can we divide a network into two groups to maximize the interaction across the groups?

2. A Real-World Example

To better understand the Max-Cut problem, let's look at an everyday scenario. Imagine a company wants to distribute promotional samples strategically to maximize word-of-mouth marketing.

In this scenario, each person represents a node, and friendships between people are represented as edges. Naturally, friends talk to each other, increasing the chances they'll discuss the new product.

The company's aim is to split their audience into two groups, group A and group B, in a way that maximizes the number of friendships (edges) between the two groups. This maximizes cross-group communication, amplifying the product's exposure without needing to distribute too many free samples. Typically, the smaller group might receive the samples, encouraging them to share their experiences with friends in the larger group.

This practical example illustrates clearly why Max-Cut is more than just a theoretical puzzle, rather it can be a useful tool for strategic decision-making in business and beyond.

3. Solving the Max-Cut 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 Max-Cut 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 Creating a Max-Cut Problem

To create a Max-Cut instance, we just need a graph with vertices and edges. Here, we'll build a graph representing friendships among nine individuals, labeled 0 through 8. Friendships between individuals are shown as edges connecting the nodes. After creating the graph, we'll visualize it to clearly illustrate these relationships.

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

# Create a graph
max_cut_graph = nx.Graph()

# Add the nodes of the graph, which represent the people of the example friendship network.
nodes = ["P0", "P1", "P2", "P3", "P4", "P5", "P6", "P7", "P8"]
max_cut_graph.add_nodes_from(nodes)

# Add the edges to the graph, which represent the friendships between the people.
edges = [
    ("P0", "P1"),
    ("P0", "P2"),
    ("P0", "P3"),
    ("P1", "P4"),
    ("P2", "P5"),
    ("P3", "P6"),
    ("P4", "P7"),
    ("P5", "P7"),
    ("P6", "P8"),
    ("P7", "P8"),
]
max_cut_graph.add_edges_from(edges)

# Draw the graph
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(max_cut_graph)
nx.draw(
    max_cut_graph,
    pos,
    with_labels=True,
    node_color="skyblue",
    edge_color="gray",
    node_size=1000,
    font_size=12,
)
plt.title("Example Max-Cut Network of 9 Points with Binary Edge Weights")
plt.show()

png

3.3 Defining the Max-Cut Data

The luna_usecases library ships the Max-Cut 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.

MaxcutData can be built straight from a NetworkX graph with MaxcutData.from_graph(), which reads the node names and the (optionally weighted) adjacency matrix off the graph for us.

# Import the Max-Cut data class from the luna_usecases library
from luna_usecases.maxcut import MaxcutData

# Describe the problem instance directly from the NetworkX graph
data = MaxcutData.from_graph(max_cut_graph)
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.maxcut import (
    MaxcutFormulation,
    MaxcutInstance,
)

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

# Combine data and formulation, then build the optimization model
instance = MaxcutInstance(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. To successfully create a job, we must first select an algorithm for the optimization from LunaSolve's collection, specify the algorithm's parameters and select a backend for the algorithm to run on.

In this instance, we solve the Max-Cut 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 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="Max-Cut 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. Turning a column of \(x_i\) values back into two groups of people 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 Max-Cut problem, this returns a MaxcutSolution holding the partition — which side of the cut each person ends up on — together with the achieved cut_value.

# Decode the raw solution back into the language of the use case
mc_solution = instance.interpret(solution)
print(mc_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.

mc_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 MaxcutCollection.from_random().
Swap SimulatedAnnealing for any other Luna algorithm — the model and the interpretation stay exactly the same.