+612 9045 4394
A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems : Nonconvex Optimization and Its Applications - Hanif D. Sherali

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

Nonconvex Optimization and Its Applications

Hardcover Published: 31st December 1998
ISBN: 9780792354871
Number Of Pages: 518

Share This Book:


RRP $823.99
or 4 easy payments of $142.69 with Learn more
Ships in 7 to 10 business days

Other Available Editions (Hide)

  • Paperback View Product Published: 2nd December 2010

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.

Prefacep. xiv
Acknowledgmentsp. xx
Copyright Permissionsp. xxi
Introductionp. 1
Discrete Linear and Nonlinear Mixed-Integer Problemsp. 2
Continuous Nonconvex Polynomial Programming Problemsp. 14
Coping with Large-Scale Representationsp. 17
Discrete Nonconvex Programsp. 21
Rlt Hierarchy for Mixed-Integer Zero-One Problemsp. 23
Basic RLT Process for Linear Mixed-Integer 0-1 Problemsp. 25
Validity of the Hierarchy of Relaxations and the Convex Hull Representationp. 34
Further Insights Into the Structure of the Relaxationsp. 43
Characterization of the Facets of the Convex Hull of Feasible Solutionsp. 49
Extension to Multilinear Polynomial Programs and Specializations for Equality Constraintsp. 52
Generalized Hierarchy for Exploiting Special Structures in Mixed-Integer Zero-One Problemsp. 61
Generalized RLT for Exploiting Special Structures (SSRLT)p. 63
Validation of the Hierarchy for SSRLTp. 75
Composing S and S-Factors for Some Special Structuresp. 78
Generalized Upper Bounding (GUB) or Multiple Choice Constraintsp. 78
Variable Upper Bounding Constraintsp. 87
Sparse Constraintsp. 90
Using Conditional Logic to Strengthen RLT/SSRLT Constraintsp. 91
Examining Sequential Lifting as an RLT Processp. 93
Numerical Example to Illustrate Conditional Logic Based Enhancement of SSRLTp. 95
Application to the Traveling Salesman Problemp. 98
Rlt Hierarchy for General Discrete Mixed-Integer Problemsp. 103
The Discrete Problem and its Equivalent Zero-One Representationp. 104
Hierarchy of Relaxations in the Transformed Zero-One Spacep. 106
Structure of a Parallel Hierarchy in the Original Variable Spacep. 110
Equivalence of the Hierarchies in the Transformed and Original Spacesp. 112
Illustrative Examplep. 125
Translating Valid Inequalities from Zero-One to General Discrete Spacesp. 127
Generating Valid Inequalities and Facets Using Rltp. 131
Convex Hull Characterization and Facets for the Quadric Boolean Polytopep. 133
Convex Hull Characterization and Facets for GUB Constrained Knapsack Polytopesp. 146
Tight Representations and Strong Valid Inequalities for Set Partitioning Problemsp. 160
Notationp. 161
A Specialized Hierarchy of Relaxations for the Set Partitioning Polytopep. 163
Insights into Deleting Fractional Vertices and Generating Manageable Relaxationsp. 177
Persistency in Discrete Optimizationp. 185
RLT-Based Persistency for Unconstrained 0-1 Polynomial Programsp. 188
RLT-Based Persistency for Constrained 0-1 Polynomial Programsp. 212
A Modified RLT Approachp. 228
Persistency for unconstrained 0-1 Polynomial Programsp. 237
Persistency for Constrained 0-1 Polynomial Programsp. 247
Relationships to Published Resultsp. 257
Continuous Nonconvex Programsp. 261
RLT-Based Global Optimization Algorithms for Nonconvex Polynomial Programming Problemsp. 263
Polynomial Programs Having Integral Exponentsp. 265
A Branch-and-Bound Algorithmp. 272
An Illustrative Examplep. 279
Polynomial Programs Having Rational Exponentsp. 281
A Branch-and-Bound Algorithmp. 289
An Illustrative Examplep. 293
Reformulation-Convexification Technique for Quadratic Programs and Some Convex Envelope Characterizationsp. 297
Reformulation by Generating Quadratic Constraints (RLT-LP)p. 300
An Illustrative Example: Higher Order Constraintsp. 302
Fundamental Insights and Results for the Level-One RLT Relaxationp. 306
Construction of Convex Hulls and Convex Envelopes: General Results and Some Special Casesp. 315
Enhancements of the RLT Relaxation: RLT-NLPp. 335
Eigen-Transformation (RLT-NLPE) and Identification of Selected Constraints (SC)p. 336
Reformulation-Convexification Approach: Inclusion of Suitable Nonlinear Constraints in RLT-LP to Derive RLT-NLPp. 338
A Lagrangian Dual Approach for Solving RLT Relaxationsp. 340
A Preliminary Computational Comparison of the Bounding Problemsp. 343
Design of a Branch-and-Bound Algorithmp. 347
Scalingp. 347
Branch-and-Bound Search Strategyp. 347
Optimality Criterionp. 348
Range Reductionsp. 348
Branching Variable Selectionp. 352
Finding Good Quality Feasible Solutionsp. 355
Summary of the Algorithmp. 357
Computational Resultsp. 359
Reformulation-Convexification Technique for Polynomial Programs: Design and Implementationp. 369
Application of RLT to a Class of Quadrified Versus the Original Polynomial Programp. 372
Quadrification Process and the Application of RLT to the Quadrified Polynomial Programp. 373
Dominance of LP(PP) over LP (QPP)p. 378
A Computational Comparison: Evaluation of the Quadrification Processp. 383
Relaxations for Univariate Polynomial Programsp. 385
Squared Grid-Factor Constraints (SGF) and Associated Problem SGF-LBp. 387
Squared Lagrangian Interpolation Polynomial Constraints (SLIP) and Associated Problem SLIP-LBp. 388
Computational Evaluation of Relaxations for Univariate Problemsp. 389
Relaxations and an Algorithm for Multivariate Problemsp. 390
Regular RLT and Convex Variable Bounding Constraintsp. 391
Constraint-Factor Based Restrictionsp. 392
Constraint Filtering Scheme and Lower Bounding Problemp. 394
Range-Reduction Strategiesp. 397
Branch-and-Bound Algorithmp. 398
Computational Resultsp. 399
Special Applications to Discrete and Continuous Nonconvex Programsp. 403
Applications to Discrete Problemsp. 405
Mixed-Integer Bilinear Programming Problemsp. 407
An Equivalent Linear Reformulationp. 409
Design of an Algorithmp. 412
Computational Experiencep. 419
Zero-One Quadratic Programming Problemsp. 423
An Equivalent Linear Reformulationp. 425
Design of an Algorithmp. 427
Computational Experiencep. 432
Miscellaneous Applicationsp. 434
Applications to Continuous Problemsp. 441
Squared Euclidean Distance Location-Allocation Problemp. 443
RLT-Based Relaxationp. 447
A Branch-and-Bound Enumeration Algorithmp. 454
Computational Resultsp. 459
Linear Complementarity Problemp. 465
A Reformulation of the LCPp. 466
Proposed Algorithmp. 472
Computational Resultsp. 479
Miscellaneous Applicationsp. 486
Referencesp. 493
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780792354871
ISBN-10: 0792354877
Series: Nonconvex Optimization and Its Applications
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 518
Published: 31st December 1998
Publisher: Springer
Country of Publication: NL
Dimensions (cm): 23.4 x 15.6  x 3.81
Weight (kg): 2.08