A reformulation-linearization technique for solving discrete and continuous nonconvex problems
type: Item
instance of: scholarly article
title: A reformulation-linearization technique for solving discrete and continuous nonconvex problems
zbMATH Open document ID: 0926.90078
author: Hanif D. Sherali
author: Warren P. Adams
published in: Nonconvex Optimization and Its Applications
publication date: 1999-03-11T00:00:00Z
review text: The book gives a new method of relaxation for discrete and continuous nonconvex programming problems. It has an Introduction and ten chapters that are grouped into three parts: Part I (Discrete nonconvex programs) contains 5 chapters that deal with discrete nonconvex programs. In the first the Reformulation-Linearization Technique (RLT) is introduced. Chapter 2 (RLT hierarchy for mixed-integer 0-1 problems) considers linear mixed 0-1 programming problems and provides the basic elements of the RLT methodology. The generation of a hierarchy of relaxations spanning the spectrum from linear programming to the convex hull representation is presented. An extension to the class of multilinear polynomial programming problems is given. Chapter 3 (Generalized hierarchy for exploiting special structures in mixed-integer 0-1 problems) presents discussions on the generalized RLT for exploiting Special Structures (SSRLT), a validation of the hierarchy for SSRLT, composing S and S-factors for some special structures. Chapter 4 (RLT hierarchy for general discrete mixed-integer problems) gives an RLT approach for general discrete mixed-integer problems. It is shown that a parallel development can be designed through the use of Lagrange interpolating polynomial factors in the reformulation phase of the procedure. The analytical construct developed provides insights into translating classes of valid inequalities for 0-1 problems to the case of general discrete variables. Chapter 5 (Generating valid inequalities and facets using RLT) is a study on convex hull characterizations and facets for the quadratic Boolean polytope and for GUB constrained knapsack polytopes. Chapter 6 (Persistency in discrete optimization) deals with RLT-based persistency for constrained 0-1 polynomial programs, RLT-based persistency for constrained 0-1 polynomial programs and a modified RLT approach. Part II (Continuous nonconvex programs) develops an RLT approach for solving condition polynomial programming pr…
reviewed by: Stefan Mititelu
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90-02
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 1260581
zbMATH Keywords: relaxation for discrete and continuous nonconvex programming problems
zbMATH Keywords: valid inequalities
zbMATH Keywords: facets
zbMATH Keywords: nonconvex polynomial programming
zbMATH Keywords: branch-and-bound
zbMATH Keywords: bilinear programming
zbMATH Keywords: squared-Euclidean distance location-allocation
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1260581