Branching and bounds tighteningtechniques for non-convex MINLP

References

• Abhishek , K. , Leyffer , S. and Linderoth , J. T. 2006 . “ Filmint: an outer-approximation-based solver for nonlinear mixed integer programs ” . preprint ANL/MCS-P1374-0906
   Google Scholar
• Achterberg , T. , Koch , T. and Martin , A. 2005 . Branching rules revisited . OR Lett. , 33 ( 1 ) : 42 – 54 .
   Google Scholar
• Adjiman , C. S. and Floudas , C. A. 1996 . Rigorous convex underestimators for general twice-differentiable problems . J. Glob. Optim. , 9 ( 1 ) : 23 – 40 .
   Web of Science ®Google Scholar
• Adjiman , C. S. , Androulakis , I. P. and Floudas , C. A. 1997 . Global optimization of MINLP problems in process synthesis and design . Comput. Chem. Eng. , 21 : S445 – S450 .
   Web of Science ®Google Scholar
• Adjiman , C. S. , Androulakis , I. P. and Floudas , C. A. 1998 . A global optimization method, αBB, for general twice-differentiable constrained NLPs: II. Implementation and computational results . Comput. Chem. Eng. , 22 ( 9 ) : 1159 – 1179 .
   Web of Science ®Google Scholar
• Adjiman , C. S. , Schweiger , C. A. and Floudas , C. A. 1998 . “ Mixed-integer nonlinear optimization in process synthesis ” . In Handbook of Combinatorial Optimization , Edited by: Du , D.-Z. and Pardalos , P. M. Vol. 1 , 1 – 76 . Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Adjiman , C. S. , Androulakis , I. P. , Maranas , C. D. and Floudas , C. A. 1996 . A global optimization method, αBB, for process design . Comput. Chem. Eng. , 20 : S419 – S424 .
   Web of Science ®Google Scholar
• Adjiman , C. S. , Dallwig , S. , Floudas , C. A. and Neumaier , A. 1998 . A global optimization method, αBB, for general twice-differentiable constrained NLPs: I. Theoretical advances . Comput. Chem. Eng. , 22 ( 9 ) : 1137 – 1158 .
   Web of Science ®Google Scholar
• Androulakis , I. P. , Maranas , C. D. and Floudas , C. A. 1995 . αBB: A global optimization method for general constrained nonconvex problems . J. Glob. Optim. , 7 ( 4 ) : 337 – 363 .
   Web of Science ®Google Scholar
• Applegate , D. L. , Bixby , R. E. , Chvátal , V. and Cook , W. J. 2006 . The Traveling Salesman Problem, A Computational Study , Princeton, NJ : Princeton University Press .
   Google Scholar
• Barton , M. and Selot , A. A production allocation framework for natural gas production systems . 17th European Symposium on Computer Aided Process Engineering – ESCAPE17 . Edited by: Plesu , V. and Agachi , P. S.
   Google Scholar
• Beale , E. M.L. and Forrest , J. J.H. 1976 . Global optimization using special ordered sets . Math. Program. , 10 ( 1 ) : 52 – 69 .
   Web of Science ®Google Scholar
• P. Belotti, COUENNE, an open-source solver for mixed-integer non-convex problems, in preparation
   Google Scholar
• Benichou , M. , Gauthier , J. M. , Girodet , P. , Hentges , G. , Ribiere , G. and Vincent , O. 1971 . Experiments in mixed-integer programming . Math. Program. , 1 : 76 – 94 .
   Google Scholar
• Biegler , L. T. , Grossmann , I. E. and Westerberg , A. W. 1997 . Systematic Methods of Chemical Process Design , Upper Saddle River, NJ : Prentice Hall .
   Google Scholar
• Bonami , P. , Biegler , L. , Conn , A. , Cornuéjols , G. , Grossmann , I. , Laird , C. , Lee , J. , Lodi , A. , Margot , F. , Sawaya , N. and Wächter , A. 2008 . An algorithmic framework for convex mixed integer nonlinear programs . Discrete Optim. , 5 : 186 – 204 .
   Web of Science ®Google Scholar
• Bonami , P. , Cornuéjols , G. , Lodi , A. and Margot , F. 2009 . A feasibility pump for mixed integer nonlinear programs . Math. Program. , 119 ( 2 ) : 331 – 352 .
   Google Scholar
• Bussieck , M. R. , Drud , A. S. and Meeraus , A. 2003 . MINLPLib – a collection of test models for mixed-integer nonlinear programming . INFORMS J. Comput. , 15 ( 1 ) : 114 – 119 . Available at http://www.gamsworld.org/minlp/minlplib/minlpstat.htm
   Web of Science ®Google Scholar
• Carrizosa , E. , Hansen , P. and Messine , F. 2004 . Improving interval analysis bounds by translations . J. Glob. Optim. , 29 ( 2 ) : 157 – 172 .
   Google Scholar
• COIN-OR project. 2000. Available at http://www.coin-or.org
   Google Scholar
• Cornuéjols , G. and Tütüncü , R. 2006 . Optimization Methods in Finance , Cambridge : Cambridge University Press .
   Google Scholar
• Dolan , E. D. and Moré , J. J. 2002 . Benchmarking optimization software with performance profiles . Math. Program. , 91 ( 2 ) : 201 – 213 .
   Web of Science ®Google Scholar
• E.D. Dolan, J.J. Moré, and T.S. Munson, Benchmarking optimization software with COPS 3.0, Tech. Rep. ANL/MCS-273, Mathematics and Computer Science Division, Argonne National Laboratory, 2004. Available at http://www.mcs.anl.gov/~more/cops/cgilog.cgi?+/cops/cops3.pdf
   Google Scholar
• Epperly , T. G.W. and Pistikopoulos , E. N. 1997 . A reduced space branch and bound algorithm for global optimization . J. Glob. Optim. , 11 : 287 – 311 .
   Web of Science ®Google Scholar
• Falk , J. E. and Soland , R. M. 1969 . An algorithm for separable nonconvex programming problems . Manage. Sci. , 15 : 550 – 569 .
   Web of Science ®Google Scholar
• Fletcher , R. and Leyffer , S. 1994 . Solving mixed integer nonlinear programs by outer approximation . Math. Program. , 66 : 327 – 349 .
   Web of Science ®Google Scholar
• Fletcher , R. and Leyffer , S. 1998 . Numerical experience with lower bounds for MIQP branch-and-bound . SIAM J. Optim. , 8 ( 2 ) : 604 – 616 .
   Web of Science ®Google Scholar
• Flores-Tlacuahuac , A. and Biegler , L. T. 2007 . A robust and efficient mixed-integer non-linear dynamic optimization approach for simultaneous design and control . Comput. Chem. Eng. , 31 : 588 – 600 .
   Web of Science ®Google Scholar
• Floudas , C. A. 2001 . Global optimization in design and control of chemical process systems . J. Process Control , 10 : 125 – 134 .
   Google Scholar
• Foulds , L. R. , Haugland , D. and Jörnsten , K. 1992 . A bilinear approach to the pooling problem . Optimization , 24 : 165 – 180 .
   Google Scholar
• Fügenschuh , A. and Schewe , L. “ Solving a nonlinear mixed-integer sheet metal design problem with linear approximations ” . Working paper
   Google Scholar
• GAMS Development Corp. 2001. SBB – Available at http://www.gams.com/dd/docs/solvers/sbb.pdf
   Google Scholar
• GamsWorld Global Optimization library. 2001. Available at http://www.gamsworld.org/global/globallib/globalstat.htm
   Google Scholar
• Grossmann , I. 2002 . Review of nonlinear mixed-integer and disjunctive programming techniques . Optim. Eng. , 3 ( 3 ) : 227 – 252 .
   Web of Science ®Google Scholar
• Hansen , E. 1992 . Global Optimization Using Interval Analysis , New York : Marcel Dekker, Inc .
   Google Scholar
• Hooker , J. 2000 . Logic-based Methods for Optimization: Combining Optimization and Constraint Satisfaction , New York : Wiley .
   Google Scholar
• Horst , R. 1986 . A general-class of branch-and-bound methods in global optimization with some new approaches for concave minimization . J. Optim. Theory Appl. , 51 ( 2 ) : 271 – 291 .
   Google Scholar
• Horst , R. and Tuy , H. 1996 . Global Optimization: Deterministic Approaches , Berlin : Springer Verlag .
   Google Scholar
• Jünger , M. and Naddef , D. 2001 . Computational Combinatorial Optimization , Edited by: Jünger , M. and Naddef , D. Berlin/Heidelberg : Springer . in volume 2241 of Lecture Notes in Computer Science
   Google Scholar
• Kalantari , B. and Rosen , J. B. 1987 . An algorithm for global minimization of linearly constrained concave quadratic functions . Math. Oper. Res. , 12 ( 3 ) : 544 – 561 .
   Google Scholar
• Kallrath , J. 2005 . Solving planning and design problems in the process industry using mixed integer and global optimization . Ann. Oper. Res. , 140 ( 1 ) : 339 – 373 .
   Web of Science ®Google Scholar
• Kesavan , P. and Barton , P. I. 2000 . Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems . Comput. Chem. Eng. , 24 : 1361 – 1366 .
   Google Scholar
• Leyffer , S. 2000 . MacMINLP: ampl collection of MINLPs Available at http://www-unix.mcs.anl.gov/~leyffer/MacMINLP
   Google Scholar
• Leyffer , S. 1999 . User manual for minlp_bb UK Tech. Rep. University of Dundee
   Google Scholar
• Liberti , L. 2006 . “ Writing global optimization software ” . In Global Optimization: From Theory to Implementation , Edited by: Liberti , L. and Maculan , N. 211 – 262 . Berlin : Springer .
   Google Scholar
• Liberti , L. “ Reformulation techniques in mathematical programming ” . Thèse d'Habilitation à Diriger des Recherches .
   Google Scholar
• Liberti , L. Reformulations in mathematical programming: definitions, in . Proceedings of the 7th Cologne-Twente Workshop on Graphs and Combinatorial Optimization . Edited by: Aringhieri , R. , Cordone , R. and Righini , G. Crema : Università degli Studi di Milano .
   Google Scholar
• Liberti , L. 2009 . Reformulations in mathematical programming: definitions and systematics . RAIRO-RO , 43 ( 1 ) : 55 – 86 .
   Google Scholar
• Liberti , L. , Cafieri , S. and Tarissan , F. 2009 . “ Reformulations in mathematical programming: a computational approach ” . In Foundations of Computational Intelligence , Edited by: Abraham , A. , Hassanien , A.-E. , Siarry , P. and Engelbrecht , A. 153 – 234 . Berlin : Springer . Vol. 3(203), Studies in Computational Intelligence
   Google Scholar
• Liberti , L. , Lavor , C. and Maculan , N. 2008 . A branch-and-prune algorithm for the molecular distance geometry problem . Int. Trans. Oper. Res. , 15 : 1 – 17 .
   Google Scholar
• Liberti , L. , Lavor , C. , Chaer Nascimento , M. A. and Maculan , N. 2009 . Reformulation in mathematical programming: an application to quantum chemistry . Discrete Appl. Math. , 157 ( 6 ) : 1309 – 1318 .
   Google Scholar
• Lin , Y. and Schrage , L. 2009 . The global solver in the LINDO API . Optim. Methods Softw. , 24 : 657 – 668 .
   Web of Science ®Google Scholar
• Liu , M. L. , Sahinidis , N. V. and Shectman , J. P. 1996 . “ Planning of chemical process networks via global concave minimization ” . In Global Optimization in Engineering Design , Edited by: Grossmann , I. 195 – 230 . Boston : Springer .
   Google Scholar
• McCormick , G. P. 1972 . “ Converting general nonlinear programming problems to separable nonlinear programming problems ” . Washington DC : Program in Logistics, The George Washington University . Tech. Paper T-267
   Google Scholar
• McCormick , G. P. 1976 . Computability of global solutions to factorable nonconvex programs: part I – convex underestimating problems . Math. Programm. , 10 : 146 – 175 .
   Google Scholar
• Messine , F. 2004 . Deterministic global optimization using interval constraint propagation techniques . RAIRO-RO , 38 ( 4 ) : 277 – 294 .
   Google Scholar
• Mittelmann , H. 2005 . A collection of mixed integer quadratically constrained quadratic programs . Available at http://plato.asu.edu/ftp/ampl_files/miqp_ampl
   Google Scholar
• Mittelmann , H. 2005 . “ A collection of quadratically constrained quadratic programs ” . Available at http://plato.asu.edu/ftp/ampl_files/qp_ampl
   Google Scholar
• Moore , R. E. 1979 . Methods and Applications of Interval Analysis , Philadelphia : Siam .
   Google Scholar
• Moura , A. S. , MacGregor Smith , J. and Takahashi , R. H.C. An ellipsoidal branch-and-cut method for solving mixed-integer quasi-convex problems . Poster presented at MIP 2007, CRM . Montreal, , Canada : Université de Montreal .
   Google Scholar
• Nemhauser , G. L. and Wolsey , L. A. 1988 . Integer and Combinatorial Optimization , New York : John Wiley & Sons .
   Google Scholar
• Nowak , I. , Alperin , H. and Vigerske , S. 2003 . “ LaGO – an object oriented library for solving MINLPs ” . In Global Optimization and Constraint Satisfaction , 32 – 42 . Berlin/Heidelberg : Springer . number 2861 in Lecture Notes in Computer Science
   Google Scholar
• O'Grady , A. R.F. , Bogle , I. D.L. and Fraga , E. S. 2001 . Interval analysis in automated design for bounded solutions . Chemicke Zvesti , 55 ( 6 ) : 376 – 381 .
   Google Scholar
• Open Source Initiative OSI . 2006 . “ Common public license version 1.0 ” . Available at http://www.opensource.org/licenses/cpl1.0.php
   Google Scholar
• Padberg , M. W. and Rinaldi , G. 1991 . A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems . SIAM Rev. , 33 ( 1 ) : 60 – 100 .
   Web of Science ®Google Scholar
• Phillips , A. T. and Rosen , J. B. 1998 . “ A quadratic assignment formulation of the molecular conformation problem ” . University of Minnesota . Tech. Rep. CSD
   Google Scholar
• Quesada , I. and Grossmann , I. E. 1995 . Global optimization of bilinear process networks and multicomponent flows . Comput. Chem. Eng. , 19 ( 12 ) : 1219 – 1242 .
   Web of Science ®Google Scholar
• Ratschek , H. and Rokne , J. 1995 . “ Interval methods ” . In Handbook of Global Optimization , Edited by: Horst , R. and Pardalos , P. M. Vol. 1 , 751 – 828 . Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Ryoo , H. S. and Sahinidis , N. V. 1995 . Global optimization of nonconvex NLPs and MINLPs with applications in process design . Comput. Chem. Eng. , 19 ( 5 ) : 551 – 566 .
   Web of Science ®Google Scholar
• Ryoo , H. S. and Sahinidis , N. V. 1996 . A branch-and-reduce approach to global optimization . J. Glob. Optim. , 8 ( 2 ) : 107 – 138 .
   Web of Science ®Google Scholar
• Ryoo , H. S. and Sahinidis , N. V. 2003 . Global optimization of multiplicative programs . J. Glob. Optim. , 26 : 387 – 418 .
   Web of Science ®Google Scholar
• Sahinidis , N. V. 1996 . Baron: a general purpose global optimization software package . J. Glob. Optim. , 8 : 201 – 205 .
   Web of Science ®Google Scholar
• Sahinidis , N. V. 2003 . “ Global optimization and constraint satisfaction: the branch-and-reduce approach ” . In Global Optimization and Constraint Satisfaction , Edited by: Bliek , C. , Jermann , C. and Neumaier , A. 1 – 16 . Heidelberg : Springer . Vol. 2861 of LNCS
   Google Scholar
• Sahinidis , N. V. , Grossmann , I. E. , Fornari , R. E. and Chathrathi , M. 1989 . Optimization model for long range planning in the chemical industry . 13 : 1049 – 1063 .
   Google Scholar
• Savelsbergh , M. W.P. 1994 . Preprocessing and probing techniques for mixed integer programming problems . ORSA J. Comput. , 6 ( 4 ) : 445 – 454 .
   Google Scholar
• Shectman , J. P. and Sahinidis , N. V. 1998 . A finite algorithm for global minimization of separable concave programs . J. Glob. Optim. , 12 : 1 – 36 .
   Google Scholar
• Smith , E. M.B. 1996 . “ On the optimal design of continuous processes ” . Imperial College of Science, Technology and Medicine, University of London . Ph.D. thesis
   Google Scholar
• Smith , E. M.B. and Pantelides , C. C. 1997 . Global optimisation of nonconvex MINLPs . Comput. Chem. Eng. , 21 : S791 – S796 .
   Web of Science ®Google Scholar
• Smith , E. M.B. and Pantelides , C. C. 1999 . A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs . Comput. Chem. Eng. , 23 : 457 – 478 .
   Web of Science ®Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2002 . “ Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software and applications ” . In Nonconvex Optimization and Its Applications , Dordrecht : Kluwer Academic Publishers . Vol. 65 of
   Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2002 . “ Exact algorithms for global optimization of mixed-integer nonlinear programs ” . In Handbook of Global Optimization , Edited by: Pardalos , P. M. and Romeijn , H. E. Vol. 2 , 65 – 86 . Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2004 . Global optimization of mixed-integer nonlinear programs: a theoretical and computational study . Math. Program. , 99 ( 3 ) : 563 – 591 .
   Web of Science ®Google Scholar
• Tawarmalani , M. and Sahinidis , N. V. 2005 . A polyhedral branch-and-cut approach to global optimization . Math. Program. B , 103 : 225 – 249 .
   Web of Science ®Google Scholar
• Vaidyanathan , R. and El-Halwagi , M. 1996, pp . “ Global optimization of nonconvex MINLPs by interval analysis ” . In Global Optimization in Engineering Design , Edited by: Grossmann , I. E. 175 – 193 . Dordrecht : Kluwer Academic Publishers .
   Google Scholar
• Vandenbussche , D. and Nemhauser , G. L. 2005 . A branch-and-cut algorithm for nonconvex quadratic programs with box constraints . Math. Program. , 102 ( 3 ) : 559 – 575 .
   Web of Science ®Google Scholar
• Van Hentenryck , P. , Michel , L. and Deville , Y. 1997 . Numerica, a Modeling Language for Global Optimization , Cambridge, MA : MIT Press .
   Google Scholar
• Vielma , J. P. , Ahmed , S. and Nemhauser , G. L. 2008 . A lifted linear programming branch-and-bound algorithm for mixed integer conic quadratic programs . INFORMS J. Comput. , 20 : 438 – 450 .
   Web of Science ®Google Scholar
• Wächter , A. and Biegler , L. T. 2006 . On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming . Math. Program. , 106 ( 1 ) : 25 – 57 .
   Web of Science ®Google Scholar
• Web page for the IBM/CMU MINLP project. 2004. Available at http://egon.cheme.cmu.edu/ibm/page.htm
   Google Scholar
• Wolsey , L. A. 1998 . Integer Programming , New York : Wiley .
   Google Scholar
• Zamora , J. M. and Grossmann , I. E. 1999 . A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms . J. Glob. Optim. , 14 : 217 – 249 .
   Web of Science ®Google Scholar
• Žilinskas , J. and Bogle , I. D.L. 2003 . Evaluation ranges of functions using balanced random interval arithmetic . Informatica , 14 ( 3 ) : 403 – 416 .
   Google Scholar