A branch-and-refine method for nonconvex mixed integer optimization

Tuesday, November 18, 2008 - 2:00pm - 2:45pm
EE/CS 3-180
Annick Sartenaer (Facultés Universitaires Notre Dame de la Paix (Namur))
Joint work with Sven Leyffer (Argonne National Laboratory)
and Emilie Wanufelle (University of Namur).

Motivated by problems related to power systems analysis which give rise
to nonconvex mixed integer nonlinear programming (MINLP) problems,
we propose a global optimization method based on ideas and techniques
that can be easily extended to handle a large class of nonconvex MINLPs.

Our method decomposes the nonlinear functions appearing in the problem
to solve into one- and two-dimensional components for which piecewise
linear envelopes are constructed using ideas similar to special ordered sets.
The resulting relaxations are then successively refined by branching on integer
or continuous variables. We prove convergence to a global optimum within a
desired accuracy under mild assumptions and present some preliminary
numerical experience.
MSC Code: