Solving the Set Packing Problem¶

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

1. Introduction¶

Set Packing problem¶

The Set Packing problem is a fundamental problem in combinatorial optimization and computer science. A problem set is given which contains subsets from a universal set. The problem involves finding the maximal number of subsets in which all subsets have an intersection equal to the empty set. This problem has widespread applications in areas such as resource allocation, scheduling, network design, and information retrieval.

Formally, a universal set $U = \{e_1, e_2, \ldots, e_n\}$ and the family of subsets of $U$, $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ is defined, where each subset $(S_j \subseteq U)$ is associated with a cost $(c_j \ge 0)$. The Set Packing problem seeks to find a sub-collection $\mathcal{S}^* \subseteq \mathcal{S}$ such that:

No Overlap: $$ \forall\, S_i, S_j \in \mathcal{S}^* \text{ with } i \neq j,\quad S_i \cap S_j = \emptyset. $$
Optimality: $$ \max_{\mathcal{S}^ \subseteq \mathcal{S}} \sum_{S_i \in \mathcal{S}^} w_i. $$

This means we want to include as many subsets (based on their cost) while not creating overlaps between them. The diffference to Set Partitioning is that not all elements of the universal set must be included in the Set Packing problem. The question is rather, what is the largest packing size (the number of subsets chosen) while ensuring no overlap between the subsets.

2. A Real-World Example¶

Imagine you are managing a community center that offers various workshops to its members. Each workshop requires specific instructors, and each instructor can only teach one workshop at a time. During every hour of the day, lectures will be taking place simultaneously. Your goal is to schedule as many workshops as possible at each hour without any instructor being double-booked. This scenario encapsulates the essence of the Set Packing problem by trying to select the maximum number of mutually disjoint subsets (workshops which need instructors) while trying to not double allocate instructors (from the universal set). However if required an instructor can be left out and take a break.

An instance of the example might be as follows. At your community center, there will be a total of 5 instructors available (the universal set) which are needed in different combinations at 7 different workshops. Your task will be to select the largest subset of workshops where there are no staff conflicts between the workshops.

universal_set = {Instructor A,Instructor B,Instructor C,Instructor D,Instructor E}

workshop_set = {{W1 :{Instructor A,Instructor B}, W2:{Instructor B,Instructor C}, W3 :{Instructor C,Instructor D}, W4 :{Instructor D,Instructor E}, W5 :{Instructor A,Instructor E}, W6 :{Instructor B,Instructor D}, W7 :{Instructor C,Instructor E}}

This means that: - Workshop W1 requires instructor A and instructor B.
- Workshop W2 requires instructor B and instructor C.
- Workshop W3 requires instructor C and instructor D.
- Workshop W4 requires instructor D and instructor E.
- Workshop W5 requires instructor A and instructor E.
- Workshop W6 requires instructor B and instructor D.
- Workshop W7 requires instructor C and instructor E.

A trivial cost we could give to each workshop might be that of 1, where each is valued equally. However, we could also associate the expected number of interested visitors we expect for each workshop with the cost. Thereby aiming to maximize also the capacity for expected visitors.

3. Solving the Set Packing problem with Luna¶

To follow along with the next steps, the luna_quantum library is needed for encoding and solving our optimization problem.

The cell below installs these packages for you if they are not already installed.

# Install the python package that is 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 Packing 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 Packing Problem¶

To create a SetPacking instance we must encode our problem into a subset matrix of size (m x n), with m being the number of subsets and n the number of elements in the universal set. The subset matrix is made up of rows representing each subset. The $j_{th}$ value is 1 if element $j$ of the universal set is included in the subset represented by the row.

Additionally the weights of each subset are given as a list containing $m$ costs, one for each subset.

# Define the universal set
universal_set = [
    "Instructor A",
    "Instructor B",
    "Instructor C",
    "Instructor D",
    "Instructor E"
]

# Assigned pair of instructors (subset) for each workshop
workshops = {
    "W1": {"Instructor A", "Instructor B"}, 
    "W2": {"Instructor B", "Instructor C"},
    "W3": {"Instructor C", "Instructor D"}, 
    "W4": {"Instructor D", "Instructor E"}, 
    "W5": {"Instructor A", "Instructor E"},
    "W6": {"Instructor B", "Instructor D"}, 
    "W7": {"Instructor C", "Instructor E"}
}

# Create the subset matrix. Each row represents a workshop and each column represents an instructor.
# e.g. The first row encodes Workshop1, which is held by instructors A and B.
subset_matrix = [[1, 1, 0, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [1, 0, 0, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 1, 0, 1]]

# Set the weights for each subset
subset_weights = [1, 1, 1, 1, 1, 1, 1]

3.3 Defining a Set Packing Object¶

To find the largest packing of our subsets using LunaSolve, we define the Set Packing use case using Luna’s SetPacking class. This class converts the problem instance into an optimization problem, which Luna can then optimize. When initializing the set_packing object, ensure you pass the subset_matrix adn the weights. Optionally, you can provide a descriptive name for your instance—if not specified, LunaSolve defaults to SP for SetPacking.

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

# Create a Setpacking object, to use within the luna_sdk for optimisation
set_packing = SetPacking(subset_matrix=subset_matrix, weights=subset_weights)

3.4 Uploading the Use Case Model to Luna¶

Now, let's upload our Set Packing 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 Packing", use_case=set_packing)

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 Packing 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 Packing 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.

Accordingly, in the case of the Set Packing problem, the representation is a list which contains the indices of all subsets that have been selected to be included in the packing. In other words, the representation is a list of all indices $i$, for which their decision variable $x_i$ is equal to one.

🔍 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 view 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!