Ebook: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems

This book deals with the theory and applications of the Reformulation- Linearization/Convexification Technique (RL T) for solving nonconvex optimization problems. A unified treatment of discrete and continuous nonconvex programming problems is presented using this approach. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. For example, the binariness on a 0-1 variable x . can be equivalently J expressed as the polynomial constraint x . (1-x . ) = 0. The motivation for this book is J J the role of tight linear/convex programming representations or relaxations in solving such discrete and continuous nonconvex programming problems. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through automatic reformulation and constraint generation techniques. As mentioned above, the focal point of this book is the development and application of RL T for use as an automatic reformulation procedure, and also, to generate strong valid inequalities. The RLT operates in two phases. In the Reformulation Phase, certain types of additional implied polynomial constraints, that include the aforementioned constraints in the case of binary variables, are appended to the problem. The resulting problem is subsequently linearized, except that certain convex constraints are sometimes retained in XV particular special cases, in the Linearization/Convexijication Phase. This is done via the definition of suitable new variables to replace each distinct variable-product term. The higher dimensional representation yields a linear (or convex) programming relaxation.

---

This book addresses a new method for generating tight linear or convex programming relaxations for discrete and continuous nonconvex programming problems. Problems of this type arise in many economics, location-allocation, scheduling and routing, and process control and engineering design applications. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through an automatic reformulation and constraint generation technique. The contents of this book comprise the original work of the authors compiled from several journal publications, and not covered in any other book on this subject. The outstanding feature of this book is that it offers for the first time a unified treatment of discrete and continuous nonconvex programming problems. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. The book lays the foundation of an idea that is stimulating and that has served to enhance the solubility of many challenging problems in the field.
Audience: This book is intended for researchers and practitioners who work in the area of discrete or continuous nonlinear, nonconvex optimization problems, as well as for students who are interested in learning about techniques for solving such problems.

---

This book addresses a new method for generating tight linear or convex programming relaxations for discrete and continuous nonconvex programming problems. Problems of this type arise in many economics, location-allocation, scheduling and routing, and process control and engineering design applications. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through an automatic reformulation and constraint generation technique. The contents of this book comprise the original work of the authors compiled from several journal publications, and not covered in any other book on this subject. The outstanding feature of this book is that it offers for the first time a unified treatment of discrete and continuous nonconvex programming problems. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. The book lays the foundation of an idea that is stimulating and that has served to enhance the solubility of many challenging problems in the field.
Audience: This book is intended for researchers and practitioners who work in the area of discrete or continuous nonlinear, nonconvex optimization problems, as well as for students who are interested in learning about techniques for solving such problems.
Content:
Front Matter....Pages i-xxiii
Introduction....Pages 1-20
Front Matter....Pages 21-21
RLT Hierarchy for Mixed-Integer Zero-One Problems....Pages 23-60
Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems....Pages 61-102
RLT Hierarchy for General Discrete Mixed-Integer Problems....Pages 103-129
Generating Valid Inequalities and Facets Using RLT....Pages 131-183
Persistency in Discrete Optimization....Pages 185-260
Front Matter....Pages 261-261
RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems....Pages 263-295
Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations....Pages 297-367
Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation....Pages 369-402
Front Matter....Pages 403-403
Applications to Discrete Problems....Pages 405-439
Applications to Continuous Problems....Pages 441-491
Back Matter....Pages 493-516

---

This book addresses a new method for generating tight linear or convex programming relaxations for discrete and continuous nonconvex programming problems. Problems of this type arise in many economics, location-allocation, scheduling and routing, and process control and engineering design applications. The principal thrust is to commence with a model that affords a useful representation and structure, and then to further strengthen this representation through an automatic reformulation and constraint generation technique. The contents of this book comprise the original work of the authors compiled from several journal publications, and not covered in any other book on this subject. The outstanding feature of this book is that it offers for the first time a unified treatment of discrete and continuous nonconvex programming problems. In essence, the bridge between these two types of nonconvexities is made via a polynomial representation of discrete constraints. The book lays the foundation of an idea that is stimulating and that has served to enhance the solubility of many challenging problems in the field.
Audience: This book is intended for researchers and practitioners who work in the area of discrete or continuous nonlinear, nonconvex optimization problems, as well as for students who are interested in learning about techniques for solving such problems.
Content:
Front Matter....Pages i-xxiii
Introduction....Pages 1-20
Front Matter....Pages 21-21
RLT Hierarchy for Mixed-Integer Zero-One Problems....Pages 23-60
Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems....Pages 61-102
RLT Hierarchy for General Discrete Mixed-Integer Problems....Pages 103-129
Generating Valid Inequalities and Facets Using RLT....Pages 131-183
Persistency in Discrete Optimization....Pages 185-260
Front Matter....Pages 261-261
RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems....Pages 263-295
Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations....Pages 297-367
Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation....Pages 369-402
Front Matter....Pages 403-403
Applications to Discrete Problems....Pages 405-439
Applications to Continuous Problems....Pages 441-491
Back Matter....Pages 493-516
....