A Trust-Region-SQP Algorithm for the Efficient Solution of Non-Convex, Non-Relaxable Mixed-Integer Nonlinear Programming Problems

Klaus Schittkowski, Oliver Exler, Thomas Lehmann

Mixed-integer optimization problems are often hard to solve, especially if function evaluations are very time-consuming or if integer variables are not relaxable. Based on the success of sequential quadratic programming (SQP) methods for continuous optimization, the idea to take integer variaables into account lead to a straigthforward extension towards a mixed-integer nonlinear programming (MINLP) algorithm based on the SQP idea. The main design goal is to minimize the total number of function evaluations, i.e., executions of the underlying simulation software. The resulting code is called MISQP and and was developed at the Unversity of Bayreuth over a period of 10 years. A mixed-integer quadratic subproblem is solved in each step by a branch-and-bound method exploiting dual information. The algorithm is stabilized by a trust region correction which goes back to Yuan (1995). The Hessian of the Lagrangian function is approximated by BFGS updates subject to the continuous and the integer variables. We outline the mathematical structure of the algorithm and present some numerical results based on a set of 200 academic test examples.The number of function evaluations is about the same as the number of function evaluations needed to solve the relaxed test problems by a standard continuous SQP code (NLPQLP).