scientific article; zbMATH DE number 1302175
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].
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions
- A revised reformulation-linearization technique for the quadratic assignment problem
- scientific article; zbMATH DE number 1857670
- A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions
- Connecting special ordered inequalities and transformation and reformulation technique in multiple choice programming
- Two new reformulation convexification based hierarchies for 0-1 MIPs
- Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations
- Models and algorithms for the product pricing with single-minded customers requesting bundles
- Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search
- Matroid optimization problems with monotone monomials in the objective
- RLT insights into lift-and-project closures
- A revised reformulation-linearization technique for the quadratic assignment problem
- A unified model for Weber problems with continuous and network distances
- A global optimization RLT-based approach for solving the hard clustering problem
- A reformulation-linearization technique for optimization over simplices
- On throughput maximization problem for UWB-based sensor networks via reformulation-linearization technique
- Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems
- scientific article; zbMATH DE number 5898062 (Why is no real title available?)
- Discrete optimization with bilinear objective function and linear constraints
- Concise RLT forms of binary programs: a computational study of the quadratic knapsack problem
- scientific article; zbMATH DE number 1857670 (Why is no real title available?)
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- A complementary column generation approach for the graph equipartition problem
- DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips
- Efficient separation of RLT cuts for implicit and explicit bilinear products
- Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
- An improved column generation algorithm for minimum sum-of-squares clustering
- Integrating lot-sizing and pricing decisions in multi-channel markets with discrete menus of prices
- Proximity guarantees of a lift-and-project approach for the cardinality-constrained Boolean quadric polytope
- A survey for the quadratic assignment problem
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
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)