Optimization Online


Strong Valid Inequalities for Orthogonal Disjunctions and Bilinear Covering Sets

Mohit Tawarmalani(mtawarma***at***purdue.edu)
Jean-Philippe P. Richard(richard***at***ise.ufl.edu)
Kwanghun Chung(khchung***at***ufl.edu)

Abstract: In this paper, we develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and apply a toolbox of results that help in checking the technical assumptions under which the convexification tool can be employed. We demonstrate its applicability in integer programming by deriving the intersection cut for mixed-integer polyhedral sets and the convex hull of certain mixed/pure-integer bilinear sets. We then develop a key result that extends the applicability of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant.

Keywords: Mixed Integer Nonlinear Programming, Nonlinear cuts, Convex Extensions, Disjunctive Programming, Bilinear Inequalities

Category 1: Global Optimization (Theory )

Category 2: Integer Programming (Cutting Plane Approaches )

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


Download: [PDF]

Entry Submitted: 09/24/2008
Entry Accepted: 09/29/2008
Entry Last Modified: 09/24/2008

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 Programming Society