A reformulation-linearization technique for solving discrete and continuous nonconvex problems (Q1280199)

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 problems of the type that arise in economics, chemical engineering, design etc. Chapter 7 (RLT-based global optimization algorithms for nonconvex polynomial programming problems) presents polynomial programs having integral or rational exponents, using a branch-and-bound algorithm. Chapter 8 (Reformulation-convexification technique for quadratic programs and some convex envelope characterizations) presents several fundamental insights into the structure and properties of the RLT process and their application to construct approximation for the closure convex hull or feasible solutions, where the objective function is accommodated into the constraints. Special studies are made for the nonconvex quadratic programs and a discussion on various algorithmic strategies. Chapter 9 (Reformulation-convexification on technique for polynomial programs: Design and implementation) extends many of the algorithmic strategies and concepts to general polynomial programming problems. Special classes of RLT constraints based on convex bounds grid factors are presented, constraint factors and Lagrange interpolating polynomials. Part III (Special applications to discrete and continuous nonconvex programs) is devoted to applications for which there specially designed RLT relaxations and algorithms are available that have substantially advanced the state-of-the-art in solving these problems. Chapter 10 (Applications to discrete problems) gives discrete optimization applications of this type including 0-1 quadratic and mixed-integer bilinear programming problems. Chapter 11 (Applications to continuous problems) includes discussions on the squared-Euclidean distance location-allocation problem, the complementarity problem and miscellaneous applications.