Run on Jupyter Notebook

TutorialAn optimization problem refers to a problem that "determines the optimal choice from among a number of alternatives under various constraints". Some examples of optimization problems are as follows:

- Higher product performance, more efficient manufacturing process, cost reduction, yield improvement
- Planning of product orders, efficient distribution routes, management of financial assets
- Disaster recovery schedule, layout of public facilities, energy supply and demand balance

Describing such problems with mathematical formulas (mathematical models) and using mathematical calculation methods to find the best solution is called "mathematical optimization".

- Objective function: A mathematical expression that expresses the degree to which an objective is achieved (minimized or maximized)
- Decision variables: Variables that can represent choices
- Constraint: Possible conditional expressions between decision variables (constraint functions)

As a concrete example of a combinatorial optimization problem, let's consider the number partitioning problem.

Suppose that the set of $n$ integers $A$ is given as follows.

$$ A = \{a_0, a_1, \cdots, a_{n-1} \} $$Consider the division of $A$ into two sets $A_0$ and $A_1$. The following problems are considered to be the number division problem:

- Decision problem: Determine if there exists a partition of a set such that the sum of the elements of $A_0$ is equal to the sum of the elements of $A_1$.
- Optimization problem: Find the partition of the set that minimizes the difference between the sum of the elements of $A_0$ and the sum of the elements of $A_1$.

Consider the partition of the set of 10 integers $A=\{2,10,3,8,5,7,9,5,3,2\}$.

For example, if we divide the set as $A_0=\{2,3,5,7,10\}, A_1=\{2,3,5,8,9\}$, we can check that the sum of the elements of each set is equal. Therefore, the answer is "exists" for a decision problem, and the above $A_0, A_1$ is the answer for an optimization problem.

In this section, we solve an optimization problem on the number partitioning problem.

Let $n$ binary variables and Ising variables corresponding to each of the $n$ elements belonging to the set $A$ be the following $$ \begin{align} q_i &\in\{0, 1\}\quad (i=0, 1, \cdots, n-1) \quad \text{(Binary)}\\ s_i &\in\{-1, 1\}\quad (i=0, 1, \cdots, n-1) \quad \text{(Ising)} \end{align} $$ These variables mean that if $q_i=0$ ($s_i=-1$), $a_i$ belongs to $A_0$, and if $q_i=1$ ($s_i=1$), $a_i$ belongs to $A_1$. Let the union of the elements of the set $A_0$ be $S_0$ and the union of the elements of the set $A_1$ be $S_1$. $$ \begin{align} S_0 &= \sum_{a_i\in A_0}a_i\\ S_1 &= \sum_{a_i\in A_1}a_i \end{align} $$

Next, we consider creating an objective function. The objective function is a function of the above binary or Ising variables, such that it takes the minimum value if the conditions to be sought are satisfied. Here, in order to find a partition that satisfies the condition $S_0 = S_1$, we set the objective function as $(S_1 - S_0)^2$. When this condition is satisfied, the objective function becomes $0$ and takes the minimum value. Thus, using binary or Ising variables, the objective function $f$ can be expressed as follows:

$$ \begin{align} f &= \left(S_1 - S_0\right)^2 = \left(\sum_{a_i\in A_1}a_i - \sum_{a_i\in A_0}a_i\right)^2\\ &= \left(\sum_{i=0}^{n-1}(2q_i -1)a_i\right)^2 \quad \text{(Binary)}\\ &= \left(\sum_{i=0}^{n-1} a_i s_i \right)^2\quad \text{(Ising)} \end{align} $$The conversion from line 1 to line 2 (line 3) used the fact that $a_i$ is assigned to $A_0$ or $A_1$ when $q_i=1$ ($s_i=1$) or $q_i=0$ ($s_i=-1$), respectively. By checking whether the value of $f$ is $0$ or not, we can check whether the resulting partition satisfies the condition or not.

Ising variables are binary variables in $s_i\in\{1, -1\in\}$. You can generate an array of Ising
variables
by giving `IsingPoly`

as an argument to `gen_symbols`

.

The objective function using the Ising variable is given by:

$$ f = \left(\sum_{i=0}^{N-1}s_ia_i\right)^2 $$Let's implement this in Amplify.

In [ ]:

```
from amplify import (
gen_symbols,
IsingPoly,
)
# List of numbers corresponding to a set of numbers A
A = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]
# len(A): Number of variables
n = len(A)
# Generate Ising variables
s = gen_symbols(IsingPoly, n)
# Check the variables
print(s)
```

We construct the objective function using the list of numbers $A$ and the Ising variables generated earlier.

In [ ]:

```
# Constructing the objective function: Ising
f = IsingPoly()
for i in range(n):
f += s[i] * A[i]
f = f**2
```

We run the problem on the Ising machine.

In [ ]:

```
from amplify.client import FixstarsClient
from amplify import Solver
from amplify import decode_solution
# Set up the client
client = FixstarsClient()
client.parameters.timeout = 1000 # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.outputs.duplicate = (
True # Enumerate solutions with the same energy value
)
solver = Solver(client)
result = solver.solve(f)
```

In [ ]:

```
# If no solution is found, len(result) == 0
if len(result) == 0:
raise RuntimeError("No solution was found")
energy = result[0].energy
values = result[0].values
# Check the energy value (minimum value of f)
print(f"f = {energy}")
# Check the values
# Variable s_i's i=0, 1, ..., N-1 , a dictionary containing the values of N-1
print(f"values = {values}")
```

Since the value of $f$ is $0$, we know that we have found a solution that satisfies the condition.

You can use `decode_solution`

to assign the found solution to the original variables in
`s`

.

In [ ]:

```
from amplify import decode_solution
solution = decode_solution(s, values)
print(solution)
```

Finally, based on the obtained solution, the numbers in the set $A$ are divided into two groups.

Prepare two lists $A_0$ and $A_1$, and assign the numbers whose solutions correspond to $0$ to $A_0$ and otherwise to $A_1$.

In [ ]:

```
A0 = sorted([A[idx] for idx, val in enumerate(solution) if val != 1])
A1 = sorted([A[idx] for idx, val in enumerate(solution) if val == 1])
print(f"A0 = {A0}")
print(f"A1 = {A1}")
```

Verify that the sums of the numbers in $A_0$ and $A_1$ are equal. We can confirm that the sum is 27.

In [ ]:

```
print(f"{sum(A0) == sum(A1)}, {sum(A0)}")
```

In the previous problem, we showed how to get only one solution. However, in this problem, we can find
multiple solutions that satisfy the condition. In the setting of this partitioning problem, the
condition is
equivalent to the objective function being $0$. If there are multiple solutions that satisfy the
condition,
it means that there are multiple solutions with an energy value of $0.0$. Some machines can get more
than
one solutions with the same energy; in the case of Fixstars Optigan, you can set the parameter
`client.parameters.outputs.duplicate`

to `True`

to get multiple solutions.

In [ ]:

```
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
client.parameters.timeout = 1000 # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.outputs.duplicate = True # Option to list solutions with the same energy value (because there are multiple solutions)
solver = Solver(client)
result = solver.solve(f)
```

The fact that there are multiple solutions can be verified as follows. 46 solutions should be found.

In [ ]:

```
len(result)
```

In [ ]:

```
from amplify import decode_solution
partitions = set()
for sol in result:
solution = decode_solution(s, sol.values)
A0 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val != 1]))
A1 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val == 1]))
# If the same division is not already included in the list
if (A1, A0) not in partitions:
partitions.add((A0, A1))
for p in partitions:
print(f"sum = {sum(p[0])}, {sum(p[1])}, partition: {p}")
```

Binary variables are binary variables of $q_i\in\{1, 0\}$. You can generate an array of binary
variables by
giving `BinaryPoly`

as an argument to `gen_symbols`

.

The objective function with binary variables is given as follows:

$$ f = \left(\sum_{i=0}^{N-1}(2q_i -1)a_i\right)^2 $$Let's implement this in Amplify.

In [ ]:

```
from amplify import (
gen_symbols,
BinaryPoly,
)
# List of numbers corresponding to a set of numbers A
A = [2, 10, 3, 8, 5, 7, 9, 5, 3, 2]
# Number of variables
n = len(A)
# Generate binary variables
q = gen_symbols(BinaryPoly, n)
# Objective function construction: binary
f = BinaryPoly()
for i in range(n):
f += (2 * q[i] - 1) * A[i]
f = f**2
```

Let's run it as we did for the Ising variable.

In [ ]:

```
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
client.parameters.timeout = 1000 # Timeout is 1 second
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you are using it in a local environment, please enter the access token for Amplify AE
client.parameters.outputs.duplicate = True # Option to list solutions with the same energy value (because there are multiple solutions)
solver = Solver(client)
result = solver.solve(f)
from amplify import decode_solution
partitions = set()
for sol in result:
solution = decode_solution(q, sol.values)
A0 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val != 1]))
A1 = tuple(sorted([A[idx] for idx, val in enumerate(solution) if val == 1]))
# If the same division is not already included in the list
if (A1, A0) not in partitions:
partitions.add((A0, A1))
for p in partitions:
print(f"sum = {sum(p[0])}, {sum(p[1])}, partition: {p}")
```

We obtained the same solution as when we solved with the Ising variables.