Improving mixed integer linear programming formulations

Abstract

This paper addresses the impact of first level Reformulation Linearization Technique (RLT) and Reduced Reformulation Linearization Technique (RRLT) on Mixed Integer Linear Programs (MILP) with big-M constraints. Sherali and Adams (1994) propose a RLT that generates a hierarchy of relaxations spanning from the ordinary linear programming relaxation to the nth level convex hull relaxation of feasible convex set for mixed integer zero-one programs, where n is the number of binary variables. Later, Sherali et al. (2000) show that there exists a first level representation having nearly half the RLT constraints that yield the same lower bound. The motivation of this paper is based on the computational success of the first level RLT and RRLT on various classes of problems formulated as mixed integer 0-1 programs. In contrast to Sherali and Adams (1994), who multiply all constraints with all binaries present in a formulation, we multiply only Big-M constraints with binaries present within these constraints. We solve a variety of problems such as flow-shop, job-shop and strip-packing to illustrate the performance of the modified RLT and RRLT.