Number Partitioning
- class qubovert.problems.NumberPartitioning(*args, **kwargs)
NumberPartitioning.
Class to manage converting the Number Partitioning problem 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 NumberPartitioning problem is as follows (quoted from [Lucas]):
Given a list of N positive numbers S = [n1, … , nN], is there a partition of this set of numbers into two disjoint subsets R and S − R, such that the sum of the elements in both sets is the same?
Note that if we can’t do this partitioning, then the next goal is to find a partition that almost does this, ie a partition that minimizes the difference in the sum between the two partitions.
This class inherits some methods and attributes from the Problem class. For more info, see
help(qubovert.problems.Problem)
.Example
>>> from qubovert.problems import NumberPartitioning >>> from any_module import qubo_solver >>> # or you can use my bruteforce solver... >>> # from qubovert.utils import solve_qubo_bruteforce as qubo_solver >>> S = [1, 2, 3, 4] >>> problem = NumberPartitioning(S) >>> Q = problem.to_qubo() >>> obj, sol = qubo_solver(Q) >>> solution = problem.convert_solution(sol)
>>> print(solution) ([1, 4], [2, 3]) # or ([2, 3], [1, 4])
>>> print(problem.is_solution_valid(solution)) True # since sum([1, 4]) == sum([2, 3])
>>> print(obj == 0) True # since the solution is valid.
__init__.
The goal of the NumberPartitioning problem is as follows (quoted from [Lucas]):
Given a list of N positive numbers S = [n1, … , nN], is there a partition of this set of numbers into two disjoint subsets R and S − R, such that the sum of the elements in both sets is the same?
Note that if we can’t do this partitioning, then the next goal is to find a partition that almost does this, ie a partition that minimizes the difference in the sum between the two partitions.
All naming conventions follow the names in the paper [Lucas].
- Parameters
S (tuple or list.) – tuple or list of N nonzero numbers that we are attempting to partition into two partitions of equal sum.
Example
>>> problem = NumberPartitioning([1, 2, 3, 4])
- property S
A copy of the S list. Updating the copy will not update the instance list.
- Returns
S – A copy of the list of numbers defining the partitioning problem.
- Return type
tuple or list.
- convert_solution(solution, spin=False)
convert_solution.
Convert the solution to the QUBO or QUSO to the solution to the Number Partitioning 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 –
- partition1list, tuple, or iterable.
The first partition. If the inputted S is a tuple, then partition1 will as a tuple, otherwise it will be a list.
- partition2list, tuple, or iterable.
The second partition.
- Return type
tuple of iterables (partition1, partition2)
Example
>>> problem = NumberPartitioning([1, 2, 3, 4]) >>> Q = problem.to_qubo() >>> value, solution = solve_qubo(Q) >>> print(solution) [0, 1, 1, 0] # ie 1 and 4 are in one partition, and 2 and 3 are in the other
>>> print(problem.convert_solution(solution)) ([1, 4], [2, 3])
- is_solution_valid(solution, spin=False)
is_solution_valid.
Returns whether or not the proposed solution partitions S into two sets of equal sum.
- Parameters
solution (iterable or dict.) – solution can be the output of NumberPartitioning.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 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(*args, **kwargs)
solve_bruteforce.
Solve the problem bruteforce. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! This is implemented in the parent
qubovert.utils.Problem
class. Some problems use a lot of slack binary variables for their QUBO/QUSO formulations. If this is the case, then the child class for this problem should override this method with a better bruteforce solver. But, for problems that do not use slack variables, this method will suffice. It converts the problem to QUBO, solves it withqubovert.utils.solve_qubo_bruteforce
, and then calls and returnsconvert_solution
.- Parameters
aruments (arguments and keyword arguments.) – Contains args and kwargs for the
to_qubo
method. Also contains aall_solutions
boolean flag, which indicates whether or not to return all the solutions, or just the best one found.all_solutions
defaults to False.- Returns
res – If
all_solutions
is False, thenres
is just the output of theconvert_solution
method. Ifall_solutions
is True, thenres
is a list of outputs of theconvert_solution
method, e.g. a converted solution for each solution that the bruteforce solver returns.- Return type
the output or outputs of the
convert_solution
method.
- 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(*args, **kwargs)
to_qubo.
Create and return upper triangular QUBO representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls
to_quso
and converts the quso formulation to a QUBO formulation.- Parameters
arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUBO.
- 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.
- Raises
RecursionError` if neither to_qubo nor to_quso are define –
in the subclass. –
- to_quso(A=1)
to_quso.
Create and return the number partitioning problem in QUSO form following section 2.1 of [Lucas]. It is the value such that the solution to the QUSO formulation is 0 if a valid number partitioning exists.
- Parameters
A (positive float (optional, defaults to 1)) – Factor in front of objective function. See section 2.1 of [Lucas].
- Returns
L – For most practical purposes, you can use QUSOMatrix in the same way as an ordinary dictionary. For more information, see
help(qubovert.utils.QUSOMatrix)
.- Return type
qubovert.utils.QUSOMatrix object.
Example
>>> problem = NumberPartitioning([1, 2, 3, 4]) >>> L = problem.to_quso()