Strong Valid Inequalities for Orthogonal Disjunctions and Polynomial Covering Sets

Mohit Tawarmalani, Jean-Philippe P. Richard and Kwanghun Chung

Purdue University Economics Working Papers from Purdue University, Department of Economics

Abstract: In this paper, we develop a convexification tool that enables 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. Then, we illustrate the convexification tool by developing convex hulls for certain polynomial covering sets with non-negative variables. We specialize the results to bilinear covering sets and use them to derive a tight relaxation of the bilinear covering sets over a hypercube. We use the orthogonally disjunctive characterization to show that the derived relaxation is at least as tight as the standard factorable relaxation for the same inequality, and derive necessary and sufficient conditions under which it is strictly tighter. Finally, we present a preliminary computational study on a set of randomly generated bilinear covering sets that indicates that the derived relaxation is substantially tighter than the factorable relaxation.

Keywords: Convex Analysis; Orthogonal disjunctions; Covering sets; Convex Relaxations (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 38 pages
Date: 2008-09
References: Add references at CitEc
Citations:

Downloads: (external link)
https://business.purdue.edu/research/Working-papers-series/2008/1213.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pur:prukra:1213

Access Statistics for this paper

More papers in Purdue University Economics Working Papers from Purdue University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Business PHD ().