# 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 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

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 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 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 with `qubovert.utils.solve_qubo_bruteforce`, and then calls and returns `convert_solution`.

Parameters

aruments (arguments and keyword arguments.) – Contains args and kwargs for the `to_qubo` method. Also contains a `all_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, then `res` is just the output of the `convert_solution` method. If `all_solutions` is True, then `res` is a list of outputs of the `convert_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 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(*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()
```