7. Solving a Combinatorial Optimization Problem#

This page explains how to solve a combinatorial optimization problem using the model Model and solver client created in “Model Formulation” and “Solver Client.”

7.1. Solve function#

The Amplify SDK provides the solve() function to perform combinatorial optimization. This function takes 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.

\[\begin{split}\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*}\end{split}\]

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

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.

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 solve() function and run the solver as follows.

result = solve(model, client)

The results obtained can be verified as follows. See “Retrieving the result” for more information.

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

7.1.1. 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 Poly or an object of the class Constraint or ConstraintList directly as the first argument of the solve() function.

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:

result = solve(objective, client)

Solving a combinatorial optimization problem with a single constraint:

result = solve(constraint1, client)

Solving a combinatorial optimization problem with multiple constraints:

result = solve(constraint1 + constraint2, client)

7.2. Retrieving the result#

The Result object returned by the solve() function contains information about the solution returned by the solver and the time taken to run it.

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 Result with the len() function. Only solutions that satisfy all constraints are included in Result by default.

>>> len(result)
1

If Result contains multiple solutions, you can use the best property to find the best solution.

>>> type(result.best)
<class 'amplify.Result.Solution'>

The best solution obtained with the best property is an instance of the Solution class. This class has the following attributes.

`objective`	The value of the objective function
`values`	The value of each variable in the solution
`feasible`	Whether the constraint is satisfied or not
`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.

>>> 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 
datetime.timedelta(microseconds=27965)

By passing values to the evaluate() method of the variable array, you can obtain the solution values corresponding to each variable in the array as an ndarray of the same form as the variable array.

>>> 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 time attribute will have the same value as the solver’s execution_time. See “Execution Time information” for more information.

Result can contain not only the best solution but also multiple solutions. You can obtain each solution as an instance of the Solution class by indexing on Result.

>>> result[0].objective
-1.0
>>> result[0].feasible
True

Iterative access is also possible.

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

7.3. Options for the execution result output#

By default, the Result object returned by the 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 solve() function.

7.3.1. Filtering the solution#

If you set the filter_solution keyword argument to the solve() function to False, solutions that do not satisfy the constraints may be included in Result.

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)

>>> 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 solve() function, you can set the filter_solution property of Result to False so that solutions that do not satisfy the constraint conditions are included in Result.

>>> result = solve(model, client)
>>> len(result)
0
>>> result.filter_solution = False
>>> len(result)
1

7.3.2. Sorting solutions#

The Amplify SDK sorts the solutions included in Result in ascending order by default. If you specify False for the sort_solution keyword argument to the solve() function, the order of the solutions in the result remains the same as that of the solutions returned by the solver.

result = solve(model, client, sort_solution=False)

You can also sort the solutions later using Result’s sort() method.

result.sort()

Note

The Amplify SDK determines the goodness of the solution in the following order.

Whether the constraints are satisfied
Whether the value of the objective function is smaller

Therefore, the solution that the best property of 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 filter_solution is False.

7.4. Dry-run option#

Specifying True for the dry_run keyword argument to the solve() function, you can perform the processes before sending the model to the solver. Many solver clients allow you to run the 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.

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 Result object returned by the solve() function does not contain a solution.

>>> len(result)
0

Note

When you run the solve() with the dry_run option, the intermediate and embedding properties of 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 “Model Conversions” 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 write_request_data of the the solver client. For more information about write_request_data, see “Save sent and received data ☁️ Cloud 💻 Local”.