Introduction to the latest version¶
This page gives the main improvements and the new functions of the latest version of Amplify AE (the v1.0 series). The latest version gives a large gain of performance over the earlier Amplify AE (the v0.9 series) in the following points.
A new GPU optimization algorithm
Support for a high-order polynomial (up to the 4th degree)
Better support for constraints (an inequality constraint, and the automatic adjustment of the constraint weight)
Both versions are available at this moment, but we recommend that you move to the latest version.
How to move to the latest version¶
If you use the Amplify SDK, you move from the earlier Amplify AE to the latest version with a replacement of the client class only. You set the parameters in almost the same way, but some of them have a new name.
The example below shows the replacement.
from amplify import FixstarsClient
client = FixstarsClient()
# Set the API token
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
# Set the execution time to 1 second
client.parameters.timeout = 1000
from amplify import AmplifyAEClient
from datetime import timedelta
client = AmplifyAEClient()
# Set the API token
client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
# Set the execution time to 1 second (note: the parameter has a new name)
client.parameters.time_limit_ms = timedelta(milliseconds=1000)
See the client page for the details of AmplifyAEClient.
The reason for the update¶
The earlier Amplify AE was a GPU-based Ising machine for a large problem, but it had the difficulties of a QUBO solver.
An inequality constraint needed an auxiliary variable.
The weight of a constraint penalty needed manual tuning.
A polynomial of the 3rd degree or higher needed a reduction of the degree.
These difficulties made the accuracy and the speed of the solution lower.
The latest Amplify AE has a new algorithm that removes these difficulties. It takes a polynomial up to the 4th degree directly, and it needs no weight for a constraint. This gives a performance that the earlier version and the solvers of other companies do not reach.
The performance in the benchmarks¶
We measured the latest Amplify AE with the standard benchmark problems and with the real problems that we solved in the past. The results of the solvers of two other companies (company A and company B) are there for the comparison.
The horizontal axis of each graph is the execution time, and the vertical axis is the value of the objective function. A plot at the lower left means that the solver gives a better solution faster.
The quadratic knapsack problem¶
The latest Amplify AE recorded a very good performance on the quadratic knapsack problem. We used jeu_300_50_1 from the benchmark problem set. This problem selects 50 items out of 300 items.
Solver |
Time to the optimal solution |
|---|---|
Amplify AE |
0.233 s 🏆 |
The solver of company A |
4.08 s |
The solver of company B |
50.0 s |
Amplify AE reached the optimal solution 18 times faster than the solver of company A, and 217 times faster than the solver of company B.
A staff shift optimization problem of a real company¶
Amplify AE also showed its performance on a complex staff shift problem with many constraints: 365 equality constraints and 720 inequality constraints.
Solver |
Objective value of the best solution (60 seconds) |
|---|---|
Amplify AE |
23.7 🏆 |
The solver of company A |
24.5 |
The solver of company B |
(no feasible solution) |
Amplify AE reached the optimal solution 6 times faster than the solver of company A. The solver of company B did not handle the combination of the complex constraints, and it found no feasible solution.
Better support for constraints¶
The graph below compares the results on a production planning problem. The problem comes from a real task, and it has many types of constraints together.
The latest version finds a feasible solution more than 100 times faster than the earlier version, and it reaches a solution of a better quality. Amplify AE gives a large gain of performance on a problem that has the complex constraints of a real operation.
The automatic adjustment of the constraint weight¶
The latest version makes this performance much easier to use. The weight of a constraint was the point where many users stopped in the past. The latest version removes that difficulty.
The move is simple. You replace the FixstarsClient class with the AmplifyAEClient class, and you no longer adjust a constraint weight.
For example, the traveling salesperson problem (TSP) needs a constraint weight on a usual QUBO solver. Amplify AE solves it with the maximum performance and with no weight, as follows.
model = Model(
route_length,
(one_hot(q, axis=1) + one_hot(q, axis=0)) * distance.max(),
)
model = Model(
route_length,
(one_hot(q, axis=1) + one_hot(q, axis=0)),
)
The adjustment of a constraint weight is one of the difficulties of a QUBO solver. A good weight is hard to find when the problem has many constraints. The latest Amplify AE adjusts the weight between the constraints and the weight between the objective function and the constraints. This removes the work at the time of the formulation, and it always gives the maximum performance. It also gives a better accuracy than the manual tuning, because the weight is the optimal one.
An inequality constraint needs no auxiliary variable¶
An inequality constraint is one more thing that makes an optimization complex. The new algorithm of the latest Amplify AE gives a much better performance on a problem with an inequality constraint. You change no formulation for this: you change the client class to AmplifyAEClient, and it works.
An inequality constraint is also a difficulty of a QUBO solver. Such a constraint needs a new auxiliary variable, so the problem becomes larger and harder to solve. In the past you sometimes had to select a penalty function at the time of the formulation. This function is not exact, but it makes the problem easier (the relaxation method).
The latest Amplify AE makes the penalty function inside the solver. It thus keeps the exact form of the inequality, and it does not make the problem larger. This removes the trial and error of the user, and it lets you give your attention to the problem itself.
Support for a high-order polynomial¶
A QUBO solver, and the earlier Amplify AE with it, expects a quadratic form for the objective function and for the constraints. But a real task often has complex interactions between the variables, and it needs a polynomial of the 3rd degree or higher.
Examples of a high-order polynomial in a real task:
Logistics: the minimum and the balance of the transport cost, and the complex constraints of a network
Production planning: an optimization with complex non-linear constraints over more than one machine and more than one process
Communication network: the complex interactions between many variables in the allocation of a band and of a resource
Such a high-order problem needs a reduction of the degree of the objective function and of the constraints. The reduction goes down to the degree that the solver takes. The reduction needs many auxiliary variables and many constraints, so the problem becomes complex. A good solution becomes hard to get in a practical time.
The latest Amplify AE takes an objective function and a constraint up to the 4th degree directly. A problem up to the 4th degree therefore needs no reduction of the degree.
The support for a high-order polynomial gives:
A large gain of performance: with no reduction of the degree, Amplify AE gives a strong performance on a high-order problem. An earlier solver solved that problem with difficulty, or with a solution of a lower quality.
A faithful expression of the problem: you formulate a problem with complex interactions in a more natural form, and the problem does not become larger than necessary.
We also give a QUBO solver mode, which behaves like an ideal quantum annealing machine. Academic research asks for that mode. Amplify AE is thus a solver of a high performance for a real task and for research.
The comparison with the earlier version¶
We compared the latest version with the earlier Amplify AE on two problems with an objective function of the 4th degree: LABS (Low Autocorrelation Binary Sequence) and BVRP (Balanced Vehicle Routing Problem).
LABS: this problem finds a sequence of an electric signal with the least noise, that is, with a low autocorrelation.
BVRP: this problem minimizes the total route length of more than one vehicle. It also minimizes the variance of each route to balance the load of each vehicle.
The graphs below compare the results on each problem. The horizontal axis is the execution time, and the vertical axis is the value of the objective function. A plot at the lower left means that the solver gives a better solution faster.
LABS: the latest version finds a feasible solution faster than the earlier version, and it reaches a solution of a better quality.
BVRP: the earlier version found no feasible solution, because the reduction of the degree made too many auxiliary variables. The latest version finds a feasible solution quickly, and it continues to improve the quality of the solution.
These results show that the latest Amplify AE gives a large gain of performance over the earlier version on a high-order (4th degree) problem.
See also
This paper of the Tanaka Laboratory of Keio University uses the latest Amplify AE. It shows that a method that takes a high-order expression directly is better than the usual reduction of the degree. It is better in the simplicity of the structure, in the stability of the computation, and in the quality of the solution. Read it if you want the technical details.
The multi-GPU option¶
The standard plan gives one GPU, and an additional option gives more than one GPU. You use more than one GPU in the two ways below.
The parallel execution of more than one job¶
If you have more than one optimization problem, you solve them efficiently with a job on each GPU. If you use the Amplify SDK, you replace the solve function with the parallel_solve function. It solves the problems in parallel on the GPUs of your contract.
The solution with more than one GPU¶
Amplify AE has an algorithm in which the GPUs anneal together. This gives a good solution faster and with a better accuracy. If you use the Amplify SDK, you set the number of the GPUs as a parameter of the client.
The performance with more than one GPU¶
We compared the annealing speed (the number of the searches per unit of time) of each plan on the maximum cut problem.
The graph below groups the plans by GPU type: the basic and standard plan, the premium plan, and the S premium plan. It gives the ratio of the annealing speed on three problem sizes. S premium (2 GPUs) and S premium (4 GPUs) give the performance with more than one GPU.
A higher plan with a better GPU gives a higher annealing speed. More than one GPU gives an even faster search. The difference between the plans, and the effect of the multi-GPU option, become larger as the problem becomes larger.
The plan for the future¶
We continue to improve the algorithm and to add new functions, so that Amplify AE takes more types of optimization problem. We also want your feedback, because it makes Amplify AE more valuable as a practical optimization solution.
Amplify AE will support the GPUs of the latest NVIDIA Blackwell architecture soon.