Solver for Relaxations in General Mixed Integer Nonlinear Programming (SCIP/NL)

Mixed Integer Nonlinear Programming (MINLP) generalizes classical Mixed
Integer Programming (MIP) by allowing nonlinearities in the objective
function and constraints. The aim of the project is to integrate a
solver for Nonlinear Relaxations into SCIP.
Like the linear programs for MILP’s, nonlinear relaxations are appear in
heuristics and branch and bound algortihms with several characteristics.
Restrictions are usually simple nonliner symbolic equations and therefor
evaluation is rather cheap. The symbolic form also makes it easy to
evaluate not only local but also global information like minimum and
maximum values and derivatives. Also, under several circumstances it is
possible to check, if restrictions are convex, concave or linear. In
case of use in a branch and bound algorithm, it can be assumed that all
restrictions are convex due the fact that non-convex restrictions are
handled in the MINLP-Framework. Since nonlinear programs from iteration
to iteration changes only slightly, information from previous steps can
be reused like active sets and penalty informations. On the other hand
there are several additional caveats for nonlinear relaxations in MINLP.
First of all, it should easy to cope with infeasibilty especially in the
convex case. Also cutoff values for convex relaxations can reduce the
solution time of the overall problem. Therefor, upper bounds during
should be avaliable during solving the relaxation. Last but not least,
it would be pleasent, if solutions can be found on corners. This is, to
apply classical methods for gomory cuts to a nonlinear programs. After
ZIB has build in a an Interface into SCIP, to cope with MINLP’s. In this
project we develop a penalty based active set EQP/SQP method for solving
the appearing nonlinear relaxations. We choose penalty functions over
filters, because it seems penalty functions can be adjusted rather sharp
from global and historical information, if relevant informations are
available during the solution process. Due to the active set strategy,
also the solution quality for cuttin plane algorithms is given. If
restrictions are activated carfully also upper bounds to a convex
problem can be given. Next to the solver, a small Framework for
analyzing nonlinear expressions is developed to extract the neccessary
additional information for the solver.

Contact

Thorsten Gellermann (gellermann[at]math.uni-erlangen.de)