ICCOPT 2013 Talk, Room 1.6, Monday, July 29, 16:30-18:00

 Speaker: Ruth Hübner, University of Göttingen, Germany
 Title: The rounding property for nonlinear mixed integer optimization problems
 Co-authors: Anita Schöbel

 Abstract:
Scientific Program

Nonlinear mixed integer optimization problems combine the difficulties of nonlinear and (mixed) integer optimization. If the values for its integer variables are already known, the MINLP reduces to a continuous optimization problem for which we assume that it is easier to solve than the original MINLP. We identify special cases where the optimal values for the integer variables can be determined by rounding (up or down) a solution of the continuous relaxation. This property is called the ``rounding property". (Compare also the rounding property for INLP introduced by Hübner and Schöbel, 2012.) Having this rounding property we could solve the original $n+m$-dimensional MINLP ($n$ integer variables, $m$ continuous) by solving up to $2^n$ $m$-dimensional continuous problems. In case the continuous relaxation can be solved in polynomial time this gives us a polynomial approach in fixed dimension. In order to use an improved solution procedure, we also investigate cases where the optimal value for the integer variables can be found by rounding the values of an optimal solution for the continuous relaxation to their closest integers - what we call the ``strong rounding property". To identify (in both cases) these special problems we analyse the geometric properties of the intersection of the level sets of the objective function with the feasible region. In doing so we are also interested which properties the MINLP inherits from the corresponding INLP where all variables have to be integer.


 Talk in: Organized Session Mon.C.16 Integer and mixed-integer nonlinear optimization
 Cluster: Global optimization and mixed-integer programming


 Go to: Mon.C
 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage