×

zbMATH — the first resource for mathematics

An exact reformulation algorithm for large nonconvex nLPs involving bilinear terms. (English) Zbl 1131.90045
Summary: Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.

MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams W., Lassiter J., Sherali H. (1998), Persistency in 0–1 polynomial programming. Mathematics of Operations Research 2(23): 359–389 · Zbl 0977.90025
[2] Adhya N., Tawarmalani M., Sahinidis N. (1999), A Lagrangian approach to the pooling problem. Industrial and Engineering Chemistry Research 38, 1956–1972
[3] Al-Khayyal F., Falk J. (1983), Jointly constrained biconvex programming. Mathematics of Operations Research 8, 273–286 · Zbl 0521.90087
[4] Audet C., Brimberg J., Hansen P., Le Digabel S., Mladenović N. (2004), Pooling problem: alternate formulations and solution methods. Management Science 50(6): 761–776 · Zbl 1232.90349
[5] Ben-Tal A., Eiger G., Gershovitz V. (1994), Global minimization by reducing the duality gap. Mathematical Programming 63, 193–212 · Zbl 0807.90101
[6] Duff I. (1981), On algorithms for obtaining a maximum transversal. ACM Transactions Mathematical Software 7, 315–330
[7] Foulds L., Haughland D., Jornsten K. (1992), A bilinear approach to the pooling problem. Optimization 24, 165–180 · Zbl 0817.90073
[8] Goodaire E., Parmenter M. (1998), Discrete Mathematics with Graph Theory. Prentice-Hall, London · Zbl 0946.05001
[9] Harary F. (1971), Graph Theory, 2nd ed., Addison-Wesley, Reading, MA · Zbl 0209.55404
[10] Hopcroft J.E., Karp R.M. (1973), An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2, 225–231 · Zbl 0266.05114
[11] Korte B., Vygen J. (2000), Combinatorial Optimization, Theory and Algorithms. Springer-Verlag, Berlin · Zbl 0953.90052
[12] Liberti L., Pantelides C. (2003), Convex envelopes of monomials of odd degree. Journal of Global Optimization 25, 157–168 · Zbl 1030.90117
[13] McCormick G. (1976), Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming 10, 146–175 · Zbl 0349.90100
[14] Pantelides C. (1988), The consistent initialization of differential-algebraic systems. SIAM J. Sci. Stat. Comput. 9, 213–231 · Zbl 0643.65039
[15] Pardalos P., Romeijn H. ed. (2002). Handbook of Global Optimization, Vol. 2. Kluwer Academic Publishers, Dordrecht · Zbl 0991.00017
[16] Quesada I., Grossmann I. (1995), Global optimization of bilinear process networks and multicomponent flows. Computers and Chemical Engineering 19(12): 1219–1242
[17] Sahinidis N., Tawarmalani M. (2005), Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. Journal of Global Optimization. 32(2): 259–280 · Zbl 1080.90087
[18] Sherali, H. (2002), Tight relaxations for nonconvex optimization problems using the reformulation-linearization/convexification technique (RLT). In (Pardalos and Romeijn, 2002), pp. 1–63. · Zbl 1111.90353
[19] Sherali H., Adams W. (1986), A tight linearization and an algorithm for 0–1 quadratic programming problems. Management Science 32(10): 1274–1290 · Zbl 0623.90054
[20] Sherali H., Adams W. (1999). A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dordrecht · Zbl 0926.90078
[21] Sherali H., Alameddine A. (1992), A new reformulation-linearization technique for bilinear programming problems. Journal of Global Optimization 2, 379–410 · Zbl 0791.90056
[22] Sherali H., Tuncbilek C. (1997), New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Operations Research Letters 21, 1–9 · Zbl 0885.90105
[23] Smith, E. (1996), On the optimal design of continuous processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London.
[24] Smith E., Pantelides C. (1999), A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Computers & Chemical Engineering 23, 457–478
[25] Tawarmalani M., Sahinidis N. (2002a), Convexification and Global Optimization in continuous and mixed-integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht · Zbl 1031.90022
[26] Tawarmalani M., Sahinidis, N. (2002b), Exact algorithms for global optimization of mixed-integer nonlinear programs. In (Pardalos and Romeijn, 2002), pp. 1–63. · Zbl 1053.90100
[27] Tawarmalani M., Sahinidis N. (2004), Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Mathematical Programming 99, 563–591 · Zbl 1062.90041
[28] Tuy H. (1998), Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrecht · Zbl 0904.90156
[29] Visweswaran V., Floudas C. (1993), New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints. Journal of Global Optimization 3, 439-462 · Zbl 0795.90070
[30] Visweswaran V., Floudas C. (1996), New formulations and branching strategies for the GOP algorithm. In: Grossmann I.(eds). Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht · Zbl 0876.90077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.