Intersection Disjunctions for Reverse Convex Sets

• 成果类型: Article
• 署名作者: Towle, Eli; Luedtke, James
• 署名单位: University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1132
• 发表日期: 2022
• 页码: 297-319
• 关键词: solving linear-programs; cuts; optimization; algorithm; economies; generate

摘要

We present a framework to obtain valid inequalities for a reverse convex set: the set of points in a polyhedron that lie outside a given open convex set. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. An intersection cut is a well-known valid inequality for a reverse convex set that is generated from a basic solution that lies within the convex set. We introduce a framework for deriving valid inequalities for the reverse convex set from basic solutions that lie outside the convex set. We first propose an extension to intersection cuts that defines a two-term disjunction for a reverse convex set, which we refer to as an intersection disjunction. Next, we generalize this analysis to a multiterm disjunction by considering the convex set's recession directions. These disjunctions can be used in a cut-generating linear program to obtain valid inequalities for the reverse convex set.