Set Cover
- class qubovert.problems.SetCover(*args, **kwargs)
SetCover.
Class to manage converting (Weighted) Set Cover to and from its QUBO and QUSO formluations. Based on the paper “Ising formulations of many NP problems”, hereforth designated as [Lucas].
The goal of the SetCover problem is to find the smallest number of subsets of U in V such that union over the elements equals U. The goal of the Weghted SetCover problem is to find the smallest weight of subsets of U in V such that union over the elements equals U, where each element in V has an associated weight.
This class inherits some methods and attributes from the
qubovert.problems.Problem
class.Example
>>> from qubovert.problems import SetCover >>> from any_module import qubo_solver >>> # or you can use my bruteforce solver... >>> # from qubovert.utils import solve_qubo_bruteforce as qubo_solver >>> U = {"a", "b", "c", "d"} >>> V = [{"a", "b"}, {"a", "c"}, {"c", "d"}] >>> problem = SetCover(U, V) >>> Q = problem.to_qubo() >>> obj, sol = qubo_solver(Q) >>> solution = problem.convert_solution(sol)
>>> print(solution) {0, 2} >>> print(problem.is_solution_valid(solution)) True # since V[0] + V[2] covers all of U >>> print(obj == len(solution)) True
__init__.
The goal of the SetCover problem is to find the smallest number of elements in V such that the union over the elements equals U. Weighted Set Cover is the task of finding the smallest weight of elements in V such that the union over the elements equals U, where each element in V has an associated weight. All naming conventions follow the names in the paper [Lucas].
- Parameters
U (set.) – The set of all elements to cover.
V (iterable of sets.) – Each set is one of the subsets.
weights (iterable of numbers (optional, defaults to None)) – Important: weights must be normalized such that max(weights) == 1; similarly, len(weights) == len(V). These are the weights for the weighted Set Cover problem. If weights is left to None, then the problem will default to the unweighted Set Cover problem (ie all the weights equal to 1).
log_trick (boolean (optional, defaults to True)) – Indicates whether or not to use the log trick discussed in [Lucas].
M (int (optional, defaults to None) We recommend not adjusting this.) – The number of duplicated elements to allow for, see [Lucas]. If M is None, then it will be set to the value required to ensure accuracy of the model. To possibly sacrifice accuracy but decrease the number of variables in the model, you can set M to something smaller.
- property M
A copy of the value for the M variable. See [Lucas].
- Returns
M
- Return type
int.
- property U
A copy of the U set. Updating the copy will not update the instance U.
- Returns
U – A copy of the set of all elements.
- Return type
set.
- property V
A copy of the V list/tuple. Updating the copy will not update the instance V.
- Returns
V – A copy of the subsets.
- Return type
iterable of sets.
- convert_solution(solution, spin=False)
convert_solution.
Convert the solution to the QUBO or QUSO to the solution to the Set Cover problem.
- Parameters
solution (iterable or dict.) – The QUBO or QUSO solution output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or -1 or 1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.
spin (bool (optional, defaults to False)) – spin indicates whether
solution
is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is ifsolution
contains all 1’s. In this case, it is unclear whethersolution
came from a spin or boolean formulation of the problem, and we will figure it out based on thespin
parameter.
- Returns
res – A set of which sets are included in the set cover. So if this function returns
{0, 2, 3}
, then the set cover is the setsV[0]
,V[2]
, andV[3]
.- Return type
set.
- is_coverable()
is_coverable.
Returns whether or not there exists a valid solution. Ie if there exists a combination of subsets in V that cover U.
- Returns
coverable – True if it is possible to construct a valid solution from V and U, False otherwise.
- Return type
bool.
Examples
>>> U = {0, 1, 2} >>> V = [{0}, {0, 1}] >>> SetCover(U, V).is_coverable() False
>>> U = {0, 1, 2} >>> V = [{0, 2}, {0, 1}] >>> SetCover(U, V).is_coverable() True
- is_solution_valid(solution, spin=False)
is_solution_valid.
Returns whether or not the proposed solution covers all the elements in U.
- Parameters
solution (iterable or dict.) – solution can be the output of SetCover.convert_solution, or the QUBO or QUSO solver output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.
spin (bool (optional, defaults to False)) – spin indicates whether
solution
is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is ifsolution
contains all 1’s. In this case, it is unclear whethersolution
came from a spin or boolean formulation of the problem, and we will figure it out based on thespin
parameter.
- Returns
valid – True if the proposed solution is valid, else False.
- Return type
boolean.
- property log_trick
log_trick.
A copy of the value for log_trick, indicating whether or not to use the log trick. See [Lucas].
- Returns
log_trick
- Return type
bool.
- property num_binary_variables
num_binary_variables.
The number of binary variables that the QUBO and QUSO use.
- Returns
num – The number of variables in the QUBO/QUSO formulation.
- Return type
int.
- solve_bruteforce(all_solutions=False)
solve_bruteforce.
Solves the Set Cover problem exactly with a brute force method. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! The advantage over this method as opposed to using a brute force QUBO solver is that the QUBO formulation has many slack variables.
- Parameters
all_solutions (boolean (optional, defaults to False)) – If
all_solutions
is set to True, all the best solutions to the problem will be returned rather than just one of the best. If the problem is very big, then it is best ifall_solutions == False
, otherwise this function will use a lot of memory.- Returns
res – A set of which sets are included in the set cover. So if this function returns
{0, 2, 3}
, then the set cover is the setsV[0]
,V[2]
, andV[3]
. Ifall_solutions == True
, thenres
will be a list of sets, where each element of the list is one of the optimal solutions.- Return type
set or list of sets.
Examples
>>> from qubovert import SetCover >>> U = {"a", "b", "c", "d"} >>> V = [{"a", "b"}, {"a", "c"}, {"c", "d"}] >>> problem = SetCover(U, V) >>> print(problem.solve_bruteforce()) {0, 2}
- to_pubo(*args, **kwargs)
to_pubo.
Since the model is already degree two,
self.to_pubo
will simply returnqubovert.utils.PUBOMatrix(self.to_qubo(*args, **kwargs))
.- Returns
P – The upper triangular PUBO matrix, a PUBOMatrix object. For most practical purposes, you can use PUBOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.PUBOMatrix)
.- Return type
qubovert.utils.PUBOMatrix object.
- to_puso(*args, **kwargs)
to_puso.
Create and return PUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls
to_pubo
orto_quso
and converts to a PUSO formulation.- Parameters
arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.
- Returns
H – For most practical purposes, you can use PUSOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.PUSOMatrix)
.- Return type
qubovert.utils.PUSOMatrix object.
- Raises
RecursionError` if neither to_pubo nor to_puso are define –
in the subclass. –
- to_qubo(A=2, B=1)
to_qubo.
Create and return the set cover problem in QUBO form following section 5.1 of [Lucas]. The Q matrix for the QUBO will be returned as an uppertriangular dictionary. Thus, the problem becomes minimizing \(\sum_{i \leq j} x_i x_j Q_{ij}\). A and B are parameters to enforce constraints.
If all the constraints are satisfied, then the objective function will be equal to the total number of sets in the cover (or for the weighted Set Cover problem, it will equal the total weight of included sets in the cover).
- Parameters
A (positive float (optional, defaults to 2)) – A enforces the constraints. See section 5.1 of [Lucas].
B (positive float that is less than A (optional, defaults to 1)) – See section 5.1 of [Lucas].
- Returns
Q – The upper triangular QUBO matrix, a QUBOMatrix object. For most practical purposes, you can use QUBOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.QUBOMatrix)
.- Return type
qubovert.utils.QUBOMatrix object.
- to_quso(*args, **kwargs)
to_quso.
Create and return QUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls
to_qubo
and converts the QUBO formulation to an QUSO formulation.- Parameters
arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.
- Returns
L – The upper triangular coupling matrix, where two element tuples represent couplings and one element tuples represent fields. For most practical purposes, you can use IsingCoupling in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.QUSOMatrix)
.- Return type
qubovert.utils.QUSOMatrix object.
- Raises
RecursionError` if neither to_qubo nor to_quso are define –
in the subclass. –
- property weights
weights.
A copy of the weights list/tuple. Updating the copy will not update the instance weights.
- Returns
weights
- Return type
iterable of numbers, where
max(weights) == 1
.