Automating a manual process: the new AIMMS Scaling tool
We recently released a new Auto-scaling feature as part of the Math Program Inspector with AIMMS 4.74. This feature can improve the quality of your model with much less manual testing and guesswork when it comes to scaling factor determination.
Hear from
How can users identify scaling issues?
Users are usually not aware about scaling issues in their model. Modelers raise their awareness when they suddenly encounter an issue with the post-solve, for example.
Usual symptoms of a poorly scaled model are:
-
AIMMS post-solve warnings “solution not reliable”, or “could not find a solution"
-
A small infeasibility due to rounding errors in the constraint
-
Instability of the solution, that it would return slightly different solutions
In one example, a model was running multiple solves, and each solve would depend on the one before. There was a very small variation in the input data, possibly due to the computer's own digit precision, which resulted in small changes in the first solution, around the 14th or 15th digit. In the end these small changes resulted in a completely different solution after the final solve. This makes the model “numerically unstable".
A poorly scaled model is a model in which right-hand-side values, model coefficients and variable bounds show order of magnitude of differences.
These differences, even if they do represent some real data and are mathematically correct, affect the numerical computation of the solution.
How did we normally resolve these issues before?
This is often the investigation and work AIMMS User Support provides to our users, in order to improve the model computation. For example, we introduce some new units in the AIMMS model.
We might ask, for example, should I input my weight data in kilograms, grams, or tons? Would it help the model computation if I would input it as “hundreds of tons”?
Several client projects we investigated had poor scaling, and we essentially had to do this work by hand. But it’s a lot of trial and error and can take quite some time without much value at the end.
And this led us to consider an automated scaling tool.
How did you approach this problem?
In theory, one could find optimal factors that would conserve the final solution, and in the meantime improve the numerical properties of the model.
But this Scaling Problem, as we will refer to it, is very large. It could take more time to solve it than to solve the actual model without scaling! How can we simplify this problem, and make resolution of the scaling problem significantly beneficial to the accuracy and the solving time? That is the compromise we were looking for, and the challenge we faced.
Solvers already provide a scaling algorithm. This algorithm is a heuristic, since it is usually too expensive to solve the scaling problem “optimally”. However, AIMMS can greatly benefit from the symbolic information included in the AIMMS model formulation to solve a simplified version of the scaling problem. For example, V_Transport(loc1,loc2) is a symbolic “link” (information) about each variable in the V_Transport matrix. That would sometimes lead to unprecedented improvements. This information is not available for solvers, or at least they do not extract it.
The Scaling Problem described above is of course the major challenge we faced. How can we simplify this problem, and make resolution of the scaling problem significantly beneficial to the solving time and the solution accuracy? Starting with the idea of using the symbolic information is not enough.
I first thought about a non-convex quadratic model, but finally realized we could reformulate it in a linear MIP model, easier to solve. However, the scaling problem is typically showing a very weak LP relaxation, and it turned out that, how ironically, this scaling problem was also poorly scaled! This in turn could affect dramatically the MIP solve. We finally found a satisfactory way to reformulate the scaling problem in order to avoid this.
What is the intended use of the scaling tool?
The scaling tool tries to scale the variables and constraints in such a way that all coefficients, right-hand-side values, and variable bounds will become as close to 1 (in an absolute sense) as possible.
This provides three benefits:
-
an improved numerical stability
-
a potential better solution
-
a potential solution time improvement
The scaling tool, in its current version, is best used for certain types of models.
Typical candidates would be very large MIPs including continuous variable. Combinatorial models, like the Traveling salesman problem or the VRP (Vehicule Routing Problem) would not be the preferred target of this feature.
Are there any plans for future development on this feature?
The scaling tool is part of the Math Program Inspector. Currently, there is no automated way to apply the scaling factors that were found. For now we suppose that developers can take the results and choose how to apply them to the model. In one of the future releases, AIMMS will automatically call the scaling tool as part of the solve statement (if some option is set), and then AIMMS will send the scaled model to the solver. The user then no longer has to worry about scaling factors.
Also, maybe investigating a scaling feature for Nonlinear models.
Find out more about the Scaling tool in our new features. (For more about the Math Program Inspector, see chapter 9 of the AIMMS User’s Guide.)
As always, your feedback is welcome! Leave us a comment.