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 [14].

The MISQP algorithm in Knitro is Artelys’ own implementation of the MISQP algorithm described in [7] 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 [8]. Zero-half cuts are generated using heuristics from Andreello et al., 2007 [9].

We also recommend the following papers: Byrd et al., 2003 [10], Fourer et al., 2003 [11], Hock and Schittkowski, 1981 [12], and Nocedal and Wright, 1999 [13].

To solve linear systems arising at every iteration of the algorithm, Knitro may utilize routines MA27 or MA57 [15], 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]

O. Exler, and K. Schittkowski, “A trust-region SQP algorithm for mixed-integer nonlinear programming”, Optimization Letters, Vol. 1:269–280, 2007.

[8]

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.

[9]

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.

[10]

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.

[11]

R. Fourer, D. M. Gay, and B. W. Kernighan, “AMPL: A Modeling Language for Mathematical Programming”, 2nd Ed., Brooks/Cole – Thomson Learning, 2003.

[12]

Hock, W. and Schittkowski, K. “Test Examples for Nonlinear Programming Codes”, volume 187 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 1981.

[13]

J. Nocedal and S. J. Wright, “Numerical Optimization”, Springer Series in Operations Research, Springer, 1999.

[14]

C.-J. Lin and J. J. Moré, “Incomplete Cholesky factorizations with limited memory”, SIAM J. Sci. Comput., 21(1):24–45, 1999.

[15]

Harwell Subroutine Library, “A catalogue of subroutines (HSL 2002)”, AEA Technology, Harwell, Oxfordshire, England, 2002.