Optimization Online


Compact extended formulations for low-rank functions with indicator variables

Shaoning Han (shaoning***at***usc.edu)
Andres Gomez (gomezand***at***usc.edu)

Abstract: We study the mixed-integer epigraph of a low-rank convex function with non-convex indicator constraints, which are often used to impose logical constraints on the support of the solutions. Extended formulations describing the convex hull of such sets can easily be constructed via disjunctive programming, although a direct application of this method often yields prohibitively large formulations, whose size is exponential in the number of variables. In this paper, we propose a new disjunctive representation of the sets under study, which leads to compact formulations with size exponential in the rank of the function, but polynomial in the number of variables. Moreover, we show how to project out the additional variables for the case of rank-one functions, recovering or generalizing known results for the convex hulls of such sets (in the original space of variables).

Keywords: Mixed-integer nonlinear optimization, convexification, disjunctive programming, indicator variables

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

Citation: Technical report, USC, October 2021

Download: [PDF]

Entry Submitted: 10/27/2021
Entry Accepted: 10/28/2021
Entry Last Modified: 10/28/2021

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 Optimization Society