Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1287/moor.2021.1132 | MATHEMATICS OF OPERATIONS RESEARCH |
Keywords | DocType | Volume |
mixed-integer nonlinear programming, valid inequalities, reverse convex sets, disjunctive programming, intersection cuts, concavity cuts | Journal | 47 |
Issue | ISSN | Citations |
1 | 0364-765X | 0 |
PageRank | References | Authors |
0.34 | 15 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Eli Towle | 1 | 0 | 0.34 |
James Luedtke | 2 | 439 | 25.95 |