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

by Sherali, Hanif D.; Adams, Warren P.

• ISBN13: 9780792354871
• ISBN10: 0792354877
• Format: Hardcover
• Copyright: 1998-11-01
• Publisher: Kluwer Academic Pub

Summary

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.

Table of Contents

Preface	xiv
Acknowledgments	xx
Copyright Permissions	xxi
Introduction	1	(20)
Discrete Linear and Nonlinear Mixed--Integer Problems	2	(12)
Continuous Nonconvex Polynomial Programming Problems	14	(3)
Coping with Large-Scale Representations	17	(4)
PART I DISCRETE NONCONVEX PROGRAMS	21	(240)
Rlt Hierarchy for Mixed-integer Zero-One Problems	23	(38)
Basic RLT Process for Linear Mixed-Integer 0-1 Problems	25	(9)
Validity of the Hierarchy of Relaxations and the Convex Hull Representation	34	(9)
Further Insights Into the Structure of the Relaxations	43	(6)
Characterization of the Facets of the Convex Hull of Feasible Solutions	49	(3)
Extension to Multilinear Polynomial Programs and Specializations for Equality Constraints	52	(9)
Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problems	61	(42)
Generalized RLT for Exploiting Special Structures (SSRLT)	63	(12)
Validation of the Hierarchy for SSRLT	75	(3)
Composing S and S-Factors for Some Special Structures	78	(13)
Generalized Upper Bounding (GUB) or Multiple Choice Constraints	78	(9)
Variable Upper Bounding Constraints	87	(3)
Sparse Constraints	90	(1)
Using Conditional Logic to Strenghten RLT/SSRLT Constraints	91	(12)
Examining Sequential Lifting as an RLT Process	93	(2)
Numerical Example to Illustrate Conditional Logic Based Enhancement of SSRLT	95	(3)
Application to the Traveling Salesman Problem	98	(5)
RLT Hierarchy for General Discrete Mixed-Integer Problems	103	(28)
The Discrete Problem and its Equivalent Zero-One Representation	104	(2)
Hierarchy of Relaxations in the Transformed Zero-One Space	106	(4)
Structure of a Parallel Hierarchy in the Original Variable Space	110	(2)
Equivalence of the Hierarchies in the Transformed and Original Spaces	112	(13)
Illustrative Example	125	(2)
Translating Valid Inequalities from Zero-One to General Discrete Spaces	127	(4)
Generating Valid Inequalities and Facets Using RLT	131	(54)
Convex Hull Characterization and Facets for the Quadric Boolean Polytope	133	(13)
Convex Hull Characterization and Facets for GUB Constrained Knapsack Polytopes	146	(14)
Tight Representations and Strong Valid Inequalities for Set Partitioning Problems	160	(25)
Notation	161	(2)
A Specialized Hierarchy of Relaxations for the Set Partitioning Polytope	163	(14)
Insights into Deleting Fractional Vertices and Generating Manageable Relaxations	177	(8)
Persistency in Discrete Optimization	185	(76)
RLT-Based Persistency for Unconstrained 0-1 Polynomial Programs	188	(24)
RLT-Based Persistency for Constrained 0-1 Polynomial Programs	212	(16)
A Modified RLT Approach	228	(29)
Persistency for unconstrained 0-1 Polynomial Programs	237	(10)
Persistency for Constrained 0-1 Polynomial Programs	247	(10)
Relationships to Published Results	257	(4)
PART II CONTINUOUS NONCONVEX PROGRAMS	261	(142)
RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problems	263	(34)
Polynomial Programs Having Integral Exponents	265	(16)
A Branch-and-Bound Algorithm	272	(7)
An Illustrative Example	279	(2)
Polynomial Programs Having Rational Exponents	281	(16)
A Branch-and-Bound Algorithm	289	(4)
An Illustrative Example	293	(4)
Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizations	297	(72)
Reformulation by Generating Quadratic Constraints (RLT-LP)	300	(2)
An Illustrative Example: Higher Order Constraints	302	(4)
Fundamental Insights and Results for the Level-One RLT Relaxation	306	(9)
Construction of Convex Hulls and Convex Envelopes: General Results and Some Special Cases	315	(20)
Enhancements of the RLT Relaxation: RLT-NLP	335	(5)
Eigen-Transformation (RLT-NLPE) and Identification of Selected Constraints (SC)	336	(2)
Reformulation-Convexification Approach: Inclusion of Suitable Nonlinear Constraints in RLT-LP to Derive RLT-NLP	338	(2)
A Lagrangian Dual Approach for Solving RLT Relaxations	340	(3)
A Preliminary Computational Comparison of the Bounding Problems	343	(4)
Design of a Branch-and-Bound Algorithm	347	(12)
Scaling	347	(1)
Branch-and-Bound Search Strategy	347	(1)
Optimality Criterion	348	(1)
Range Reductions	348	(4)
Branching Variable Selection	352	(3)
Finding Good Quality Feasible Solutions	355	(2)
Summary of the Algorithm	357	(2)
Computational Results	359	(10)
Reformulation-Convexification Technique for Polynomial Programs: Design and Implementation	369	(34)
Application of RLT to a Class of Quadrified Versus the Original Polynomial Program	372	(11)
Quadrification Process and the Application of RLT to the Quadrified Polynomial Program	373	(5)
Dominance of LP(PP) over LP (QPP)	378	(5)
A Computational Comparison: Evaluation of the Quadrification Process	383	(2)
Relaxations for Univariate Polynomial Programs	385	(3)
Squared Grid-Factor Constraints (SGF) and Associated Problem SGF-LB	387	(1)
Squared Lagrangian Interpolation Polynomial Constraints (SLIP) and Associated Problem SLIP-LB	388	(1)
Computational Evaluation of Relaxations for Univariate Problems	389	(1)
Relaxations and an Algorithm for Multivariate Problems	390	(9)
Regular RLT and Convex Variable Bounding Constraints	391	(1)
Constraint-Factor Based Restrictions	392	(2)
Constraint Filtering Scheme and Lower Bounding Problem	394	(3)
Range-Reduction Strategies	397	(1)
Branch-and-Bound Algorithm	398	(1)
Computational Results	399	(4)
PART III SPECIAL APPLICATIONS TO DISCRETE AND CONTINUOUS NONCONVEX PROGRAMS	403	(90)
Applications to Discrete Problems	405	(36)
Mixed-Integer Bilinear Programming Problems	407	(16)
An Equivalent Linear Reformulation	409	(3)
Design of an Algorithm	412	(7)
Computational Experience	419	(4)
Zero-One Quadratic Programming Problems	423	(11)
An Equivalent Linear Reformulation	425	(2)
Design of an Algorithm	427	(5)
Computational Experience	432	(2)
Miscellaneous Applications	434	(7)
Applications to Continuous Problems	441	(52)
Squard Euclidean Distance Location-Allocation Problem	443	(22)
RLT-Based Relaxation	447	(7)
A Branch-and-Bound Enumeration Algorithm	454	(5)
Computational Results	459	(6)
Linear Complementarity Problem	465	(21)
A Reformulation of the LCP	466	(6)
Proposed Algorithm	472	(7)
Computational Results	479	(7)
Miscellaneous Applications	486	(7)
References	493