Perspective Reformulation and Applications

Oktay Gunluk (gunlukus.ibm.com)
Jeff Linderoth (linderotcae.wisc.edu)

Abstract: In this paper we survey recent work on the perspective reformulation approach that generates tight, tractable relaxations for convex mixed integer nonlinear programs (MINLP)s. This preprocessing technique is applicable to cases where the MINLP contains binary indicator variables that force continuous decision variables to take the value 0, or to belong to a convex set. We derive from first principles the perspective reformulation, and we discuss a variety of practical MINLPs whose relaxation can be strengthened via the perspective reformulation. The survey concludes with comments and computations comparing various algorithmic techniques for solving perspective reformulations.

Keywords: Mixed-integer nonlinear programming, perspective functions

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation:

Download: [PDF]

Entry Submitted: 09/09/2009
Entry Accepted: 09/10/2009
Entry Last Modified: 09/30/2009

Modify/Update this entry