Optimization Online


Perspective Reformulations of Mixed Integer Nonlinear Programs with Indicator Variables

Oktay Gunluk (oktay***at***watson.ibm.com)
Jeff Linderoth (linderoth***at***wisc.edu)

Abstract: We study mixed integer nonlinear programs (MINLP)s that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is ``turned off'', forces some of the decision variables to assume fixed values, and, when it is ``turned on'', forces them to belong to a convex set. Many practical MINLPs contain integer variables of this type. We first study a mixed integer set defined by a single separable quadratic constraint and a collection of variable upper and lower bound constraints, and a convex hull description of this set is derived. We then extend this result to produce an explicit characterization of the convex hull of the union of a point and a bounded convex set defined by analytic functions. Further, we show that for many classes of problems, the convex hull can be expressed via conic quadratic constraints, and thus relaxations can be solved via second-order cone programming. Our work is closely related with the earlier work of Ceria and Soares (1996) as well as recent work by Frangioni and Gentile (2006) and, Akt\"urk, Atamt\"urk and G\"urel (2007). Finally, we apply our results to develop tight formulations of mixed integer nonlinear programs in which the nonlinear functions are separable and convex and in which indicator variables play an important role. In particular, we present computational results for three applications -- quadratic facility location, network design with congestion, and portfolio optimization with buy-in thresholds -- that show the power of the reformulation technique.

Keywords: Mixed-integer nonlinear programming -- perspective functions

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

Citation: Technical Report: Dept. of ISyE, University of Wisconsin-Madison

Download: [PDF]

Entry Submitted: 06/20/2008
Entry Accepted: 06/20/2008
Entry Last Modified: 09/30/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society