A branch-and-refine method for nonconvex mixed integer optimization
Presenter
November 18, 2008
Keywords:
- Nonconvex, optimization
MSC:
- 90C26
Abstract
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.