Compact Extended Formulations for Low-Rank Functions with Indicator Variables

Shaoning Han () and Andrés Gómez ()
Additional contact information
Shaoning Han: Department of Mathematics, National University of Singapore, Singapore 119076
Andrés Gómez: Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089

Mathematics of Operations Research, 2025, vol. 50, issue 3, 1992-2016

Abstract: We study the mixed-integer epigraph of a special class of convex functions with nonconvex indicator constraints, which are often used to impose logical constraints on the support of the solutions. The class of functions we consider are defined as compositions of low-dimensional nonlinear functions with affine functions. 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 dimension of the nonlinear function but polynomial in the number of variables. Moreover, we show how to project out the additional variables for the case of dimension one, recovering or generalizing known results for the convex hulls of such sets (in the original space of variables). Our computational results indicate that the proposed approach can significantly improve the performance of solvers in structured problems.

Keywords: 90C11; mixed-integer nonlinear optimization; convexification; disjunctive programming; indicator variables (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.0281 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:3:p:1992-2016

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().