Can Tuning Knitro Solver Considerably Make A Difference?

Question

I have an NLP that I am hoping to solve with Knitro and I am aware of a multitude of different settings that you can "tune" in order to improve solution performance. I am not familiar with optimization solvers and the various settings, and so what I am trying to determine is exactly how much of a difference tuning the settings can make in solving problems. Does tuning the solver have the potential to drastically improve the solving times, and if so, could you provide a small conceptual example that illustrates how different solver settings might be able to improve the computational efficiency of a problem?

I am trying to determine if investing time into learning the fundamentals of the solver (and thus the tuning specs) is really worth my time as a student if my problem is very difficult to solve.

Answer 1

(Disclaimer: I am a developer of Knitro)

When developing a NLP solver, we set the default values for the different options so as to minimize the resolution time in average for different class of problems (CUTer, QPLIB, Mittelmann instances, etc.). When working on a specific problem, it often pays to find appropriate parameters to improve the resolution time. In Knitro, the most impactful parameters are usually:

• algorithm: Knitro comes with 4 different algorithms to solve NLP problems.
  • algorithm=1 uses the classical interior point algorithm, and Knitro computes at each iteration a line-search step using direct linear algebra (you could specify the line-search procedure with linesearch). If the line-search fails to improve the merit function used inside Knitro, the algorithm falls back to a trust-region step (the CG step appearing in the log of Knitro).
  • algorithm=2 uses a trust-region algorithm, using a quadratic approximation of the non-linear function internally. This algorithm could be powerful if you have callbacks available to compute the Hessian vector product $\nabla^2f(x^k) v$, as you won't need to compute the whole Hessian in this case.
  • algorithm=3 uses an active-set algorithm (more precisely, a sequential linear-quadratic programming algorithm).
  • algorithm=4 uses a classical SQP algorithm, which could be powerful if evaluating the oracle for the function, the gradient and the Hessian is costly. Indeed, the SQP algorithm usually performs a smaller number of iterations than the other algorithms.
• linsolver: determine which linear solvers to use when solving the Newton step at each iteration. On large-scale problems, setting an appropriate linear solver could improve a lot the performance. MA27 and MA57 give good performance overall, and MA86/MA97 target more specific architecture. You may also want to use Intel PARDISO here.
• hessopt: specify which algorithm to use internally. If you provide the Hessian, hessopt=1 performs the classical Newton algorithm. If you have only gradients available, I recommend using hessopt=2 (BFGS) if the problem is medium-sized, and hessopt=6 (L-BFGS) if the problem has more than 10,000 variables or constraints. When using L-BFGS, you can play with the parameter lm_size to determine how many coefficients to use in the limited memory approximation of the Hessian.
• presolve: determine the level of the presolve. Basically, the presolve removes redundancies in the linear constraints (fixed variables, linearly dependant rows, etc). You can specify the level of the presolve with presolve_level.
• Concerning the specific parameters for the barrier used inside the interior point algorithm, they are often more difficult to tune. I recommend setting bar_conic_enable=1 if you are using the conic API of Knitro. bar_murule allows to change the update rule of the penalty parameter \mu, bar_penaltycons is useful if your problem has difficult or degenerate constraints, bar_watchdog enables a watchdog procedure in the line-search, and bar_penaltyrule allows more control to define the merit function uses internally in Knitro.

In any case, before tuning the performance of the solver, I recommend to spend some time on formulating the NLP problem properly, e.g.:

• Choosing an appropriate scaling (the closer the objective and the range of the constraint to 1.0, the better) ;
• Avoiding redundant and linearly dependent constraints ;
• Specifying most of the constraints by using the linear and quadratic API of Knitro (by doing so, we let Knitro computes automatically the Jacobian and the Hessian, and that could lead to much better performance).

In any case, I recommend having a look at:

• https://www.artelys.com/docs/knitro//2_userGuide/algorithms.html
• https://www.artelys.com/docs/knitro//3_referenceManual/userOptions.html

and we would be happy to help you more specifically if you choose to contact the support team on support-knitro [AT] artelys.com!

I am trying to determine if investing time into learning the fundamentals of the solver (and thus the tuning specs) is really worth my time as a student if my problem is very difficult to solve.

If you are interested by the theory lying behind the optimization solver Knitro, I advise usually to have a look at this article: http://users.iems.northwestern.edu/~nocedal/PDFfiles/integrated.pdf

Furthermore, Numerical Optimization by Nocedal and Wright is a must read.

Answer 2

Tuning a solver can make a big difference when it comes to IP/MIP problems. For continuous problems, it's unlikely to see a significant difference in performance.

If the solver enters branch and bound and/or has to use MIP heuristics to find primal solutions/feasible points, then there's no reason that the default settings would work better than something different.

That being said, it's rare to find a better configuration than what a solver's developers suggest.

In general, we tune our solvers over large diverse sets of difficult problems (our own set is 3,000+) and pick combinations of features that (i) work best on average, and (ii) are well balanced, i.e., don't give an amazing performance for some problems but horrendous in others.

We even have hard coded overrides to prevent users from using combinations of options that are known to perform badly for certain types of problems.

There's usually 1% of cases not covered by the defaults, which is the only reason we make algorithmic options available to our users.

If one finds themselves in that 1% of cases, I would suggest experimenting with one option at a time, and to pick the important ones first, e.g. branching rules, type/frequency of heuristics, etc. I strongly advise against tweaking numbers/parameters, maybe with the exception of feasibility tolerances.