Number Partitioning

Number Partitioning#

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

What is number partitioning?#

Number partitioning is the problem of dividing a given set of numbers into two sets such that the sum of the numbers is equal. Let us consider a simple example.

For example, we have such a set of numbers \(A = \{1, 2, 3, 4\}\). It is easy to divide \(A\) to \(\{1, 4\}, \{2, 3\}\), and we can get the sum of each subset as 5. Thus, when the size of the set is small, the answer is relatively easy to obtain. However, the larger problem size is hard to solve quickly. For this reason, we explain how to solve this problem using annealing in this tutorial.

Mathematical model#

First, let us model the Hamiltonian of this problem. Let \(A\) be the set to be partitioned, and \(A\) has elements \(a_i \ (i = \{0, 1, \dots, N-1\})\), where \(N\) is the number of elements in this set. We consider dividing \(A\) into two sets \(A_0\) and \(A_1\). We define a binary variable \(x_i\) that is 0 when \(a_i\) is contained in \(A_0\) and 1 when \(a_i\) is contained in \(A_1\). Using \(x_i\), the total value of the numbers into \(A_0\) can be written as \(\sum_i a_i(1-x_i)\), and the sum of \(A_1\) is \(\sum_i a_i x_i\). We need to find a solution that satisfies the constraint that the sum of each of the two subsets is equal.

\[ \sum_{i=0}^{N-1} a_i (1-x_i) = \sum_{i=0}^{N-1} a_i x_i \ \Longrightarrow \ \sum_{i=0}^{N-1}a_i (2 x_i - 1) = 0 \tag{1} \]

Applying the penalty method to (1) yields the Hamiltonian for the number partitioning.

\[ H = \left\{ \sum_{i=0}^{N-1} a_i (2 x_i - 1) \right\}^2 \tag{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.

import jijmodeling as jm

a = jm.Placeholder("a",ndim = 1)
N = a.shape[0]
x = jm.BinaryVar("x",shape=(N,))
i = jm.Element("i",belong_to=(0,N))

a is a one-dimensional array representing the elements in \(A\). We can get the number of elements N from the length of a. We define a binary variable x. Finally, we define the subscript i used in (2).
Then, we implement the Hamiltonian of number partitioning.

problem = jm.Problem("number partition")
s_i = 2*x[i] - 1
problem += (jm.sum(i, a[i]*s_i)) ** 2

We can check the implementation of the mathematical model on the Jupyter Notebook.

problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{number partition} & & \\& & \min \quad \displaystyle \left(\left(\sum_{i = 0}^{\mathrm{len}\left(a, 0\right) - 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}\]

Prepare an instance#

We prepare a set of numbers \(A\). Here, we consider the problem of partitioning numbers from 1 to 40. In the problem of partitioning consecutive numbers from \(N_i\) to \(N_f\), and the number of numbers is even, there are various patterns of partitioning. However, the total value of the partitioned set can be calculated as follows:

\[ (\mathrm{total \ value}) = \frac{(N_f + N_i) (N_f - N_i + 1)}{4} \]

In this case, the total value is expected to be 410. Let’s check it.

import numpy as np

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

Solve by JijSolver#

We solve this problem using jijsolver.

import jijsolver
 
interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

Visualize the solution#

Let’s check the result obtained. We separate the indices classified as \(A_0\) and \(A_1\). Finally, we sum over them.

df = solution.decision_variables
x_1_indices = np.ravel(df[df["value"]==1.0]["subscripts"].to_list())
x_0_indices = np.ravel(df[df["value"]==0.0]["subscripts"].to_list())
A_1 = instance_data["a"][x_1_indices]
A_0 = instance_data["a"][x_0_indices]
print(f"class 1 : {A_1} , total value = {np.sum(A_1)}")
print(f"class 0 : {A_0} , total value = {np.sum(A_0)}")

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

As we expected, we obtain both total values are 410.

Contents