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.

Mathematical Model#

First, let us consider the mathematical model for 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\). Since this problem requires finding 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 this constraint.

Formulation with JijModeling#

Next, we show how to formulate the above mathematical model using JijModeling. We first define the variables and parameters used in the model.

import jijmodeling as jm

problem = jm.Problem("Number Partition")

a = problem.Float("a", ndim=1)
N = problem.DependentVar("N", a.len_at(0))
x = problem.BinaryVar("x", shape=(N, ))

Here, a is defined as a one-dimensional array representing the elements of \(A\), N as the number of elements in \(A\) (automatically determined from the length of a), and x as a binary variable used for optimization.

Constraint#

The constraint can be formulated as follows.

problem += problem.Constraint("equal", (jm.sum(N, lambda i: a[i]*(1-x[i])) == jm.sum(N, lambda i: a[i]*x[i])))

Let us check the formulation in the Jupyter Notebook.

problem
\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{Number Partition}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{equal}&\quad \displaystyle \sum _{i=0}^{N-1}{{a}_{i}\cdot \left(1-{x}_{i}\right)}=\sum _{i=0}^{N-1}{{a}_{i}\cdot {x}_{i}}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}N&=\mathop{\mathtt{len\_{}at}}\left(a,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

Creating an 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.

import numpy as np

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

Running Optimization with OpenJij#

Let us solve the optimization problem using OpenJij’s simulated annealing.

from ommx_openjij_adapter import OMMXOpenJijSAAdapter

instance = problem.eval(instance_data)

adapter = OMMXOpenJijSAAdapter(instance)
best_sample = adapter.sample(instance, num_reads=10, uniform_penalty_weight=0.8).best_feasible_unrelaxed

Visualizing the Solution#

Here, we separate the indices classified into \(A_0\) and \(A_1\) in \(A\), and compute their sums.

# decode a result to JijModeling sampleset
# get the indices of x == 1
df = best_sample.decision_variables_df
class_0_indices = [row['subscripts'][0] for _, row in df.iterrows() if row['name'] == 'x' and row['value'] <= 0.5]
class_1_indices = [row['subscripts'][0] for _, row in df.iterrows() if row['name'] == 'x' and row['value'] > 0.5]

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

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

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