Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems

Hanif D. Sherali, Warren P. Adams and Patrick J. Driscoll
Additional contact information
Hanif D. Sherali: Virginia Polytechnic Institute and State University, Blacksburg, Virginia
Warren P. Adams: Clemson University, Clemson, South Carolina
Patrick J. Driscoll: U.S. Military Academy, West Point, New York

Operations Research, 1998, vol. 46, issue 3, 396-405

Abstract: A new hierarchy of relaxations is presented that provides a unifying framework for constructing a spectrum of continuous relaxations spanning from the linear programming relaxation to the convex hull representation for linear mixed integer 0-1 problems. This hierarchy is an extension of the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1990, 1994a), and is particularly designed to exploit special structures. Specifically, inherent special structures are exploited by identifying particular classes of multiplicative factors that are applied to the original problem to reformulate it as an equivalent polynomial programming problem, and subsequently, this resulting problem is linearized to produce a tighter relaxation in a higher dimensional space. This general framework permits us to generate an explicit hierarchical sequence of tighter relaxations leading up to the convex hull representation. (A similar hierarchy can be constructed for polynomial mixed integer 0-1 problems.) Additional ideas for further strengthening RLT-based constraints by using conditional logical implications, as well as relationships with sequential lifting, are also explored. Several examples are presented to demonstrate how underlying special structures, including generalized and variable upper bounding, covering, partitioning, and packing constraints, as well as sparsity, can be exploited within this framework. For some types of structures, low level relaxations are exhibited to recover the convex hull of integer feasible solutions.

Keywords: Programming; integer; reformulation-linearization technique; automatic reformulation procedure; hierarchy of relaxations; convex hull representations (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.396 (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:inm:oropre:v:46:y:1998:i:3:p:396-405

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().