# 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 and optimizes the model using the solver corresponding to the solver client.

Let's optimize the following example using Amplify AE.

```{math}
\begin{align*}
    \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{align*}
```

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

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

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 such as penalty function calculations, variable conversions, degree reduction, and graph embedding as needed to make the input model client-ready. The {py:func}`~amplify.solve` function allows you to specify several 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, it is possible to pass an object of the class {py:class}`~amplify.Poly` or an object of the class {py:class}`~amplify.Constraint` or {py:class}`~amplify.ConstraintList` directly as the first argument of the {py:func}`~amplify.solve` function.

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

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.

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = 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:class}`~amplify.Result.best` property to find the best solution.

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

The best solution obtained with the {py:class}`~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
```

The values of the objective function, the values of the variables, whether all constraints are satisfied, and the time at which the solution was found can be obtained for the best solution 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)
```

By passing {py:attr}`~amplify.Result.Solution.values` to the {py:meth}`~amplify.PolyArray.evaluate` method of the variable array, you can obtain the solution values corresponding to each variable in the array as 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, FixstarsClient, 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 = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

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

Even after calling 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` so that solutions that do not satisfy the constraint conditions are included 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 order of the solutions in the result remains the same as that of the solutions returned by the solver.

```{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 solution that the {py:class}`~amplify.Result.best` property of {py:class}`~amplify.Result` can obtain is the one with the smallest value of the objective function among the solutions that satisfy the constraints, if any. 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 if the model you want to solve is available for input to the solver, what model transformations and graph embeddings the Amplify SDK performs, and what kind of query data the Amplify SDK sends before connecting to the solver.

```{testcode}
from amplify import VariableGenerator, equal_to, Model, FixstarsClient, 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 = FixstarsClient()

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}
When you run the solve() with the `dry_run` option, the {py:attr}`~amplify.Result.intermediate` and {py:attr}`~amplify.Result.embedding` properties of {py:class}`~amplify.Result` are the same as when run 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, but the request data is written to a file if you set {py:attr}`~amplify.FixstarsClient.write_request_data` of the the solver client. For more information about {py:attr}`~amplify.FixstarsClient.write_request_data`, see "[](#client-write-data)".
```