Videos

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.