Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations

AbstractIn this paper, we consider the reformulation-linearization technique (RLT) of Sherali and Adams (SIAM J. Discrete Math. 3 (3) (1990) 411–430, Discrete Appl. Math. 52 (1994) 83–106) and explore the generation of reduced first-level representations for 0–1 mixed-integer programs that tend to retain the strength of the full first-level linear programming relaxation. The motivation for this study is provided by the computational success of the first-level RLT representation (in full or partial form) experienced by several researchers working on various classes of problems. We show that there exists a first-level representation having only about half the RLT constraints that yields the same lower bound value via its relaxation. Accordingly, we attempt to a priori predict the form of this representation and identify many special cases for which this prediction is accurate. However, using various counter examples, we show that this prediction as well as several variants of it are not accurate in general, even for the case of a single binary variable. In addition, since the full first-level relaxation produces the convex hull representation for the case of a single binary variable, we investigate whether this is the case with respect to the reduced first-level relaxation as well, showing similarly that it holds true only for some special cases. Some empirical results on the relative merit and prediction capability of the reduced, versus the full, first-level representation are also provided