Bibliography
A summary of the algorithms and techniques implemented in the Knitro software product is given in Byrd et al., 2006b [6]. Any publications referencing the Knitro software should cite this paper (along with any other relevant citations mentioned below).
For a detailed description of the algorithm implemented in Interior/CG see Byrd et al., 1999 [1] and for the global convergence theory see Byrd et al., 2000 [2]. The method implemented in Interior/Direct is described in Waltz et al., 2006 [3]. The Active Set algorithm is described in Byrd et al., 2004 [4] and the global convergence theory for this algorithm is in Byrd et al., 2006a [5].
The implementation of the CG preconditioner makes use of the icfs software, which is described in details in Lin and Moré, 1999 [15].
For mixed-integer nonlinear optimization, the hybrid Quesada-Grossman (HQG) method in Knitro is based on the algorithm described in [7]. The MISQP algorithm in Knitro is Artelys’ own implementation of the MISQP algorithm described in [8] but differs in some details.
In order to strengthen MINLP formulations Knitro generates cuts. Especially, Knitro generates lifted cover inequalities which requires solving efficiently a knapsack problem. For solving this problem, we use the Combo algorithm from Martello et al., 1997 [9]. Zero-half cuts are generated using heuristics from Andreello et al., 2007 [10].
We also recommend the following papers: Byrd et al., 2003 [11], Fourer et al., 2003 [12], Hock and Schittkowski, 1981 [13], and Nocedal and Wright, 1999 [14].
To solve linear systems arising at every iteration of the algorithm, Knitro may utilize routines MA27 or MA57 [16], a component package of the Harwell Subroutine Library (HSL). HSL, a collection of Fortran codes for large-scale scientific computation. See http://www.hsl.rl.ac.uk/
In addition, the Active Set algorithm in Knitro may make use of the COIN-OR Clp linear programming solver module. The version used in Knitro may be downloaded from http://www.artelys.com/tools/clp/
Lastly, Knitro may make use of the Intel(R) Math Kernel Library (https://software.intel.com/en-us/intel-mkl) for some linear algebra computations.
[1] | R. H. Byrd, M. E. Hribar, and J. Nocedal, “An interior point algorithm for large scale nonlinear programming”, SIAM Journal on Optimization, 9(4):877–900, 1999. |
[2] | R. H. Byrd, J.-Ch. Gilbert, and J. Nocedal, “A trust region method based on interior point techniques for nonlinear programming”, Mathematical Programming, 89(1):149–185, 2000. |
[3] | R. A. Waltz, J. L. Morales, J. Nocedal, and D. Orban, “An interior algorithm for nonlinear optimization that combines line search and trust region steps”, Mathematical Programming A, 107(3):391–408, 2006. |
[4] | R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, “An algorithm for nonlinear optimization using linear programming and equality constrained subproblems”, Mathematical Programming, Series B, 100(1):27–48, 2004. |
[5] | R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, “On the convergence of successive linear-quadratic programming algorithms”, SIAM Journal on Optimization, 16(2):471–489, 2006. |
[6] | R. H. Byrd, J. Nocedal, and R.A. Waltz, “KNITRO: An integrated package for nonlinear optimization”, In G. di Pillo and M. Roma, editors, Large-Scale Nonlinear Optimization, pages 35–59. Springer, 2006. |
[7] | I. Quesada, and I. E. Grossmann, “An LP/NLP based branch and bound algorithm for convex MINLP optimization problems”, Computers and Chemical Engineering, 16(10-11):937–947, 1992. |
[8] | O. Exler, and K. Schittkowski, “A trust-region SQP algorithm for mixed-integer nonlinear programming”, Optimization Letters, Vol. 1:269–280, 2007. |
[9] | S. Martello, D. Pisinger, and P. Toth, “Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem”, Management Science, 45(3):414-424, 1997. |
[10] | G. Andreello, A. Caprara, and M. Fischetti, “Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study” INFORMS Journal on Computing, 19(2):229–238, 2007. |
[11] | R. H. Byrd, J. Nocedal, and R. A. Waltz, “Feasible interior methods using slacks for nonlinear optimization”, Computational Optimization and Applications, 26(1):35–61, 2003. |
[12] | R. Fourer, D. M. Gay, and B. W. Kernighan, “AMPL: A Modeling Language for Mathematical Programming”, 2nd Ed., Brooks/Cole – Thomson Learning, 2003. |
[13] | Hock, W. and Schittkowski, K. “Test Examples for Nonlinear Programming Codes”, volume 187 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1981. |
[14] | J. Nocedal and S. J. Wright, “Numerical Optimization”, Springer Series in Operations Research, Springer, 1999. |
[15] | C.-J. Lin and J. J. Moré, “Incomplete Cholesky factorizations with limited memory”, SIAM J. Sci. Comput., 21(1):24–45, 1999. |
[16] | Harwell Subroutine Library, “A catalogue of subroutines (HSL 2002)”, AEA Technology, Harwell, Oxfordshire, England, 2002. |