Abstract
Nonconvex programs involving bilinear terms and linear equality constraints often appear more nonlinear than they really are. By using an automatic symbolic reformulation we can substitute some of the bilinear terms with linear constraints. This has a dramatically improving effect on the tightness of any convex relaxation of the problem, which makes deterministic global optimization algorithms like spatial Branch-and-Bound much more eff- cient when applied to the problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Adhya M. Tawarmalani N. Sahinidis (1999) ArticleTitleA Lagrangian approach to the pooling problem Industrial and Engineering Chemistry Research 38 1956–1972 Occurrence Handle10.1021/ie980666q
Adjiman, C. (1998), Global Optimization Techniques for Process Systems Engineering. Ph.D. thesis, Princeton University.
C. Adjiman S. Dallwig C. Floudas A. Neumaier (1998) ArticleTitleA global optimization method, α BB, for general twice-differentiable constrained NLPs: I. Theoretical advances Computers and Chemical Engineering 22 IssueID9 1137–1158 Occurrence Handle10.1016/S0098-1354(98)00027-1
A. Aho J. Hopcroft J. Ullman (1983) Data Structures and Algorithms Addison-Wesley Reading, MA
F. Al-Khayyal J. Falk (1983) ArticleTitleJointly constrained biconvex programming Mathematics of Operations Research 8 IssueID2 273–286
Epperly, T. (1995), Global optimization of nonconvex nonlinear programs using parallel branch and bound. Ph.D. thesis, University of Winsconsin, Madison.
T. Epperly E. Pistikopoulos (1997) ArticleTitleA reduced space branch and bound algorithm for global optimization Journal of Global Optimization 11 287–311 Occurrence Handle10.1023/A:1008212418949
Gill, P. (1999), User's Guide for SNOPT 5.3. Systems Optimization Laboratory, Department of EESOR, Stanford University, California.
P. Kesavan P. Barton (2000) ArticleTitleDecomposition algorithms for nonconvex mixed-integer nonlinear programs AIChE Symposium Series 96 IssueID323 458–461
B. Korte J. Vygen (2000) Combinatorial Optimization, Theory and Algorithms Springer-Verlag Berlin
L. Liberti (2004) ArticleTitleReduction constraints for the global optimization of NLPs International Transactions in Operations Research 11 33–41 Occurrence Handle10.1111/j.1475-3995.2004.00438.x
Liberti, L., Tsiakis, P., Keeping, B. and Pantelides, C. (2001),ooOPS , 1.24 ed., Centre for Process Systems Engineering, Chemical Engineering Department, Imperial College, London, UK.
G. McCormick (1976) ArticleTitleComputability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems Mathematical Programming 10 146–175 Occurrence Handle10.1007/BF01580665
H.S. Ryoo N.V. Sahinidis (1995) ArticleTitleGlobal optimization of nonconvex NLPs and MINLPs with applications in process design Computers and Chemical Engineering 19 IssueID5 551–566 Occurrence Handle10.1016/0098-1354(94)00097-8
H. Sherali A. Alameddine (1992) ArticleTitleA new Reformulation–Linearization Technique for bilinear programming problems Journal of Global Optimization 2 379–410 Occurrence Handle10.1007/BF00122429
H. Sherali J. Smith W. Adams (2000) ArticleTitleReduced first-level representations via the reformulation–linearization technique: Results, counterexamples and computations. Discrete Applied Mathematics 101 247–267 Occurrence Handle10.1016/S0166-218X(99)00225-5
Smith, E. (1996), On the optimal design of continuous processes. Ph.D. thesis, Imperial College of Science, Technology and Medicine, University of London.
E. Smith C. Pantelides (1997) ArticleTitleGlobal optimisation of nonconvex MINLPs Computers and Chemical Engineering 21 S791–S796
E. Smith C. Pantelides (1999) ArticleTitleA symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs Computers and Chemical Engineering 23 457–478 Occurrence Handle10.1016/S0098-1354(98)00286-5
R. Vaidyanathan M. El-Halwagi (1996) Global optimization of nonconvex MINLPs by interval analysis I. Grossmann (Eds) Global Optimization in Engineering Design Kluwer Academic Publishers Dordrecht 175–193
L. Wolsey (1998) Integer Programming Wiley New York
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Liberti, L. Linearity Embedded in Nonconvex Programs. J Glob Optim 33, 157–196 (2005). https://doi.org/10.1007/s10898-004-0864-2
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-004-0864-2