Title: Inner approximations in mixed-integer nonlinear optimization

We present two streams of work for generating good feasible solutions to mixed integer nonlinear programs. In the first part of the talk, we consider nonlinear integer programs and provide an approximation method that uses monomial orders on the integer lattice with different permutations of the variable order. An approximation factor is obtained, and it depends in some sense on the sparsity of the objective function. We also show that our method is exact (i.e., obtains the optimal solution) for binary problems. Although the method is not polynomial-time in general, we give some tractable approximations and implementable algorithms that are competitive in providing good solutions on benchmark test instances for linear and quadratic integer problems. This is joint work with my PhD student Yiran Zhu.

A second idea is to do variable discretizations and reformulate the resulting problem into a mixed-integer linear program. I will talk about the many ways of doing this on mixed-integer quadratically constrained programs and how the discretizations can be adaptively refined in an iterative algorithm to improve the quality of solutions. Numerical tests on a wide range of test instances gives very good performance in comparison to global solvers. This is joint work with Arie Koster and Sascha Kuhnke at RWTH Aachen.