# Solving a Combinatorial Optimization Problem

This page explains how to solve a combinatorial optimization problem using the model {py:class}`~amplify.Model` and solver client created in "[](model.md)" and "[](clients.md)."

## Solve function

The Amplify SDK provides the {py:func}`~amplify.solve` function to perform combinatorial optimization. This function takes {py:class}`~amplify.Model` as its first argument and a solver client object as its second argument. It optimizes the model using the solver corresponding to the solver client.

Let's optimize the following example using Amplify AE.

```{math}
\begin{aligned}
    \text{minimize: } \quad & f = q_0 q_1 - q_2 \\
    \text{subject to: } \quad &  q_0 + q_1 + q_2 = 1, \\
    & q_0, q_1, q_2 \in \{0, 1\}
\end{aligned}
```

First, we create a model by constructing the objective function and constraints.

```{testcode}
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve

gen = VariableGenerator()
q = gen.array("Binary", 3)

objective = q[0] * q[1] - q[2]
constraint = one_hot(q)

model = objective + constraint
```

Then, we create a solver client for Amplify AE and set the timeout period to 1000 milliseconds.

```{testcode}
from datetime import timedelta

client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
```

```{testcode}
:hide:
import os

client.url = os.getenv("TEST_AE_URL", "")
client.token = os.getenv("TEST_AE_TOKEN", "")
```

Now, we can pass the model and solver client to the {py:func}`~amplify.solve` function and run the solver as follows.

```{testcode}
result = solve(model, client)
```

The results obtained can be verified as follows. See "[](solver-result)" for more information.

```{doctest}
>>> print(f"objective = {result.best.objective}")
objective = -1.0
>>> print(f"q = {q.evaluate(result.best.values)}")
q = [0. 0. 1.]
```

```{seealso}
The Amplify SDK automatically performs model transformations as needed to make the input model client-ready. These transformations include penalty function calculations, variable conversions, degree reduction, and graph embedding. The {py:func}`~amplify.solve` function lets you specify parameters for this model transformation. See the "[](#conversion-parameters)" pages for a detailed description of each parameter.
```

### Skipping the model construction

Suppose the model consists only of an objective function or only of constraints. In that case, you can pass an object of the class {py:class}`~amplify.Poly` directly as the first argument of the {py:func}`~amplify.solve` function. You can also pass an object of the class {py:class}`~amplify.Constraint` or {py:class}`~amplify.ConstraintList`.

```{testcode}
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint1 = one_hot(q[0] + q[1])
constraint2 = one_hot(q[1] + q[2])

client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
```

```{testcode}
:hide:
import os

client.url = os.getenv("TEST_AE_URL", "")
client.token = os.getenv("TEST_AE_TOKEN", "")
```

Solving an unconstrained combinatorial optimization problem:

```{testcode}
result = solve(objective, client)
```

Solving a combinatorial optimization problem with a single constraint:

```{testcode}
result = solve(constraint1, client)
```

Solving a combinatorial optimization problem with multiple constraints:

```{testcode}
result = solve(constraint1 + constraint2, client)
```

(solver-result)=

## Retrieving the result

The {py:class}`~amplify.Result` object returned by the {py:func}`~amplify.solve` function contains information about the solution returned by the solver and the time taken to run it.

```python
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint = one_hot(q)
model = objective + constraint

client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)

result = solve(model, client)
```

```{testcode}
:hide:
from amplify import VariableGenerator, one_hot, AmplifyAEClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint = one_hot(q)
model = objective + constraint

client = AmplifyAEClient()
client.url = os.getenv("TEST_AE_URL", "")
client.token = os.getenv("TEST_AE_TOKEN", "")
client.parameters.time_limit_ms = timedelta(milliseconds=1000)

result = solve(model, client)
```

You can obtain the number of solutions in {py:class}`~amplify.Result` with the {py:func}`len` function. Only solutions that satisfy all constraints are included in {py:class}`~amplify.Result` by default.

```{doctest}
>>> len(result)
1
```

If {py:class}`~amplify.Result` contains multiple solutions, you can use the {py:attr}`~amplify.Result.best` property to find the best solution.

```{doctest}
>>> type(result.best)
<class 'amplify.Result.Solution'>
```

The best solution obtained with the {py:attr}`~amplify.Result.best` property is an instance of the {py:class}`~amplify.Result.Solution` class. This class has the following attributes.

```{list-table}
- * {py:attr}`~amplify.Result.Solution.objective`
  * The value of the objective function
- * {py:attr}`~amplify.Result.Solution.values`
  * The value of each variable in the solution
- * {py:attr}`~amplify.Result.Solution.feasible`
  * Whether the constraint is satisfied or not
- * {py:attr}`~amplify.Result.Solution.time`
  * The time at which the solver finds the solution
```

For the best solution, you can obtain the values of the objective function, the values of the variables, and whether all constraints are satisfied. You can also obtain the time at which the solution was found, as follows:

```{doctest}
>>> result.best.objective
-1.0
>>> result.best.values
Values({Poly(q_0): 0, Poly(q_1): 0, Poly(q_2): 1})
>>> result.best.feasible
True
>>> result.best.time # doctest: +SKIP
datetime.timedelta(microseconds=27965)
```

Pass {py:attr}`~amplify.Result.Solution.values` to the {py:meth}`~amplify.PolyArray.evaluate` method of the variable array. You then obtain the solution values corresponding to each variable in the array. These values form an {py:class}`~numpy.ndarray` of the same form as the variable array.

```{doctest}
>>> print(q.evaluate(result.best.values))
[0. 0. 1.]
```

```{attention}
Depending on the solver used, it may not be possible to obtain the time at which the solver found the solution. In such cases, the {py:attr}`~amplify.Result.Solution.time` attribute will have the same value as the solver's {py:attr}`~amplify.Result.execution_time`. See "[](timing.md)" for more information.
```

{py:class}`~amplify.Result` can contain not only the best solution but also multiple solutions. You can obtain each solution as an instance of the {py:class}`~amplify.Result.Solution` class by indexing on {py:class}`~amplify.Result`.

```{doctest}
>>> result[0].objective
-1.0
>>> result[0].feasible
True
```

Iterative access is also possible.

```{doctest}
>>> for r in result:
...     print(r.objective)
...     print(r.values)
...     print(r.feasible)
...     print(r.time) # doctest: +SKIP
-1.0
amplify.Values({Poly(q_0): 0.0, Poly(q_1): 0.0, Poly(q_2): 1.0})
True
0:00:00.028060
```

```{seealso}
The {py:class}`~amplify.Result` object also contains model transformation, graph embedding, and runtime information. See "[](evaluation.md)" for details.
```

## Options for the execution result output

By default, the {py:class}`~amplify.Result` object returned by the {py:func}`~amplify.solve` function contains only solutions that satisfy the constraints in ascending order of objective function values. You can change this behavior by setting the `filter_solution` and `sort_solution` keyword arguments to the {py:func}`~amplify.solve` function.

(filter-solution)=

### Filtering the solution

If you set the `filter_solution` keyword argument to the {py:func}`~amplify.solve` function to {py:obj}`False`, solutions that do not satisfy the constraints may be included in {py:class}`~amplify.Result`.

```{testcode}
from amplify import VariableGenerator, equal_to, Model, AmplifyAEClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)

client = AmplifyAEClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
```

```{testcode}
:hide:
import os
client.url = os.getenv("TEST_AE_URL", "")
client.token = os.getenv("TEST_AE_TOKEN", "")
```

```{doctest}
>>> result1 = solve(model, client)
>>> len(result1)
0
>>> result2 = solve(model, client, filter_solution=False)
>>> len(result2)
1
>>> result2.best.feasible
False
```

Even after you call the {py:func}`~amplify.solve` function, you can set the {py:attr}`~amplify.Result.filter_solution` property of {py:class}`~amplify.Result` to {py:obj}`False`. This includes solutions that do not satisfy the constraint conditions in {py:class}`~amplify.Result`.

```{doctest}
>>> result = solve(model, client)
>>> len(result)
0
>>> result.filter_solution = False
>>> len(result)
1
```

### Sorting solutions

The Amplify SDK sorts the solutions included in {py:class}`~amplify.Result` in ascending order by default. If you specify {py:obj}`False` for the `sort_solution` keyword argument to the {py:func}`~amplify.solve` function, the solutions keep the order that the solver returned.

```{testcode}
result = solve(model, client, sort_solution=False)
```

You can also sort the solutions later using {py:class}`~amplify.Result`'s {py:meth}`~amplify.Result.sort` method.

```{testcode}
result.sort()
```

```{note}
The Amplify SDK determines the goodness of the solution in the following order.
1. Whether the constraints are satisfied
2. Whether the value of the objective function is smaller

Therefore, the {py:attr}`~amplify.Result.best` property of {py:class}`~amplify.Result` obtains one solution, if any. It is the solution with the smallest objective function value among the solutions that satisfy the constraints. If no solution satisfies the constraint condition, the Amplify SDK returns the solution with the smallest objective function value if {py:attr}`~amplify.Result.filter_solution` is {py:obj}`False`.
```

## Dry-run option

Specifying {py:obj}`True` for the `dry_run` keyword argument to the {py:func}`~amplify.solve` function, you can perform the processes before sending the model to the solver. Many solver clients allow you to run the {py:func}`~amplify.solve` function with `dry_run` without specifying an API token.

This option lets you see three things before connecting to the solver. First, whether the model you want to solve is available for input to the solver. Second, what model transformations and graph embeddings the Amplify SDK performs. Third, what kind of query data the Amplify SDK sends.

```{testcode}
from amplify import VariableGenerator, equal_to, Model, AmplifyAEClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)

client = AmplifyAEClient()

result = solve(model, client, dry_run = True)
```

When you run the solve() with the `dry_run` option, the {py:class}`~amplify.Result` object returned by the {py:func}`~amplify.solve` function does not contain a solution.

```{doctest}
>>> len(result)
0
```

```{note}
The `dry_run` option does not change the {py:attr}`~amplify.Result.intermediate` and {py:attr}`~amplify.Result.embedding` properties of {py:class}`~amplify.Result`. They are the same as when you run solve() without the `dry_run` option. This is useful if you want to know how the Amplify SDK performs model transformations and graph embeddings. See "[](conversion.md)" for more information about each property.
```

```{note}
When running with the `dry_run` option, the Amplify SDK does not send the request to the solver. If you set {py:attr}`~amplify.AmplifyAEClient.write_request_data` of the solver client, the request data is written to a file. For more information about {py:attr}`~amplify.AmplifyAEClient.write_request_data`, see "[](#client-write-data)".
```