# 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 + V 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 if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin 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 sets V, V, and V.

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 if solution contains all 1’s. In this case, it is unclear whether solution came from a spin or boolean formulation of the problem, and we will figure it out based on the spin 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 if all_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 sets V, V, and V. If all_solutions == True, then res 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 return qubovert.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 or to_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.