EXPLOITING SPECIAL STRUCTURES IN CONSTRUCTING A HIERARCHY OF RELAXATIONS FOR 0-1 MIXED-INTEGER PROBLEMS

A new hierarchy of relaxations is presented that provides a unifying f ramework for constructing a spectrum of continuous relaxations spannin g from the linear programming relaxation to the convex hull representa tion for linear mixed integer 0-1 problems. This hierarchy is an exten sion 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 app lied to the original problem to reformulate it as an equivalent polyno mial programming problem, and subsequently, this resulting problem is linearized to produce a tighter relaxation in a higher dimensional spa ce. This general framework permits us to generate an explicit hierarch ical sequence of tighter relaxations leading up to the convex hull rep resentation. (A similar hierarchy can be constructed for polynomial mi xed integer 0-1 problems.) Additional ideas for further strengthening RLT-based constraints by using conditional logical implications, as we ll as relationships with sequential lifting, are also explored. Severa l examples are presented to demonstrate how underlying special structu res, including generalized and variable upper bounding, covering, part itioning, and packing constraints, as well as sparsity, can be exploit ed within this framework. For some types of structures, low level rela xations are exhibited to recover the convex hull of integer feasible s olutions.