- NLC algorithm
- Thousands of variables and half millions contraints
- Numerical results on realistic problems
- Primal and dual warm starts
The NCL algorithm, designed by Kenneth Judd, Ding Ma, Michael Saunders, and Dominique Orban as part of Ding Ma’s PhD thesis at Stanford, addresses the difficulty in solving such models. The idea is to approximate the ill-posed problem with a sequence of well-posed subproblems without the degeneracy feature. Early subproblems can be solved loosely. Accuracy is only required as we approach a solution of the original model.
The first version of NCL is implemented entirely in AMPL and calls Artelys Knitro’s barrier algorithm with appropriate options to solve the subproblems tackling tax policy models with thousands of variables and half a million constraints.
NCL’s success on the tax models prompted them to investigate a generalization for any optimization model. The Julia language offers the requisite tools: the Julia interface to Artelys KNITRO and the JuliaSmoothOptimizers (JSO) infrastructure for optimization. In particular, JSO’s generic modeling features gives access to large test sets by way of the Julia interface to the CUTEst collection and to AMPL models.
Thanks to the work of Pierre-Élie Personnaz during his internship at GERAD, numerical results on realistic tax problems were presented at the ICCOPT 2019 conference in Berlin with performance that surpass all previous results. The NCL solver showcases how powerful the combination of Julia, JSO, and Artelys Knitro can be for optimization. Ongoing improvements include primal and dual warm starts, progressive tolerances, and parameter tuning.