LINGO exploits the convex nature of linear models to find globally optimal solutions. However, we aren’t as fortunate with nonlinear models. With NLP models, LINGO’s default NLP solver uses a local search procedure. This can lead to LINGO stopping at locally optimal points, perhaps missing a global point lying elsewhere. You may refer to On Mathematical Modeling for more information on how and why this can happen.

A strategy that has proven successful in overcoming this problem is to restart the NLP solver several times from different initial points. It is not uncommon for a different starting point to lead to a different local solution point.  Thus, if we restart from enough unique points, saving the best local solution as we go, then we stand a much better chance of finding the true global solution.  We refer to this solution strategy as multistart.

The Multistart Solver box on the Global Solver tab:

multis

contains two options, Attempts and Multistart Hurdle.

The Attempts option is used to set the number of times the multistart solver restarts the standard NLP solver in its attempt to find successively better local solutions.  Each new starting point is intelligently generated to maximize the chances of finding a new local point. The default option, Solver Decides, entails restarting 5 times on small NLPs and disabling multistart on larger models. Setting multistart to 1 causes the NLP solver to be invoked only once, effectively disabling multistart. Setting multistart to any value greater than 1 will cause the NLP solver to restart that number of times on all NLPs. In general, we have found that setting the number of multistarts to around 5 tends to be adequate for most models. Highly nonlinear models may require a larger setting.

The Multistart Hurdle option sets a goal for the multistart solver.  If the multistart solver finds a solution as good, or better, than the hurdle value, the solver will interrupt and return that solution.  This is useful on long-running models, where you may be happy with any solution better than, say, 100.

Note:If the Attempts limit for the multistart solver is hit before the HRDLMS value, then the solver will also interrupt.
Note:Keep in mind that multistart will dramatically increase runtimes, particularly if a large number of restarts is selected.  Thus, one should avoid using multistart unnecessarily on convex models that will converge to a global point in a single pass without any additional prodding.

The following example illustrates the usefulness of multistart. Consider the simple, yet highly nonlinear, model:

MODEL:

  MIN = X * @COS( 3.1416 * X);

  @BND( 0, X, 6);

END

The graph of the objective function is as follows:

wavy

The objective function has three local minimal points over the feasible range. These points are summarized in the following table:

Point

X

Objective

1

1.09

-1.05

2

3.03

-3.02

3

5.02

-5.01

Clearly, the third local point is also the globally best point, and we would like the NLP solver to converge to this point. Below is the solution you will get from LINGO if the multistart option is disabled:

  Local optimal solution found at step:             11

  Objective value:                           -1.046719

          Variable           Value        Reduced Cost

                 X        1.090405           0.1181082E-07

               Row    Slack or Surplus      Dual Price

                 1       -1.046719           -1.000000

Unfortunately, as you can see, we converged to the least preferable of the local minimums. However, after setting the number of multistarts to five and re-solving, we do obtain the global solution:

  Local optimal solution found at step:             39

  Objective value:                           -5.010083

          Variable           Value        Reduced Cost

                 X        5.020143          -0.7076917E-08

               Row    Slack or Surplus      Dual Price

                 1       -5.010083           -1.000000

Note:Unlike the global solver, the multistart solver can only claim its solution to be locally optimal.  This is because there may always be a better solution out there that the multistart solver may, or may not, be able to find with additional runs.  The global solver, on the other hand, can claim global optimality by having partitioned the original model into a series of smaller, convex models.
Note:The multistart solver can run on multiple cores to improve performance.  So, if your machine has multiple cores, be sure to set the thread limit to something higher than 1, with the ideal setting being N, where N is the number of available cores on your machine.   Refer to the Threads parameter on the General Solver tab, discussed above, for more information on setting the thread limit.