Mixed-integer bilevel representability
成果类型：
Article
署名作者：
Basu, Amitabh; Ryan, Christopher Thomas; Sankaranarayanan, Sriram
署名单位：
Johns Hopkins University; University of Chicago; Universite de Montreal; Polytechnique Montreal
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-019-01424-w
发表日期：
2021
页码：
163-197
关键词：
摘要：
We study the representability of sets by extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these three paradigms. We then prove that the feasible region of bilevel problems with integer variables exclusively in the upper level is a finite union of sets representable by mixed-integer programs and vice versa. Further, we prove that, up to topological closures, we do not get additional modeling power by allowing integer variables in the lower level as well. To establish the last statement, we prove that the family of sets that are finite unions of mixed-integer representable sets (up to topological closures) forms an algebra of sets; i.e., this family is closed under finite unions, intersections and complementation.