FICO Xpress Global (beta): A global solver for a nonlinear world

Community Manager

3 years ago

The golden rule of computing: “Garbage in, garbage out” also applies to optimization modeling. The results that you get from your optimization process can only be as accurate as

The input data (that usually ends up in some coefficients of the model) and
The model itself.

On the second aspect, a major source of imprecision comes in when one attempts to linearize elements of an optimization problem that are inherently nonlinear.

If you need to model the chemical reactions of substances or the physical processes when dealing with liquids or gases, you will often get polynomial terms involved. If your engineering involves electromagnetic components, chances are that trigonometric functions will appear in your models. And if you want to represent growth processes accurately, exponential terms are not far away. Arguably, the world is nonlinear.

Figure 1: The world is nonlinear. Coarse linearization can easily lead to significant precision loss.

But who says you must linearize those nonlinearities? So far, modelers often saw themselves confronted with choosing between the lesser evil:

If they wanted to work with nonlinearities natively, they had to compromise with the optimality guarantees: Most nonlinear solvers, e.g., FICO Xpress Nonlinear, only guarantee local optimality. That means the provided solution is the best in a local neighborhood, but there is no guarantee that it will also be the overall – globally – best.
If they wanted a guarantee for global optimality, they had to work with (mixed-integer) linear optimization solvers, like the FICO Xpress Optimizer.

Implementing a global solver for mixed-integer nonlinear optimization is a challenging, yet not impossible endeavor. As of 2022, we succeeded in this quest: FICO Xpress's unique portfolio of solver technologies welcomes its newest member: FICO Xpress Global. To the best of our knowledge, this makes FICO Xpress the first commercial solver to have leveraged its own MIP technology to implement a fully-fledged global optimization solver for general nonlinear (including non-convex) problems.

This means that from now on, you can use products, rational functions (i.e., divisions), trigonometric functions (sine and friends), exponential functions, logarithms, roots, power functions, absolute values, piecewise-linear functions, error functions and all combinations of those as constraints and objective function that you feed into FICO Xpress.

Figure 2: All the nonlinearities FICO Xpress Global can handle. For existing FICO Xpress Nonlinear users: The global solver can handle the same nonlinearities and the modeling API stays the same.

But is it really that simple? Arguably, nonlinear optimization is theoretically and practically much harder than linear optimization. For the Math ~~nerds~~ experts: While continuous linear optimization is solvable in polynomial time, continuous nonlinear optimization is undecidable; while optimizing a linear objective without constraints (only variable bounds) is trivial, optimizing a quadratic function without constraints is NP-hard. Consequently, the boundary of when an optimization problem gets too complex to be solved efficiently is hit much earlier in the nonlinear case than in the linear case (and hence the popularity of local solvers). There are, however, a few cases when using a global solver is promising:

When you have an optimization problem with a big linear core, meaning that the majority of constraints is linear and only some variables are involved in the few nonlinear constraints. Linear problems that are amended by only a small number of nonlinearities are a prevalent case in practice, see Figure 3 for an example.
When you have tight bounds on your decision variables and the nonlinearities in your problem are “well-behaved,” e.g., they do not show singularities within the domain, and the involved terms (including intermediate results) do not grow arbitrarily large. As an example, take sinx, x∈[0,2π]. The input is bounded to cover a single period of the sine function. The function values and the first and second derivatives are bounded by [-1,1], and the function graph can be easily subdivided into two convex and two concave regions. Take as a closely related counterexample the function sine^xy; x,y∈[0,2π]. Even though the input variables are tightly bounded again and the function value is bounded by [-1,1], this is a badly conditioned problem. The term inside the sine can grow very large very quickly: e^4π² is an 18-digit number, close to typical solver thresholds for infinity and way beyond what can be accurately represented in floating point arithmetic*. There are almost a quintillion convex and concave regions, and derivatives can grow close to (numeric) infinity. All of this will challenge the solver to get anything meaningful when x and y approach their upper bounds.
* = While e^4π² ≈ 139720110310117791.465814, the approximate value that a computer (in double-precision) will use is 139720110310117152.000000, hence off by about 639 or more than ten times 2π. Evaluating the sine function with such an error margin in the input is meaningless.
When a local solver has trouble finding reasonable solutions: In such a case, you might understand a global solver, even if it does not finish, as a rigorous enumeration of the search space, and the global solver will feed the local solver internally with a systematic sequence of promising starting points which will eventually lead to high-quality solutions, see Figure 4.
There is no way around a global solver whenever you require an optimality guarantee or a proven bound on the optimal values.

Figure 3: A problem with a linear core: Fixing a single (out of three) variables renders the problem linear. Further, the nonlinearity is very “well-behaved”.

Figure 4: A simple continuous, nonconvex optimization problem: Find the largest square with all vertices on the blue line. A local solver (left) finds a feasible, yet suboptimal solution. FICO Xpress Global (right) promptly finds a globally optimal solution (and proves optimality).

If you are curious and want to participate in the beta program, please write an e-mail to [email protected] . If you already were a user of FICO Xpress Nonlinear and would like to upgrade to FICO Xpress Global, you can still use all your existing models and code. The only difference will be that you need to set the GLOBALSOLVE control. Everyone else can find more information on FICO Xpress Global in our online documentation.

We are looking forward to your feedback!

The technical details of how to turn one of the world’s leading MIP solvers into a fully-fledged MINLP solver will have to wait for another day. Follow the Xpress Optimization Community to get notified when our blog on all the cool algorithms behind our global solver will get explained – to drop some names: Outer Approximation cuts, DAG propagation, spatial branching.

The “fine print”:
Given that our global solver is currently in a beta program, there are some limitations:

Cutting or branching in callbacks is not yet supported
Some API functions like XPRSfixmipentities() or XPRSrepairinfeas() will not work yet
Interrupted solves can currently not be resumed
No support for user functions