The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

详细信息    查看全文

• 作者：Jan Kronqvist ; Andreas Lundell ; Tapio Westerlund
• 关键词：Convex MINLP ; Extended supporting hyperplane (ESH) algorithm ; Extended cutting plane (ECP) algorithm ; Supporting hyperplanes ; Cutting planes ; Supporting hyperplane optimization toolkit (SHOT)
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：64
• 期：2
• 页码：249-272
• 全文大小：1,366 KB
• 参考文献：1.Alefeld, G.E., Potra, F.A., Shi, Y.: Algorithm 748: enclosing zeros of continuous functions. ACM Trans. Math. Softw. 21(3), 327–344 (1995)CrossRef
  2.Bagirov, A., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory, Practice and Software. Springer, New York (2014)CrossRef
  3.Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., et al.: An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5(2), 186–204 (2008)CrossRef
  4.Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed integer nonlinear programs. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and Its Applications, vol. 154, pp. 1–39. Springer, New York (2012)CrossRef
  5.Bussieck, M., Dirkse, S., Vigerske, S.: PAVER 2.0: an open source environment for automated performance analysis of benchmarking data. J. Glob. Optim. 59(2–3), 259–275 (2014)CrossRef
  6.Bussieck, M.R., Vigerske, S.: MINLP solver software. Wiley Encyclopedia of Operations Research and Management Science (2010)
  7.Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250–255 (1965)CrossRef
  8.Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36(3), 307–339 (1986)CrossRef
  9.Eronen, V.P., Mäkelä, M.M., Westerlund, T.: On the generalization of ECP and OA methods to nonsmooth convex MINLP problems. Optimization 63(7), 1057–1073 (2014)CrossRef
  10.Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45(1), 3–38 (2009)CrossRef
  11.Fourer, R., Ma, J., Martin, K.: OSiL: an instance language for optimization. Comput. Optim. Appl. 45(1), 181–203 (2010)CrossRef
  12.Gassmann, H., Ma, J., Martin, K., Sheng, W.: Optimization services 2.9 users manual (2015). https://​projects.​coin-or.​org/​OS
  13.Geoffrion, A.M.: Generalized Benders decomposition. J. Optim. Theory Appl. 10(4), 237–260 (1972)CrossRef
  14.Jeroslow, R.: There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21(1), 221–224 (1973)CrossRef
  15.Kocis, G.R., Grossmann, I.E.: Computational experience with DICOPT solving MINLP problems in process systems engineering. Comput. Chem. Eng. 13(3), 307–315 (1989)CrossRef
  16.Lastusilta, T., Bussieck, M.R., Westerlund, T.: An experimental study of the GAMS/AlphaECP MINLP solver. Ind. Eng. Chem. Res. 48(15), 7337–7345 (2009)CrossRef
  17.Leyffer, S.: Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Comput. Optim. Appl. 18(3), 295–309 (2001)CrossRef
  18.Lundell, A., Skjäl, A., Westerlund, T.: A reformulation framework for global optimization. J. Glob. Optim. 57(1), 115–141 (2013)CrossRef
  19.Lundell, A., Westerlund, J., Westerlund, T.: Some transformation techniques with applications in global optimization. J. Glob. Optim. 43(2), 391–405 (2009)CrossRef
  20.Lundell, A., Westerlund, T.: Global optimization of mixed-integer signomial programming problems. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and Its Applications, vol. 154, pp. 349–369. Springer, New York (2012)CrossRef
  21.Mäkelä, M.: Survey of bundle methods for nonsmooth optimization. Optim. Methods Softw. 17(1), 1–29 (2002)CrossRef
  22.MINLP Library 2 (2014). http://​www.​gamsworld.​org/​minlp/​minlplib2/​html/​
  23.Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59, 1–24 (2014)CrossRef
  24.Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)CrossRef
  25.Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)CrossRef
  26.Veinott Jr, A.F.: The supporting hyperplane method for unimodal programming. Oper. Res. 15(1), 147–152 (1967)CrossRef
  27.Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)CrossRef
  28.Westerlund, T., Petterson, F.: An extended cutting plane method for solving convex MINLP problems. Comput. Chem. Eng. 19, S131–S136 (1995)CrossRef
  29.Westerlund, T., Pörn, R.: Solving pseudo-convex mixed integer optimization problems by cutting plane techniques. Optim. Eng. 3(3), 253–280 (2002)CrossRef
  
• 作者单位：Jan Kronqvist (1)
  Andreas Lundell (1)
  Tapio Westerlund (1)
  
  1. Optimization and Systems Engineering, Åbo Akademi University, Turku, Finland
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916

文摘

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented. Keywords Convex MINLP Extended supporting hyperplane (ESH) algorithm Extended cutting plane (ECP) algorithm Supporting hyperplanes Cutting planes Supporting hyperplane optimization toolkit (SHOT)