TY - JOUR
T1 - Reduced first-level representations via the reformulation-linearization technique
T2 - Results, counterexamples, and computations
AU - Sherali, Hanif D.
AU - Smith, Jonathan C.
AU - Adams, Warren P.
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant Number DMI-9812047, and the Air Force Office of Scientific Research under Grant Number F49620-96-1-0274. The authors also thank three anonymous referees for their constructive comments that led to a greatly improved presentation.
PY - 2000/4/15
Y1 - 2000/4/15
N2 - In 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.
AB - In 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.
KW - Convex hull representations
KW - Linear programming relaxations
KW - Reformulation-linearization technique (RLT)
UR - http://www.scopus.com/inward/record.url?scp=0347934519&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347934519&partnerID=8YFLogxK
U2 - 10.1016/S0166-218X(99)00225-5
DO - 10.1016/S0166-218X(99)00225-5
M3 - Article
AN - SCOPUS:0347934519
SN - 0166-218X
VL - 101
SP - 247
EP - 267
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-3
ER -