Solving the Set Partitioning problem¶

In this notebook, we will describe how to solve the Set Partitioning problem with LunaSolve. We will begin by defining, explaining and giving an example for the Set Partitioning 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.

📥 Download the Notebook (.ipynb)

Table of Contents¶

Introduction
A Real World Example
Solving the Set Partitioning problem with Luna

Set Partitioning Problem¶

The Set Partitioning problem is a classic combinatorial optimization challenge in computer science and mathematics. It involves dividing a universal set into mutually exclusive subsets, meaning subsets that don’t overlap, such that every element in the universal set is included exactly once. The goal is to find such a partitioning while minimizing the total cost associated with the selected subsets.

Formally, the problem is defined as follows: Let $ U = {e_1, e_2, \ldots, e_n} $ be the universal set, and let $ \mathcal{S} = {S_1, S_2, \dots, S_n} $ be a family of subsets of $ U $, each with an associated cost $ c_j \ge 0 $.

We aim to select a sub-collection $ \mathcal{S}^* \subseteq \mathcal{S} $ such that:

Coverage: Every element of $ U $ is included in exactly one of the chosen subsets: $$ \bigcup_{S_i \in \mathcal{S}^} S_i = U \quad \text{and} \quad \forall S_i, S_j \in \mathcal{S}^ , \; i \neq j \Rightarrow S_i \cap S_j = \emptyset. $$
Optimality: The total cost of the selected subsets is minimized: $$ \min_{\mathcal{S}^ \subseteq \mathcal{S}} \sum_{S_i \in \mathcal{S}^} c_i. $$

Much like number partitioning, this problem has a wide range of practical applications in scheduling, resource allocation, workforce planning, and logistics, to name a few. The goal is always to allocate all resources from the universal set over the possible combinations (the subsets) as efficiently as possible, w.r.t. to each subset.

2. A Real-World Example¶

To illustrate, let’s consider a fictional example where we try to optimize the task allocation across workers to minimize the total working time. Each task is assigned to exactly one worker, and the cost of a subset could be the time required to complete its tasks, plus overheads such as setup time, overtime, or worker fatigue. Our goal is to assign tasks in such a way that no task is done more than once, and the overall cost is minimized.

Imagine we have six tasks—A, B, C, D, E, and F—each with a defined start time and duration. The objective is to group all tasks into work plans such that:

Each task is scheduled exactly once.
No two tasks in the same work plan overlap in time.
The cost of each work plan is minimized.

The cost of a work plan is defined as:

$$\text{Cost} = (\text{End time of last task} - \text{Start time of first task}) + 0.5 \text{ hours} $$ The added 0.5 hours accounts for overhead, such as check-in and check-out times at a facility.

The aim is to divide all tasks (the universal set) into groups (subsets) which entail all possible combinations and try to minimize the total cost!

Here's the task data:

Task	Start Time (hours)	Duration (hours)
A	0.0	1.5
B	1.0	2.0
C	2.0	2.0
D	2.5	2.0
E	3.5	2.0
F	5.0	1.5

To ensure feasibility, we only allow work plans that contain non-overlapping tasks. Based on this rule, we can construct a list of valid work plans (subsets) and calculate their associated costs:

Work Plan (Subset)	Cost (hours)
{A}	2.0
{B}	2.5
{C}	2.5
{D}	2.5
{E}	2.5
{F}	2.0
{A, C}	4.5
{A, D}	5.0
{A, E}	6.0
{A, F}	7.0
{B, E}	5.0
{B, F}	6.0
{C, F}	5.0
{D, F}	4.5
{A, C, F}	7.0
{A, D, F}	7.0

These precomputed work plans will form the basis of our optimization model in the following sections.

3. Solving the Set Partitioning problem with Luna¶

To follow along with the next steps, three libraries are needed: 1. luna_quantum for encoding and solving our optimization problem,

Run the cell below to install this library automatically if it isn't already installed.

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

3.1 Setting Up the Luna Client¶

Now let's dive into solving the Set Partitioning 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.

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)

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 Set Partitioning problem¶

An instance of the Set Partitioning problem needs a universal set, a collection of subsets of the universal set, and finally a cost associated with each subset. To parse this information to the SetPartitioning use case of Luna, we must define the universal set in the form of a list, the possible subsets as a list of lists, and the respective cost for each subset.

# Define the universal set
set = [1, 2, 3, 4, 5, 6] # A, B, C, D, E, F

# Define all possible subsets of the universal set
subsets = [
    [1],        # A
    [2],        # B
    [3],        # C
    [4],        # D
    [5],        # E
    [6],        # F
    [1, 3],     # A,C
    [1, 4],     # A,D
    [1, 5],     # A,E
    [1, 6],     # A,F
    [2, 5],     # B,E
    [2, 6],     # B,F
    [3, 6],     # C,F
    [4, 6],     # D,F
    [1, 3, 6],  # A,C,F
    [1, 4, 6]   # A,D,F
]

# Define the cost of each subset
costs = [
    2,  
    2,  
    2,  
    2,  
    2,  
    2,  
    4,  
    5,  
    6,  
    7,  
    5,  
    6,  
    5,  
    4,   
    7,   
    7   
]

3.3 Defining a Set Partitioning Object¶

To find the smallest partition of the universal set from the problem set using LunaSolve, we define the Set Partitioning use case using Luna’s SetPartitioning class. This class converts the problem instance into an optimization problem, which Luna can then optimize.

When initializing the SetPartitioning object, make sure to pass the universal set, the subsets and the costs. Additionally, the instance can also be given a name, which is set on default to SPP for the Set Partitioning problem.

# Import the SetPartitioning object from the luna sdk
from luna_quantum.solve.use_cases import SetPartitioning

# Create a SetPartitioning object
set_partition = SetPartitioning(set_=set, subsets=subsets, costs=costs)

3.4 Uploading the Use Case Model to Luna¶

Now, let's upload our Set Partitioning problem to Luna as an optimization task. We can use LunaSolve's ls.model.create_from_use_case() method and provide the use case object we just defined and assign a clear, identifiable name to the optimization.

# Initiliaze the optimization object using the created use case instance
model = ls.model.create_from_use_case(name="Set Partitioning Optimization", use_case=set_partition)

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 Set Partitioning 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 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 name for the job for easy identification.

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

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

# Execute an outbound solve request.
job = algorithm.run(model.id, name="Set Partitioning with SA")

3.6 Retrieving the Solution¶

In step 3.4, we uploaded our problem, and in step 3.5, we sent a solution request to Luna. 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()

The Solution object returns the sampled solutions in the native optimization format of the provider's solver together with its metadata. To interpret the solutions quicker, LunaSolve provides automatic post-processing functions which decode the samples back into an intuitive and easy-to-read format as below.

You can use the job.get_use_case_representation_result() method to retrieve the decoded form of the solution. This returns the solution in a readable format, with a few key components:

The sense attribute indicates whether our objective is to maximize or minimize the target function.
The result is typically an iterable containing the representation (the solution itself) and the corresponding obj_value (objective value). While the objective value can be complex due to embedded constraint penalties, generally, smaller values signify better solutions for minimization problems and vice versa for maximization problems.
The description helps clarify the format of the returned representation.

The representation of the Set Partitioning problem consists of a decoded list containing the indices of all subsets, as they are given in the defined subsets list earlier, which are selected to be part of the partition.

🔍 Upcoming Feature: Use Case Representation Analysis¶

Coming soon to the Luna SDK!

We're introducing a powerful new capability: Use Case Representation Analysis. This feature will allow you to analyze and visualize how your use cases are interpreted across models and workflows—giving you deeper insight into solution quality, representation alignment, and more.

✨ What to Expect
You'll soon be able to retrieve and examine the full use case representation for a given solve job:

use_case_result = ls.solve_job.get_use_case_representation(job.id)
print(use_case_result)

Finally, if we wish to only see the best solution from all evaluated samples we can call the job.get_use_case_representation_best_result() method.

best_use_case_result = ls.solve_job.get_best_use_case_result(use_case_result)
print(best_use_case_result)

Congrats! You have now solved the Set Partitioning problem using the use case library of Luna! If you are interested in finding out more about the plethora of different use cases Luna provides, we encourage you to explore the use case library!