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

Front Cover
Springer Science & Business Media, Dec 31, 1998 - Computers - 514 pages
0 Reviews
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

INTRODUCTION
1
11 Discrete Linear and Nonlinear MixedInteger Problems
2
12 Continuous Nonconvex Polynomial Programming Problems
14
13 Coping with LargeScale Representations
17
DISCRETE NONCONVEX PROGRAMS
21
RLT HIERARCHY FOR MIXED INTEGER ZEROONE PROBLEMS
23
21 Basic RLT Process for Linear MixedInteger 01 Problems
25
22 Validity of the Hierarchy of Relaxations and the Convex Hull Representation
34
83 Fundamental Insights and Results for the LevelOne RLT Relaxation
306
General Results and Some Special Cases
315
RLTNLP
335
851 EigenTransformation RLTNLPE and Identification of Selected Constraints SC
336
Inclusion of Suitable Nonlinear Constraints in RLTLP to Derive RLTNLP
338
86 A Lagrangian Dual Approach for Solving RLT Relaxations
340
87 A Preliminary Computational Comparison of the Bounding Problems
343
88 Design of a BranchandBound Algorithm
347

23 Further Insights Into the Structure of the Relaxations
43
24 Characterization of the Facets of the Convex Hull of Feasible Solutions
49
25 Extension to Multilinear Polynomial Programs and Specializations for Equality Constraints
52
GENERALIZED HIERARCHY FOR EXPLOITING SPECIAL STRUCTURES IN MIXEDINTEGER ZEROONE PROBLEMS
61
31 Generalized RLT for Exploiting Special Structures SSRLT
63
32 Validation of the Hierarchy for SSRLT
75
33 Composing S and SFactors for Some Special Structures
78
332 Variable Upper Bounding Constraints
87
333 Sparse Constraints
90
34 Using Conditional Logic to Strengthen RLTSSRLT Constraints
91
341 Examining Sequential Lifting as an RLT Process
93
342 Numerical Example to Illustrate Conditional Logic Based Enhancement of SSRLT
95
343 Application to the Traveling Salesman Problem
98
RLT HIERARCHY FOR GENERAL DISCRETE MIXEDINTEGER PROBLEMS
103
41 The Discrete Problem and its Equivalent ZeroOne Representation
104
42 Hierarchy of Relaxations in the Transformed ZeroOne Space
106
43 Structure of a Parallel Hierarchy in the Original Variable Space
110
44 Equivalence of the Hierarchies in the Transformed and Original Spaces
112
45 Illustrative Example
125
46 Translating Valid Inequalities from ZeroOne to General Discrete Spaces
127
GENERATING VALID INEQUALITIES AND FACETS USING RLT
131
51 Convex Hull Characterization and Facets for the Quadric Boolean Polytope
133
52 Convex Hull Characterization and Facets for GUB Constrained Knapsack Polytopes
146
53 Tight Representations and Strong Valid Inequalities for Set Partitioning Problems
160
531 Notation
161
532 A Specialized Hierarchy of Relaxations for the Set Partitioning Polytope
163
533 Insights into Deleting Fractional Vertices and Generating Manageable Relaxations
177
PERSISTENCY IN DISCRETE OPTIMIZATION
185
61 RLTBased Persistency for Unconstrained 01 Polynomial Programs
188
62 RLTBased Persistency for Constrained 01 Polynomial Programs
212
63 A Modified RLT Approach
228
631 Persistency for Unconstrained 01 Polynomial Programs
237
632 Persistency for Constrained 01 Polynomial Programs
247
64 Relationships to Published Results
257
CONTINUOUS NONCONVEX PROGRAMS
261
RLTBASED GLOBAL OPTIMIZATION ALGORITHMS FOR NONCONVEX POLYNOMIAL PROGRAMMING PROBLEMS
263
71 Polynomial Programs Having Integral Exponents
265
711 A BranchandBound Algorithm
272
712 An Illustrative Example
279
72 Polynomial Programs Having Rational Exponents
281
721 A BranchandBound Algorithm
289
722 An Illustrative Example
293
REFORMULATIONCONVEXIFICATION TECHNIQUE FOR QUADRATIC PROGRAMS AND SOME CONVEX ENVELOPE CHARACTERIZATI...
297
81 Reformulation by Generating Quadratic Constraints RLTLP
300
Higher Order Constraints
302
883 Optimally Criterion
348
885 Branching Variable Selection
352
886 Finding Good Quality Feasible Solutions
355
887 Summary of the Algorithm
357
89 Computational Results
359
REFORMULATIONCONVEXIFICATION TECHNIQUE FOR POLYNOMIAL PROGRAMS DESIGN AND IMPLEMENTATION
369
91 Application of RLT to a Class of Quadrified Versus the Original Polynomial Program
372
977 Qualification Process and the Application of RLT to the Quadrified Polynomial Program
373
972 Dominance of LPPP over LPQPP
378
Evaluation of the Quadriflcation Process
383
93 Relaxations for Univariate Polynomial Programs
385
931 Squared GridFactor Constraints SGF and Associated Problem SGFLB
387
94 Squared Lagrangian Interpolation Polynomial Constraints SLIP and Associated Problem SLIPLB
388
95 Computational Evaluation of Relaxations for Univariate Problems
389
96 Relaxations and an Algorithm for Multivariate Problems
390
961 Regular RLT and Convex Variable Bounding Constraints
391
962 ConstraintFactor Based Restrictions
392
963 Constraint Filtering Scheme and Lower Bounding Problem
394
964 RangeReduction Strategies
397
965 BranchandBound Algorithm
398
97 Computational Results
399
SPECIAL APPLICATIONS TO DISCRETE AND CONTINUOUS NONCONVEX PROGRAMS
403
APPLICATIONS TO DISCRETE PROBLEMS
405
101 MixedInteger Bilinear Programming Problems
407
1011 An Equivalent Linear Reformulation
409
1012 Design of an Algorithm
412
1013 Computational Experience
419
102 ZeroOne Quadratic Programming Problems
423
1021 An Equivalent Linear Reformulation
425
1022 Design of an Algorithm
427
1023 Computational Experience
432
103 Miscellaneous Applications
434
APPLICATIONS TO CONTINUOUS PROBLEMS
441
111 Squared Euclidean Distance LocationAllocation Problem
443
1111 RLTBased Relaxation
447
1112 A BranchandBound Enumeration Algorithm
454
1113 Computational Results
459
112 Linear Complementarity Problem
465
1121 A Reformulation of the LCP
466
1122 Proposed Algorithm
472
1123 Computational Results
479
113 Miscellaneous Applications
486
REFERENCES
493
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 512 - Dissertation. School of Industrial and Systems Engineering. Georgia Institute of Technology. Atlanta. Cullen, FH. Jarvis, JJ. and Ralliff. HD (1981), "Set partitioning based heuristics for interactive routing".
Page xxi - The Institute for Operations Research and the Management Sciences, 901 Elkridge Landing Rd..
Page xxi - Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems," Operations Research, 46(3), pp.

References to this book

All Book Search results »

About the author (1998)

Hanif D. Sherali is a University Distinguished Professor Emeritus in the Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia, USA. He is an elected member of the US National Academy of Engineering.

Bibliographic information