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.
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.]
See also
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 clientready. The solve()
function allows you to specify several parameters for this model transformation. See the βModel conversion parametersβ pages for a detailed description of each parameter.
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.
The value of the objective function 

The value of each variable in the solution 

Whether the constraint is satisfied or not 

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
See also
The Result
object also contains model transformation, graph embedding, and runtime information. See βModel Conversionsβ and βExecution Time informationβ for details.
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. Dryrun 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β.