Solving the Set Partitioning problem

Download Notebook

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.

Table of Contents

1. Introduction
2. A Real World Example
3. Solving the Set Partitioning problem with Luna

1. 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}^\star \subseteq \mathcal{S}\) such that:

1. Coverage: Every element of \(U\) is included in exactly one of the chosen subsets: \(\bigcup_{S_i \in \mathcal{S}^\star} S_i = U \quad \text{and} \quad \forall S_i, S_j \in \mathcal{S}^\star , \; i \neq j \Rightarrow S_i \cap S_j = \emptyset.\)

2. Optimality: The total cost of the selected subsets is minimized: \(\min_{\mathcal{S}^\star \subseteq \mathcal{S}} \sum_{S_i \in \mathcal{S}^\star} 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:

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:

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, you'll need the following libraries: 1. luna_usecases for encoding our optimization problem, 2. luna_quantum for solving it, and 3. matplotlib for visualizing the results.

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

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.

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 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. We start by writing them down as a list, a list of lists, and a list of costs.

# Define the universal set
universal_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 the Set Partitioning Data

The luna_usecases library ships the Set Partitioning 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.

SetPartitioningData.from_values() expects the subsets as a binary subset_matrix of size (m x n), with m being the number of subsets and n the number of elements in the universal set. Row \(i\), column \(j\) is 1 exactly when element \(j\) of the universal set belongs to subset \(i\). Converting our list of subsets into that matrix is a one-liner.

# Import the Set Partitioning data class from the luna_usecases library
from luna_usecases.set_partitioning import SetPartitioningData

# Encode the subsets as a binary subset matrix
subset_matrix = [
    [1 if element in subset else 0 for element in universal_set] for subset in subsets
]

# Describe the problem instance
data = SetPartitioningData.from_values(
    subset_matrix=subset_matrix, costs=[float(cost) for cost in costs]
)
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.set_partitioning import (
    SetPartitioningFormulation,
    SetPartitioningInstance,
)

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

# Combine data and formulation, then build the optimization model
instance = SetPartitioningInstance(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 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.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="Set Partitioning 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_s\) values back into a partition 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 Set Partitioning problem, this returns a SetPartitioningSolution holding the selected_subsets — the indices of the chosen subsets — their total_cost, and an is_valid flag confirming that every element of the universal set is covered exactly once.

# Decode the raw solution back into the language of the use case
spp_solution = instance.interpret(solution)
print(spp_solution.to_string())

# Map the selected subset indices back to the subsets themselves
print("Chosen subsets:", [subsets[i] for i in spp_solution.selected_subsets])

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.

import matplotlib.pyplot as plt

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