Given a collection $S$ of subsets of a set $X$, the set packing problem tries to find the subsets that are pairwise disjoint (in other words, no two of them share an element). The goal is to maximize the number of such subsets.
We will go through two examples to show:
The problem is as follows. First, let us print the list of subsets.
import numpy as np
import json
from qiskit import BasicAer
from qiskit.optimization.applications.ising import set_packing
from qiskit.aqua.algorithms import NumPyMinimumEigensolver
from qiskit.optimization.applications.ising.common import sample_most_likely
input_file = 'sample.setpacking'
with open(input_file) as f:
list_of_subsets = json.load(f)
print(list_of_subsets)
[[4, 5], [4], [5]]
The brute-force method is as follows. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a subset is either 0 (meaning the subset is not taken) or 1 (meaning the subset is taken). We print the binary assignment that satisfies the definition of the set packing.
def brute_force():
# brute-force way: try every possible assignment!
def bitfield(n, L):
result = np.binary_repr(n, L)
return [int(digit) for digit in result] # [2:] to chop off the "0b" part
L = len(list_of_subsets)
max = 2**L
max_v = -np.inf
for i in range(max):
cur = bitfield(i, L)
cur_v = set_packing.check_disjoint(cur, list_of_subsets)
if cur_v:
if np.count_nonzero(cur) > max_v:
max_v = np.count_nonzero(cur)
return max_v
size = brute_force()
print("Size of set packing", size)
Size of set packing 2
qubit_op, offset = set_packing.get_operator(list_of_subsets)
Here we directly construct the algorithm and then run() it to get the result.
algo = NumPyMinimumEigensolver(qubit_op)
result = algo.run()
x = sample_most_likely(result.eigenstate)
ising_sol = set_packing.get_solution(x)
np.testing.assert_array_equal(ising_sol, [0, 1, 1])
oracle = brute_force()
print("Size of set packing", np.count_nonzero(ising_sol))
Size of set packing 2
We can create the objects directly ourselves too and run VQE for the result
from qiskit.aqua import aqua_globals
from qiskit.aqua.algorithms import VQE
from qiskit.aqua.components.optimizers import COBYLA
from qiskit.circuit.library import TwoLocal
aqua_globals.random_seed = 100
optimizer = COBYLA()
var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')
vqe = VQE(qubit_op, var_form, optimizer)
backend = BasicAer.get_backend('statevector_simulator')
result = vqe.run(backend)
x = sample_most_likely(result.eigenstate)
ising_sol = set_packing.get_solution(x)
print("Size of set packing", np.count_nonzero(ising_sol))
Size of set packing 2