# Number Partitioning¶

We will solver the number partitioning problem. We try to find the partion of numbers A to two groups, B and C, such that summation of B and that of C are equal.

# list of numbers
A = [10, 8, 7, 9]


We use Spin variables $$s_i$$ to formulate this problem. A spin variable only takes +1 or -1. $$s_i = +1$$ represents that element A[i] is belong to B, and $$s_i = -1$$ represents element A[i] is belong to C. In that time, the difference of the summation of elemements in B and that of C can be calculated by $$\sum_i a_i s_i$$.

Hence, we can obtain the desired partitioning by optimizing the spin variables to take minimum value of $$(\sum_i a_i s_i)^2$$.

min  sum( a_i s_i ) ^ 2
s.t. s_i in {-1, 1}


In flopt, we model the problem as follows.

import flopt

# create variables
s = flopt.Variable.array("s", len(A), cat="Spin")

# create problem
prob = flopt.Problem("Number Partitioning")

# set objective function
prob += flopt.dot(s, A) ** 2

print(prob)
>>> Name: Number Partitioning
>>>   Type         : Problem
>>>   sense        : minimize
>>>   objective    : (10*s_0+(8*s_1)+(7*s_2)+(9*s_3))^2
>>>   #constraints : 0
>>>   #variables   : 4 (Spin 4)


## Solving using RandomSearch¶

We search the optimal solution by RandomSearch. This is a simple sampling algorithm, which repeats to assigne random values to all variables in one search phase.

# solve until obtain the solution
# whose objective value is lower than or equal to 0
prob.solve(solver="Random", msg=True, lowerbound=0)

print("s", flopt.Value(s))
>>> s [1 -1 1 -1]


We succeeded to obtain the optimal solution.

## Conversion to other formulations of number partitioning¶

By using flopt.convert methods, we can obtain the structure data for another formulation of the number partitioning.

### QP¶

from flopt import Variable, Problem, Dot
from flopt.convert import QpStructure

s = Variable.array("x", len(A), cat="Spin")
prob = Problem("Number Partitioning")
prob += Dot(s, A) ** 2

# create QpStructure after binarize problem
flopt.convert.binarize(prob)
qp = QpStructure.fromFlopt(prob)

print(qp.show())
>>> QpStructure
>>> obj  1/2 x.T.dot(Q).dot(x) + c.T.dot(x) + C
>>> s.t. Gx <= h
>>>      Ax == b
>>>      lb <= x <= ub
>>>
>>> #x
>>> 4
>>>
>>> Q
>>> [[  0. 112. 160. 144.]
>>>  [112.   0. 140. 126.]
>>>  [160. 140.   0. 180.]
>>>  [144. 126. 180.   0.]]
>>>
>>> c
>>> [0. 0. 0. 0.]
>>>
>>> C
>>> 294
>>>
>>> G
>>> None
>>>
>>> h
>>> None
>>>
>>> A
>>> None
>>>
>>> b
>>> None
>>>
>>> lb
>>> [-1. -1. -1. -1.]
>>>
>>> ub
>>> [1. 1. 1. 1.]
>>>
>>> x
>>> [Variable("x_1", cat="Spin", ini_value=1)
>>>  Variable("x_2", cat="Spin", ini_value=-1)
>>>  Variable("x_0", cat="Spin", ini_value=-1)
>>>  Variable("x_3", cat="Spin", ini_value=-1)]


### LP¶

from flopt.convert import LpStructure
lp = LpStructure.fromFlopt(prob)

print(lp.show())
>>> LpStructure
>>> obj  c.T.dot(x) + C
>>> s.t. Gx <= h
>>>      Ax == b
>>>      lb <= x <= ub
>>>
>>> #x
>>> 10
>>>
>>> c
>>> [ 504.  560. -900.  720.  576. -756.  640. -960.  448. -832.]
>>>
>>> C
>>> 1156.0
>>>
>>> G
>>> [[ 0.  0.  0.  0.  0.  0.  1. -1.  0.  0.]
>>>  [ 0.  0.  0.  0.  0.  0.  1.  0.  0. -1.]
>>>  [-0. -0. -0. -0. -0. -0. -1.  1. -0.  1.]
>>>  [ 0.  1.  0.  0.  0.  0.  0. -1.  0.  0.]
>>>  [ 0.  1.  0.  0.  0. -1.  0.  0.  0.  0.]
>>>  [-0. -1. -0. -0. -0.  1. -0.  1. -0. -0.]
>>>  [ 0.  0.  0.  1.  0.  0.  0. -1.  0.  0.]
>>>  [ 0.  0. -1.  1.  0.  0.  0.  0.  0.  0.]
>>>  [-0. -0.  1. -1. -0. -0. -0.  1. -0. -0.]
>>>  [ 0.  0.  0.  0.  0.  0.  0.  0.  1. -1.]
>>>  [ 0.  0.  0.  0.  0. -1.  0.  0.  1.  0.]
>>>  [-0. -0. -0. -0. -0.  1. -0. -0. -1.  1.]
>>>  [ 0.  0.  0.  0.  1.  0.  0.  0.  0. -1.]
>>>  [ 0.  0. -1.  0.  1.  0.  0.  0.  0.  0.]
>>>  [-0. -0.  1. -0. -1. -0. -0. -0. -0.  1.]
>>>  [ 1.  0.  0.  0.  0. -1.  0.  0.  0.  0.]
>>>  [ 1.  0. -1.  0.  0.  0.  0.  0.  0.  0.]
>>>  [-1. -0.  1. -0. -0.  1. -0. -0. -0. -0.]]
>>>
>>> h
>>> [0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1.]
>>>
>>> A
>>> None
>>>
>>> b
>>> None
>>>
>>> lb
>>> [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
>>>
>>> ub
>>> [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
>>>
>>> x
>>> [Variable("mul_5", cat="Binary", ini_value=0)
>>>  Variable("mul_1", cat="Binary", ini_value=0)
>>>  Variable("x_3_b", cat="Binary", ini_value=0)
>>>  Variable("mul_2", cat="Binary", ini_value=0)
>>>  Variable("mul_4", cat="Binary", ini_value=0)
>>>  Variable("x_2_b", cat="Binary", ini_value=0)
>>>  Variable("mul_0", cat="Binary", ini_value=0)
>>>  Variable("x_0_b", cat="Binary", ini_value=0)
>>>  Variable("mul_3", cat="Binary", ini_value=0)
>>>  Variable("x_1_b", cat="Binary", ini_value=1)]


### Ising¶

from flopt.convert import IsingStructure
ising = IsingStructure.fromFlopt(prob)

print(ising.show())
>>> IsingStructure
>>> - x.T.dot(J).dot(x) - h.T.dot(x) + C
>>>
>>> #x
>>> 4
>>>
>>> J
>>> [[  -0. -160. -140. -180.]
>>>  [  -0.   -0. -112. -144.]
>>>  [  -0.   -0.   -0. -126.]
>>>  [  -0.   -0.   -0.   -0.]]
>>>
>>> h
>>> [-0. -0. -0. -0.]
>>>
>>> C
>>> 294.0
>>>
>>> x
>>> [Variable("x_0", cat="Spin", ini_value=-1)
>>>  Variable("x_1", cat="Spin", ini_value=1)
>>>  Variable("x_2", cat="Spin", ini_value=-1)
>>>  Variable("x_3", cat="Spin", ini_value=-1)]


### Qubo¶

from flopt.convert import QuboStructure
qubo = QuboStructure.fromFlopt(prob)

print(qubo.show())
>>> QuboStructure
>>> x.T.dot(Q).dot(x) + C
>>>
>>> #x
>>> 4
>>>
>>> Q
>>> [[-960.  640.  560.  720.]
>>>  [   0. -832.  448.  576.]
>>>  [   0.    0. -756.  504.]
>>>  [   0.    0.    0. -900.]]
>>>
>>> C
>>> 1156.0
>>>
>>> x
>>> [Variable("x_0_b", cat="Binary", ini_value=0)
>>>  Variable("x_1_b", cat="Binary", ini_value=1)
>>>   Variable("x_2_b", cat="Binary", ini_value=0)
>>>    Variable("x_3_b", cat="Binary", ini_value=0)] ] ] ]]