# 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)  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)".