Skip to main content
SpringerLink
Log in

Tight Relaxations for Nonconvex Optimization Problems Using the Reformulation-Linearization/Convexification Technique (RLT)

  • Chapter
Handbook of Global Optimization

Part of the book series: Nonconvex Optimization and Its Applications ((NOIA,volume 62))

Abstract

This paper provides an expository discussion on applying the Reformulation-Linearization/Convexification Technique (RLT) to design exact and approximate methods for solving nonconvex optimization problems. While the main focus here is on continuous nonconvex programs, we demonstrate that this approach provides a unifying framework that can accommodate discrete problems such as linear zero-one mixed-integer programming problems and general bounded-variable integer programs as well. The basic RLT approach is designed to solve polynomial programming problems having nonconvex polynomial objective functions and constraints. The principal RLT construct for such problems is to first reformulate the problem by adding a suitable set of polynomial constraints and then to linearize this resulting problem through a variable substitution process in order to produce a tight higher dimensional linear programming relaxation. Various additional classes of valid inequalities, filtered through a constraint selection scheme or a separation routine, are proposed to further tighten the developed relaxation while keeping it manageable in size. This relaxation can be embedded in a suitable branch-and-bound scheme in order to solve the original problem to global optimality via a sequence of linear programming problems. Because of the tight convexification effect of this technique, a limited enumeration or even the use of a local search method applied to the initial relaxation’s solution usually serves as an effective heuristic strategy. We also discuss extensions of this approach to handle polynomial programs having rational exponents, as well as general factorable programming problems, and we provide recommendations for using RLT to solve even more general unstructured classes of nonconvex programming problems. Some special case applications to solve squared-Euclidean, Euclidean, or ℓ p -distance location-allocation problems are discussed to illustrate the RLT methodology.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  • Al-Khayyal, F.A. and Falk, J.E. (1983). Jointly constrained biconvex programming. Mathematics of Operations Research,pages 273–286.

    Google Scholar 

  • Audet, C., Hansen, P., Jaumard, B., and Savard, G. (2000). A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Mathematical Programming, 87(1):131–152.

    Google Scholar 

  • Bazaraa, M.S., Jarvis, J.J., and Sherali, H.D. (1990). Linear Programming and Network Flows. John Wiley and Sons, Inc., New York, NY, 2 edition.

    Google Scholar 

  • Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (1993). Nonlinear Programming: Theory and Algorithms. John Wiley and Sons, Inc., New York, NY, 2 edition.

    Google Scholar 

  • Brimberg, J. and Love, R.F. (1991). Estimating travel distances by the weighted l? norm. Naval Research Logistics, 38:241–259.

    Google Scholar 

  • Bromberg, M. and Chang, T. (1992). One dimensional global optimization using linear lower bounds. In Floudas, C.A. and Pardalos, P.M., editors, Recent Advances in Global Optimization,pages 200–220. Princeton University Press, Princeton, NJ.

    Google Scholar 

  • Cooper, L. (1972). The transportation-location problem. Operations Research, 20(1):94–108.

    Google Scholar 

  • Duffin, R.J., Peterson, E.L., and Zener, C. (1967). Geometric Programming. John Wiley and Sons, Inc., New York, NY.

    Google Scholar 

  • Falk, J.E. and Soland, R.M. (1969). An algorithm for separable nonconvex programming problems. Management Science, 15:550–569.

    Google Scholar 

  • Fiacco, A.V. and McCormick, G.P. (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, Inc., New York, NY.

    Google Scholar 

  • Floudas, C.A. and Pardalos, P.M. (1990). A Collection of Test Problems for Constrained Global Optimization Algorithms,volume 455 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany. G. Goos and J. Hartmanis (eds.).

    Google Scholar 

  • Floudas, C.A. and Visweswaran, V. (1990). A global optimization algorithm (GOP) for certain classes of nonconvex NLP’s-1. theory. Computers and Chemical Engineering, 14:1397–1417.

    Google Scholar 

  • Floudas, C.A. and Visweswaran, V. (1993). A primal-relaxed dual global optimization approach. Journal of Optimization Theory and Applications, 78(2):187–225.

    Google Scholar 

  • Floudas, C.A. and Visweswaran, V. (1995). Quadratic optimization. In Horst, R. and Pardalos, P.M., editors, Handbook of Global Optimization,pages 217–270. Kluwer Academic Publishers, Dordrecht, The Netherlands.

    Google Scholar 

  • Francis, R.L., McGinnis, Jr., L.F., and White, J.A. (1992). Facility Layout and Location: An Analytical Approach. Prentice-Hall, Englewood Cliffs, NJ, 2 edition.

    Google Scholar 

  • Ghotb, F. (1987). Constrained nonlinear optimization with factorable programming. In Teo, K.L., Paul, H., Cheu, K.L., and Wang, C.M., editors, Proceedings of the International Conference on Optimization: Techniques and Applications, pages 842–857, Singapore. National University of Singapore.

    Google Scholar 

  • Named, A.S.E. and McCormick, G.P. (1993). Calculation of bounds on variables satisfying nonlinear inequality constraints. Journal of Global Optimization, 3: 25–47.

    Article  Google Scholar 

  • Hansen, P. and Jaumard, B. (1992). Reduction of indefinite quadratic progress to bilinear programs. Journal of Global Optimization, 2 (1): 4160.

    Article  MathSciNet  Google Scholar 

  • Hansen, P., Jaumard, B., and Lu, S. (1991). An analytical approach to global optimization. Mathematical Programming, 52: 227–254.

    Article  MathSciNet  MATH  Google Scholar 

  • Hansen, P., Jaumard, B., and Xiong, J. (1993). Decomposition and interval arithmetic applied to global minimization of polynomial and rational functions. Journal of Global Optimization, 3: 421–437.

    Article  MathSciNet  MATH  Google Scholar 

  • Hines, W.W. and Montgomery, D.C. (1972). Probability and Statistics in Engineering and Management Science. The Ronald Press Company, New York, NY.

    Google Scholar 

  • Hock, W. and Schittkowski, K. (1981). Test Examples for Nonlinear Programming Codes. Springer-Verlag, Berlin, Germany.

    Google Scholar 

  • Horst, R. and Thy, H. (1993). Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, Germany, 2 edition.

    Google Scholar 

  • Jackson, R.H.F. and McCormick, G.P. (1988). Second-order sensitivity analysis in factorable programming: theory and applications. Mathematical Programming, 41 (1): 1–27.

    Article  MathSciNet  MATH  Google Scholar 

  • Kojima, M. and Tuncel, L. (1998). Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization problems. Technical Report B-341, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan.

    Google Scholar 

  • Konno, H. and Kuno, T. (1995). Multiplicative programming problems. In Horst, R. and Pardalos, P.M., editors, Handbook of Global Optimization, pages 369–405. Kluwer Academic Publishers, Dordrecht, The Netherlands.

    Google Scholar 

  • Kortanek, K.L., Xu, X., and Ye, Y. (1995). An infeasible interior-point algorithm for solving primal and dual geometric programs. Technical report, Department of Management Science, The University of Iowa, Iowa City, IA.

    Google Scholar 

  • Kostreva, M.M. and Kinard, L.A. (1991). A differentiable homotopy approach for solving polynomial optimization problems and noncooperative games. Computers and Mathematics with Applications, 21 (6/7): 135–143.

    Article  MathSciNet  MATH  Google Scholar 

  • Lasdon, L.S., Waren, A.D., Sarkas, S., and Palacios, F. (1979). Solving the pooling problem using generalized reduced gradient and successive linear programming algorithms. ACM SIGMAP Bulletin, 27 (E): 9.

    Article  Google Scholar 

  • Love, R.F. and Juel, H. (1982). Properties and solution methods for large location-allocation problems. Journal of the Operational Research Society, 33 (5): 443–452.

    MATH  Google Scholar 

  • Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley Publishing Co., Inc., Reading, MA.

    Google Scholar 

  • Maranas, C.D. and Floudas, C.A. (1994). Global optimization in generalized geometric programming. Working paper, Department of Chemical Engineering, Princeton University, Princeton, NJ.

    Google Scholar 

  • McCormick, G.P. (1976). Computability of global solutions to factorable nonconvex programs: Part I–convex underestimating problems. Mathematical Programming, 10: 147–175.

    Article  MathSciNet  MATH  Google Scholar 

  • Murtagh, B.A. and Saunders, M.A. (1987). MINOS 5.1 User’s Guide. Technical Report Sol 83–20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA. (Update: MINOS 5.4.).

    Google Scholar 

  • Pardalos, P.M. and Rosen, J.B. (1987). Constrained Global Optimization: Algorithms and Applications, volume 268 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany. G. Coos and J. Hartmanis (eds.).

    Google Scholar 

  • Peterson, E.L. (1976). Geometric programming. SIAM Review, 18: 1–15.

    Article  MathSciNet  MATH  Google Scholar 

  • Ryoo, H.S. and Sahinidis, N.V. (1995). Global optimization of nonconvex NLPs and MINLPs with applications in process design. Computers and Chemical Engineering, 19 (5): 551–566.

    Google Scholar 

  • Sherali, H.D., Al-Loughani, I., and Subramanian, S. (1999). Global optimization procedures for the capacitated euclidean and t p distance multifacility location-allocation problems. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA. To appear in Operations Research.

    Google Scholar 

  • Sherali, H.D. and Ganesan, V. (2001). Global optimization approximation procedures for solving the container ship design problem. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA.

    Google Scholar 

  • Shectman, J.P. and Sahinidis, N.V. (1996). A finite algorithm for global minimization of separable concave programs. In Floudas, C.A. and Pardalos, P.M., editors, State of the Art in Global Optimization, pages 303–338. Kluwer Academic Publishers, Dordrecht, The Netherlands

    Chapter  Google Scholar 

  • Sherali, H.D. (1998). Global optimization of nonconvex polynomial programming problems having rational exponents. Journal of Global Optimization, 12 (3): 267–283.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Adams, W.P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3 (3): 411–430.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Adams, W.P. (1994). A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Applied Mathematics, 52: 83–106.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Adams, W.P. (1999). A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dordrecht, The Netherlands.

    Google Scholar 

  • Sherali, H.D., Adams, W.P., and Driscoll, P. (1998). Exploiting special structures in constructing a hierarchy of relaxations for 0–1 mixed integer problems. Operations Research, 46 (3): 396–405.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D., Al-Loughani, I., and Subramanian, S. (1999). Global optimization procedures for the capacitated euclidean and t p distance multifacility location-allocation problems. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA. To appear in Operations Research.

    Google Scholar 

  • Sherali, H.D. and Ganesan, V. (2001). Global optimization approximation procedures for solving the container ship design problem. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA.

    Google Scholar 

  • Sherali, H.D. and Alameddine, A. (1992). A new reformulation-linearization algorithm for solving bilinear programming problems. Journal of Global Optimization, 2: 379–410.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Fraticelli, B.M.P. (2000). Enhancing RLT relaxations via a new class of semidefinite cuts. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA. To appear in Journal of Global Optimization.

    Google Scholar 

  • Sherali, H.D. and Ganesan, V. (2001). Global optimization approximation procedures for solving the container ship design problem. Technical report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA.

    Google Scholar 

  • Sherali, H.D. and Nordai, F. (1988). NP-hard, capacitated, balanced p-median problems on a chain graph with a continuum of link demands. Mathematics of Operations Research, 13 (1): 32–49.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Smith, E.P. (1995). A global optimization approach to a water distribution network problem. Journal of Global Optimization, 11: 107–132.

    Article  MathSciNet  Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1992a). A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization, 2: 101–112.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1992b). A squared-Euclidean distance location-allocation problem. Naval Research Logistics, 39: 447469.

    Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1997a). Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems. Journal of Global Optimization, 10: 381–390.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1995). A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization, 7: 1–31.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1997a). Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems. Journal of Global Optimization, 10: 381–390.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Tuncbilek, C.H. (1997b). New reformulation-linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Operations Research Letters, 21 (1): 110.

    Article  MathSciNet  Google Scholar 

  • Sherali, H.D. and Ulular, 0. (1989). A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems. Applied Mathematics and Optimization, 20: 193–221.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Wang, H. (2001). Global optimization of nonconvex factorable programming problems. Mathematical Programming, 89 (3): 459–478.

    Article  MathSciNet  MATH  Google Scholar 

  • Shor, N.Z. (1990). Dual quadratic estimates in polynomial and boolean programming. Annals of Operations Research, 25 (1–4): 163–168.

    Article  MathSciNet  MATH  Google Scholar 

  • Sherali, H.D. and Ulular, 0. (1989). A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems. Applied Mathematics and Optimization, 20: 193–221.

    Article  MathSciNet  MATH  Google Scholar 

  • Tuncbilek, C.H. (1994). Polynomial and Indefinite Quadratic Programming Problems: Algorithms and Applications. PhD thesis, Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA.

    Google Scholar 

  • Visweswaran, V. and Floudas, C.A. (1992). Unconstrained and constrained global optimization of polynomial functions in one variable. Journal of Global Optimization, 2: 73–99.

    Article  MathSciNet  MATH  Google Scholar 

  • Visweswaran, V. and Floudas, C.A. (1993). New properties and computational improvement of the GOP algorithm for problems with quadratic objective function and constraints. Journal of Global Optimization, 3: 439–462.

    Article  MathSciNet  MATH  Google Scholar 

  • Watson, L.T., Billups, S.C., and Morgan, A.P. (1987). Algorithm 652 HOMPACK: A suite of codes for globally convergent homotopy algorithms. ACM Transactions on Mathematical Software, 13 (3): 281–310.

    Article  MathSciNet  MATH  Google Scholar 

  • Wendell, R.E. and Hurter, A.P. (1973). Location theory, dominance and convexity. Operations Research, 21 (1): 314–320.

    Article  MathSciNet  MATH  Google Scholar 

  • Wolkowicz, H., Saigal, R., and Vandenberge, L., editors (2000). Handbook of Semidefinite Programming Theory, Algorithms, and Applications, volume 27 of International Series in Operations Research and Management Science. Kluwer Academic Publishers, Dordrecht/Boston/ London.

    Google Scholar 

  • Zikan, K. (1990). `back initialization and multiple object tracking problem. Technical report, Department of Operations Research, Stanford University, Stanford, CA.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 24061, USA

    Hanif D. Sherali

Authors
  1. Hanif D. Sherali
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA

    Panos M. Pardalos  & H. Edwin Romeijn  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer Science+Business Media Dordrecht

About this chapter

Cite this chapter

Sherali, H.D. (2002). Tight Relaxations for Nonconvex Optimization Problems Using the Reformulation-Linearization/Convexification Technique (RLT). In: Pardalos, P.M., Romeijn, H.E. (eds) Handbook of Global Optimization. Nonconvex Optimization and Its Applications, vol 62. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-5362-2_1

Download citation

  • DOI: https://doi.org/10.1007/978-1-4757-5362-2_1

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4419-5221-9

  • Online ISBN: 978-1-4757-5362-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation