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 am 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

undefinedThorsten Gellermann (gellermann [ a t ] math [ d o t ] uni-erlangen [ d o t ] de)