scientific article; zbMATH DE number 1302175

From MaRDI portal
Publication:4247442





This paper is a chapter from the Handbook of Combinatorial Optimization and has therefore an overview character. Moreover, it is based on excerpts from the book by the authors entitled ``A reformulation-linearization technique for solving discrete and continuous nonconvex problems (1998; Zbl 0926.90078). The authors decided to give no proofs in this paper and refer the reader to the original research papers or the above mentioned book. The paper is divided into \(9\) sections. After an introduction containing a discussion of the existing literature (which is sometimes hard to follow since concepts which are later defined are already presented), Section \(2\) explains the Reformulation-Linearization Technique (RLT) for linear mixed integer zero-one problems (MILP). First the MILP is reformulated by multiplying each of the inequalities by predefined polynomials. To be more concrete, for the binary variables \(x_1, \ldots, x_n\) products with factors \(x_i\) and \(1 - x_i\) are built depending on the desired order \(d\) of the reformulation resulting in polynomials of degree \(d\). After multiplying the inequalities with these polynomials we obtain nonlinear constraints. A first simplification is made by using the fact that \(x_i x_i = x_i\) and \(x_i (1 - x_i) = 0\) for the binary variables \(i=1, \ldots, n\). In a next step the formulation is linearized by defining new variables for all possible products. It can be shown that the reformulation of degree \(n\) will result in the convex hull of the mixed integer zero-one problem (after a projection step). RLT is illustrated using a simple example. Section~\(3\) states some more properties of the RLT relaxation and in Section \(4\) the possibility of generating valid inequalities and facets using RLT is discussed. The next section addresses multilinear programs and equality constraints. Here a detailed application to the Quadratic Assignment Problem (QAP) is presented. For the QAP case also promising computational results are reported. Section \(6\) shows how to exploit special structures to generate tighter RLT representations. A modified version of RLT, called SSRLT (special structures reformulation-linearization technique) is developed. In the succeeding section it is demonstrated how some specific special structures can be exploited in designing an application of the general framework of SSRLT. Topics discussed include generalized upper bounding or multiple choice constraints, variable upper bounding constraints and sparse constraints. Section \(8\) is devoted to how conditional logic can be used to strengthen RLT constraints. An application to the traveling salesman problem is investigated in detail. The paper ends with conclusions and extensions. Especially, computational aspects are addressed. For the entire collection see [Zbl 0903.90001].




Cited in
(28)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247442)