## A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex ProblemsThis 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 |

493 | |

### Other editions - View all

A Reformulation-Linearization Technique for Solving Discrete and Continuous ... Hanif D. Sherali,W. P. Adams No preview available - 2010 |

A Reformulation-Linearization Technique for Solving Discrete and Continuous ... Hanif D. Sherali,W. P. Adams No preview available - 2013 |

### Common terms and phrases

applications binary valued binary variables bound-factor bounding problem branch-and-bound algorithm branching variable Chapter coefficients computational consider construct convex envelope convex hull representation corresponding CPLEX denote discrete optimization dual solution equivalent facet factors feasible region feasible solution formulation given Global Optimization Hence hyperrectangle implied incumbent solution index sets knapsack problem Lagrangian dual Lemma linear programming relaxation lower bound LP relaxation MIBLP Minimize mixed-integer multipliers node nonlinear nonnegative Note objective function objective function value objective value obtained optimal dual optimal solution packing problem polynomial programming problems polytope primal solution Problem LP(d problem QP procedure Proposition quadratic quadratic programming restrictions RLT constraints RLT process RLT relaxation RLT-LP Section Sherali solution to Problem solving SSRLT strategies subproblem subset surrogate Theorem tighten traveling salesman problem upper bound valid inequalities vertex yields zero zero-one

### 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.