Compact Extended Formulations for Low-Rank Functions with Indicator Variables
研究了一类带非凸指示约束的凸函数的混合整数上境图，提出了一种新的析取表示，得到规模在变量数上多项式、在非线性函数维度上指数的紧凑公式，并展示了如何投影出额外变量，计算实验表明能显著提升求解器性能。
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. Funding: This work was supported by the National Science Foundation Division of Computing and Communication Foundations [Grant 2006762].