Abstract
The paper describes a software package called LaGO for solving nonconvex mixed integer nonlinear programs (MINLPs). The main component of LaGO is a convex relaxation which is used for generating solution candidates and computing lower bounds of the optimal value. The relaxation is generated by reformulating the given MINLP as a block-separable problem, and replacing nonconvex functions by convex underestimators. Results on medium size MINLPs are presented.
AMS classifications: 90C22, 90C20, 90C27, 90C26, 90C59
The work was supported by the German Research Foundation (DFG) under grant NO 421/2-1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs — I. Theoretical advances. Computers and Chemical Engineering, 1137–1158 (1998)
Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. J. of Global Opt. 9, 23–40 (1997)
Alperin, H., Nowak, I.: Lagrangian Smoothing Heuristics for MaxCut. Technical report, HU–Berlin NR–2002–6 (2002)
Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib - A Collection of Test Models for Mixed-Iinteger Nonlinear Programming. INFORMS J. Comput. 15(1) (2003)
Bussieck, M.R., Pruessner, A.: Mixed-integer nonlinear programming. SIAG/OPT Newsletter: Views & News. (2003)
Bliek, C., Spellucci, P., Vicente, L., Neumaier, A., Granvilliers, L., Monfroy, E., Benhamou, F., Huens, E., Van Hentenryck, P., Sam-Haroud, D., Faltings, B.: COCONUT Deliverable D1, Algorithms for Solving Nonlinear Constrained and Optimization Problems: The State of The Art (2001), http://www.mat.univie.ac.at/neum/glopt.html
GAMS Development Corp. and GAMS Software GmbH. MINLP World (2002), http://www.gamsworld.org/minlp/
Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Brooks/Cole Publishing Company (1993)
Floudas, C.A.: Deterministic Global Optimization: Theory, Algorithms and Applications. Kluwer Academic Publishers, Dordrecht (2000)
Gill, P.E., Murray, W., Saunders, M.A.: SNOPT 5.3 user’s guide. Technical report, University of California, San Diego, Mathematics Department Report NA 97-4 (1997)
Gomes, F., Sorensen, D.: ARPACK++: a C++ Implementation of ARPACK eigenvalue package (1997), http://www.crpc.rice.edu/software/ARPACK/
Horst, R., Pardalos, P.: Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995)
Kesavan, P., Allgor, R.J., Gatzke, E.P., Barton, P.I.: Outer Approximation Algorithms for Separable Nonconvex Mixed-Integer Nonlinear Programs. Submitted to Mathematical Programming (2001)
Nowak, I.: Lagrangian Decomposition of Mixed-Integer All-Quadratic Programs. Technical report, HU–Berlin NR–2002–7 (2002)
Phillips, A., Rosen, J., Walke, V.: Molecular structure determination by global optimization. Dimacs Series in Discrete Mathematics and Theoretical Computer Science, vol. 23, pp. 181–198 (1995)
Smith, E.M.B., Pantelides, C.C.: A Symbolic Reformulation/Spatial Branch and Bound Algorithm for the Global Optimization of nonconvex MINLPs. Computers and Chemical Engineering 23, 457–478 (1999)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002)
Ugray, Z., Lasdon, L., Plummer, J., Glover, F., Kelly, J., Marti, R.: A multistart scatter search heuristic for smooth NLP and MINLP problems (2002), http://www.utexas.edu/courses/lasdon/papers.htm
Vaidyanathan, R., EL-Halwagi, M.: Global optimization of nonconvex MINLP’s by interval analysis. In: Grossmann, I.E. (ed.) Global Optimization in Engineering Design, pp. 175–193. Kluwer Academic Publishers, Dordrecht (1996)
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nowak, I., Alperin, H., Vigerske, S. (2003). LaGO – An Object Oriented Library for Solving MINLPs. In: Bliek, C., Jermann, C., Neumaier, A. (eds) Global Optimization and Constraint Satisfaction. COCOS 2002. Lecture Notes in Computer Science, vol 2861. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39901-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-39901-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20463-3
Online ISBN: 978-3-540-39901-8
eBook Packages: Springer Book Archive