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.