A new hierarchy of relaxations for 0-1 mixed integer problems with application to some specially structured problems

Abstract

A new hierarchy of relaxations is developed that extends the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1989, 1990). This hierarchy referred to as (RLT1), 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, and is particularly designed to exploit explicit or implicit special structures defined by the constraints of a problem. Specifically, inherent special structures are exploited by identifying specific classes of multiplicative factors that can be applied to the original mathematical formulation of a problem to reformulate it as an equivalent polynomial programming problem. Subsequently, this resulting problem is linearized to produce a tighter relaxation in a higher dimensional space. This general framework permits one to generate a hierarchical sequence of tighter relaxations leading up to the convex hull representation. Several classes of constraints are presented to demonstrate how underlying special structures, including generalized upper bounding (GUB), variable upper bounding (VUB), 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. An alternative partial application of this new hierarchy is also presented, along with a discussion of some additional cases that might lend themselves to such a scheme. Additional ideas for further strengthening RLT1-based constraints by using conditional logical implications, as well as relationships with sequential lifting, are also presented.

This new RLT1 is applied in detail to the set packing problem and several formulations of the Asymmetric 'Traveling Salesman Problem (ATSP). Computational experimentation is performed to illustrate the relative strength of RLT1 relaxations in comparison to those obtained using other methods. A new class of valid inequalities for the 3-index TSP is also presented. Finally, the dissertation concludes with comments concerning extensions and parallel implementations of RLT1.