Solving the Max-Clique Problem with LunaSolve

Download Notebook

In this notebook, we'll explore how to tackle the Max-Clique problem using LunaSolve. First, we'll introduce and explain the Max-Clique 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. Max-Clique

The Max-Clique problem is a combinatorial optimization problem in graph theory where the goal is to find the largest clique. A Clique is a subset of vertices in a graph where every pair of vertices is connected by an edge. Intuitively, it is about identifying the largest fully connected subgraph of the graph.

However, the Max-Clique problem can also be expressed more precisely. Formally, a clique in an undirected graph \(G = (V, E)\), with vertices \(V\) and connecting edges \(E\), is a subset of vertices \(C \subseteq V\) such that for every pair of vertices \(u, v \in C\), the edge \((u,v)\) is in \(E\). Then the objective of the Max-Clique problem is to find a clique of maximum size in \(G\).

2. A Real World Example

To better illustrate the Max-Clique problem consider the following example. Imagine you're planning a small board games night. You want to create an enjoyable and harmonious atmosphere with a group of friends. So you decide to invite a group of friends who all know and get along with one another, from your various social circles. However the games are more fun the more participate, so you choose from all of your friends. The challenge you are facing is to identify the largest group from your social circle, such that everyone gets along well.

You have the following information about your friends Alice (A), Bob (B), Charlie (C), David (D), Emma (E), Frank (F), Grace (G), Henry (H), Irene (I), Jade (J), and Ken (K).

A knows B, C, and D.
B knows A, C, and D.
C knows A, B, and D.
D knows A, B, C, and E.
E knows F, D, J, I and K.
F knows E.
G knows H and I.
H knows G and I.
I knows G and H.
J knows E and K.
K knows E and J.

The connections of these relationships can be represented as a network or a graph and will also improve the visualisation of our problem at hand.

3. Solving the Max-Clique 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-Clique 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-Clique problem

To create a Max-Clique instance, any graph with vertices and edges is sufficient. In this notebook, we will create one representing the network of friendships among 11 of our friends. Each person is a node of the graph. Some pairs of our friends are also friends, and we express this attribute through an edge connecting the two nodes representing them. After defining the graph, we will visualize it for better comprehension.

import matplotlib.pyplot as plt
import networkx as nx

# Create the graph
max_clique_graph = nx.Graph()

# Add nodes to the graph (and represent our friends in the problem)
people = [
    "Alice",
    "Bob",
    "Charlie",
    "David",
    "Emma",
    "Frank",
    "Grace",
    "Henry",
    "Irene",
    "Jade",
    "Ken",
]
max_clique_graph.add_nodes_from(people)

# Add edges to the graph (and represent the relationships between our friends)
relationships = [
    ("Alice", "Bob"),
    ("Alice", "Charlie"),
    ("Alice", "David"),
    ("Bob", "Charlie"),
    ("Bob", "David"),
    ("Charlie", "David"),
    ("Emma", "David"),
    ("Emma", "Frank"),
    ("Emma", "Irene"),
    ("Grace", "Henry"),
    ("Henry", "Irene"),
    ("Irene", "Grace"),
    ("Emma", "Jade"),
    ("Jade", "Ken"),
    ("Ken", "Emma"),
]
max_clique_graph.add_edges_from(relationships)

# Draw the graph using the matplotlib library
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(max_clique_graph)
nx.draw(
    max_clique_graph,
    pos,
    with_labels=True,
    node_size=2000,
    font_size=12,
    node_color="lightblue",
    font_color="black",
    edge_color="gray",
)
plt.title("Friendship network", fontsize=16)
plt.show()

png

3.3 Defining the Max-Clique Data

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

MaxCliqueData describes the friendship network as a binary adjacency matrix plus the matching node names. NetworkX's nx.to_numpy_array() produces exactly that matrix; passing nodelist=people keeps its row and column order aligned with our friends' names.

# Import the Max-Clique data class from the luna_usecases library
from luna_usecases.max_clique import MaxCliqueData

# Turn the NetworkX graph into an adjacency matrix
adjacency_matrix = nx.to_numpy_array(max_clique_graph, nodelist=people)

# Describe the problem instance
data = MaxCliqueData.from_adjacency_matrix(
    adjacency_matrix=adjacency_matrix, node_names=people
)
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.max_clique import (
    MaxCliqueFormulation,
    MaxCliqueInstance,
)

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

# Combine data and formulation, then build the optimization model
instance = MaxCliqueInstance(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-Clique 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 exectue 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-Clique 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 a group of friends 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-Clique problem, this returns a MaxCliqueSolution holding the clique_nodes — the names of the people in the largest clique found — together with the clique_size and an is_valid flag.

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

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