Optimization Online


Intersection disjunctions for reverse convex sets

Eli Towle (etowle***at***wisc.edu)
James Luedtke (jim.luedtke***at***wisc.edu)

Abstract: We present a framework to obtain valid inequalities for optimization problems constrained by a reverse convex set, which is defined as the set of points in a polyhedron that lie outside a given open convex set. We are particularly interested in cases where the closure of the convex set is either non-polyhedral, or is defined by too many inequalities to directly apply disjunctive programming. Reverse convex sets arise in many models, including bilevel optimization and polynomial optimization. Intersection cuts are a well-known method for generating valid inequalities for a reverse convex set. Intersection cuts are generated from a basic solution that lies within the convex set. Our contribution is a framework for deriving valid inequalities for the reverse convex set from basic solutions that lie outside the convex set. We begin by proposing an extension to intersection cuts that defines a two-term disjunction for a reverse convex set. Next, we generalize this analysis to a multi-term disjunction by considering the convex set's recession directions. These disjunctions can be used in a cut-generating linear program to obtain disjunctive cuts for the reverse convex set.

Keywords: Mixed-integer nonlinear programming, valid inequalities, reverse convex sets, disjunctive programming, intersection cuts

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Global Optimization (Theory )


Download: [PDF]

Entry Submitted: 01/07/2019
Entry Accepted: 01/08/2019
Entry Last Modified: 04/29/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society