Number Partitioning

Number Partitioning#

Here we show how to solve the number partitioning problem using OpenJij, JijModeling, and ommx-openjij-adapter. This problem is also mentioned in 2.1. Number Partitioning in Lucas, 2014, “Ising formulations of many NP problems”.

Overview of the Number Partitioning Problem#

Number partitioning is the problem of dividing a given set of numbers into two subsets such that the sum of the numbers is equal.

Example#

Let us have a set of numbers \(A=\{1, 2, 3, 4\}\). It is easy to divide this set into equal sums: \(\{1, 4\}, \{2, 3\}\) and the sum of each subset is 5. Thus, when the size of the set is small, the answer is relatively easy to obtain. When the problem is large, however, it is not immediately solvable. Here, we solve this problem using annealing.

import openjij as oj
import jijmodeling as jm
import numpy as np

Mathematical Model#

First, let us model the Hamiltonian of this problem. Let \(A\) be the set to be partitioned and \(a_i (i = \{0,1,\dots,N-1\})\) be its elements. Here \(N\) is the number of elements in this set. We consider dividing \(A\) into two sets \(A_0\) and \(A_1\). Let \(x_i\) be a variable whose \(i\)th element of \(A\) is 0 when it is contained in the set \(A_0\) and 1 when it is contained in \(A_1\). Using this variable \(x_i\), the total value of the numbers in \(A_0\) is written as \(\sum_i a_i (1-x_i)\) and \(\sum_i a_i x_i\) for \(A_1\). As we find a solution that satisfies the constraint that the sum of the numbers contained in \(A_0\) and \(A_1\) be equal, this can be expressed as:

\[\sum_i a_i (1-x_i)=\sum_i a_i x_i\]

The problem is to find \(x_i\) that satisfies the constraint. By transforming this expression, we can write \(\sum_i a_i (2-x_i)=0\), and by using the Penalty method and squaring this constraint, the Hamiltonian for the number-splitting problem is:

\[H=\left( \sum_{i=0}^{N-1} a_i (2-x_i)\right)^2\]

Modeling by JijModeling#

Next, we show how to implement the above equation using JijModeling. We first define variables for the mathematical model described above.

problem = jm.Problem("number partition")
a = jm.Placeholder("a", ndim = 1)
N = a.len_at(0, latex="N")
x = jm.BinaryVar("x",shape=(N,))
i = jm.Element("i",(0,N))
s_i = 2*x[i] - 1
problem += (jm.sum(i,a[i] * s_i))**2
problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{number partition} & & \\& & \min \quad \displaystyle \left(\left(\sum_{i = 0}^{N - 1} a_{i} \cdot \left(2 \cdot x_{i} - 1\right)\right)^{2}\right) & \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

Instance#

As an example, let us solve an easy problem; let us consider the problem of dividing numbers from 1 to 40. When dividing consecutive numbers from \(N_i\) to \(N_f\) and keeping the total number of consecutive numbers even, there are several patterns of division. However, the total value of the divided set is:

\[\mathrm{total\ value} = \frac{(N_{i} + N_{f})(N_{f} - N_{i} + 1)}{4}\]

In this case, the total value is expected to be 410. Let us confirm this.

N = 40
instance_data = {"a":np.arange(1,N+1)}

Create Instance#

instance = jm.Interpreter(instance_data).eval_problem(problem)

Solve by OpenJij#

import ommx_openjij_adapter as oj_ad

sampleset = oj_ad.OMMXOpenJijSAAdapter.sample(
    instance,
    uniform_penalty_weight=0.8,
    num_reads=100,
)
best_sample = sampleset.best_feasible_unrelaxed()

Decoding and Displaying the Solution#

Let us take a look at the results obtained. We decode the returned calculation results to facilitate analysis.

# decode a result to JijModeling sampleset
# get the indices of x == 1x
x_value = best_sample.extract_decision_variables("x")
class_1_indices = [k[0] for k, v in x_value.items() if v == 1]
class_0_indices = [k[0] for k, v in x_value.items() if v == 0]

class_1 = instance_data["a"][class_1_indices]
class_0 = instance_data["a"][class_0_indices]

print(f"class 1 : {class_1} , total value = {np.sum(class_1)}")
print(f"class 0 : {class_0} , total value = {np.sum(class_0)}")

class 1 : [ 2  4  7 10 11 13 15 16 19 20 21 22 23 24 26 28 35 37 38 39] , total value = 410
class 0 : [ 1  3  5  6  8  9 12 14 17 18 25 27 29 30 31 32 33 34 36 40] , total value = 410

As expected, both total values are 410. Above, we dealt with a problem whose solution is known because it is a consecutive number. We recommend you try more complex problems, such as generating numbers randomly.

Contents