Example NP problems published in A. Lucas, Front. Phys. (2014) - Set packing problem¶

This example code implements the set packing problem introduced in the paper A. Lucas, "Ising formulations of many NP problems", Front. Phys. (2014) using Fixstars Amplify. Other NP-complete and NP-hard problems introduced in the same paper are also discussed below (the corresponding sections in the paper are shown in the brackets).

Graph partitioning problem (Sec. 2.2).
Maximum clique problem (Sec. 2.3)
Exact cover problem (Sec. 4.1)
Set packing problem (Sec. 4.2)
Minimum vertex cover problem (Sec. 4.3)
Satisfiability problem (SAT) (Sec. 4.4)
Minimal maximal matching problem (Sec. 4.5)
Graph coloring problem (Sec. 6.1)
Clique cover problem (Sec. 6.2)
Job sequencing problem with integer lengths (Sec. 6.3)
Hamiltonian cycle problem (Sec. 7.1)
Directed feedback vertex set problem (Sec. 8.3)
Minimum feedback edge set problem (Sec. 8.5)
Graph isomorphism problem (Sec. 9)

Set packing problem¶

Suppose there is a set $S$ and given subsets $T_0, T_1, \ldots, T_{N-1}$ of $S$. The problem of selecting some of $T_0, T_1, \dots, T_{N-1}$ so that they have no common parts and making the sum of the number of elements of the selected subsets as large as possible is called the set packing problem.

For example, consider the case shown in the figure below where $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and $T_0 = \{1, 2, 3, 6, 9\}$, $T_1 = \{1, 2, 5, 8\}$, $T_2 = \{4, 7\}$, $T_3 = \{4, 5\}$ and $T_4 = \{6, 9\}$ as the subsets. In this case, if $T_1$, $T_2$, and $T_4$ are chosen, the sum of the number of elements is $8$, which is the maximum. On the other hand, since $T_0$ and $T_1$, for example, have a common part, they cannot be chosen at the same time.

This example program uses Fixstars Amplify to solve the set packing problem. The formulation follows that of Sec. 4.2 of A. Lucas, Front. Phys. (2014).

Problem definition¶

As an example, we implement the above problem setting as follows.

In [ ]:

S = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # Set S
T = [[1, 2, 3, 6, 9], [1, 2, 5, 8], [4, 7], [4, 5], [6, 9]]  # Subsets of S

Formulation¶

Decision variables¶

Let $N$ binary variables $q$ correspond to $T_0, T_1, \ldots, T_{N-1}$ to indicate whether to select the corresponding subset $T_i$. If we choose $T_i$, $q_i$ is $1$; if not, $0$.

For example, when choosing three subsets of $T_1$, $T_2$, and $T_4$, the decision variable $q$ is as follows

Subset	$$T_0$$	$$T_1$$	$$T_2$$	$$T_3$$	$$T_4$$
$$q$$	0	1	1	0	1

Objective function¶

Since we want the sum of the number of elements in the chosen subsets to be as large as possible, the objective function is:

$$ -\sum_{i = 0}^{N - 1} q_i \cdot (\# T_i). $$

Here, $\# T_i$ is the number of elements in $T_i$. The minus sign is to convert the maximization problem into a minimization problem.

Constraints¶

We need to impose the condition that "the chosen subsets have no overlap" on $q$:

$$ q_i q_j = 0 \quad \text{if} \quad T_i\ \text{and} \ T_j \ \text{overlap}. $$

Implementation¶

Using the problem and formulation described above, let us implement and solve the problem. First, create as many binary variables $q$ as there are subsets using the BinarySymbolGenerator in the Fixstars Amplify SDK.

In [ ]:

from amplify import VariableGenerator
    
N = len(T)
    
gen = VariableGenerator()
q = gen.array("Binary", N)

Next, we implement the objective function. As mentioned above, the objective function is written as $-\sum_{i = 0}^{N - 1} q_i \cdot (\# T_i)$, which can be implemented as follows.

In [ ]:

import numpy as np
    
subset_lengths = np.array([len(t) for t in T])  # Array of (#T_i)
cost = -(q * subset_lengths).sum()

The next step is to implement the constraints. We can write the constraints follows:

$$ q_i q_j = 0 \ \bigl(\text{if} \:\: T_i \:\: \text{and} \:\: T_j \:\: \text{overlap}\bigr). $$

In [ ]:

from amplify import equal_to, sum as amplify_sum
import itertools
    
    
def overlap(t_i, t_j):
    return len(set(t_i) & set(t_j)) > 0
    
    
constraints = amplify_sum(
    equal_to(q[i] * q[j], 0)
    for i, j in itertools.combinations(range(N), 2)
    if overlap(T[i], T[j])
)

Now, we combine the created objective function and constraints into a logical model.

The constraints are given to the Ising machine as penalty functions for the objective function. Thus, we need to appropriately set a weight for the constraints, which can be determined by estimating values equivalent to or slightly larger than the possible values of the objective function. In this case, the weights for the constraints are $\max(\#T_i)$.

In [ ]:

model = cost + np.max(subset_lengths) * constraints

Let us set the client and solve the logical model with Fixstars Amplify Annealing Engine (AE). Since Amplify SDK automatically filters the solutions that satisfy the constraints, if the result is not empty, you know that there is a solution that satisfies the constraints.

In [ ]:

from amplify import FixstarsClient, solve
from datetime import timedelta
    
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = timedelta(milliseconds=1000)  # timeout is 1000 ms
    
# Solve the problem
result = solve(model, client)
    
if len(result) == 0:
    print("No solution has been found.")
else:
    print("A solution has been found.")

Finally, let us visualize the results. You can also try different sets $S$ or its subsets $T_i$.

In [ ]:

print(
    f"Sum of the element: {int(-result.best.objective)}"
)  # Show the best objective function value
values = q.evaluate(result.best.values)
for i in np.where(values == 1)[0]:
    print(f"T{i} : {T[i]}")