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

Hanif D. Sherali, Jonathan C. Smith, Warren P. Adams

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)247-267
Number of pages21
JournalDiscrete Applied Mathematics
Volume101
Issue number1-3
DOIs
StatePublished - Apr 15 2000
Externally publishedYes

Keywords

  • Convex hull representations
  • Linear programming relaxations
  • Reformulation-linearization technique (RLT)

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations'. Together they form a unique fingerprint.

  • Cite this