The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. (English) Zbl 1339.90247

Summary: 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.


90C11 Mixed integer programming
90C25 Convex programming
Full Text: DOI


[1] Alefeld, GE; Potra, FA; Shi, Y, Algorithm 748: enclosing zeros of continuous functions, ACM Trans. Math. Softw., 21, 327-344, (1995) · Zbl 0872.65041
[2] Bagirov, A., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory, Practice and Software. Springer, New York (2014) · Zbl 1312.90053
[3] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; etal., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028
[4] Bonami, P; Kilinç, M; Linderoth, J; Lee, J (ed.); Leyffer, S (ed.), Algorithms and software for convex mixed integer nonlinear programs, No. 154, 1-39, (2012), New York · Zbl 1242.90121
[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, 259-275, (2014) · Zbl 1300.90003
[6] Bussieck, M.R., Vigerske, S.: MINLP solver software. Wiley Encyclopedia of Operations Research and Management Science (2010)
[7] Dakin, RJ, A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 250-255, (1965) · Zbl 0154.42004
[8] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[9] Eronen, VP; Mäkelä, MM; Westerlund, T, On the generalization of ECP and OA methods to nonsmooth convex MINLP problems, Optimization, 63, 1057-1073, (2014) · Zbl 1295.90022
[10] Floudas, CA; Gounaris, CE, A review of recent advances in global optimization, J. Glob. Optim., 45, 3-38, (2009) · Zbl 1180.90245
[11] Fourer, R; Ma, J; Martin, K, Osil: an instance language for optimization, Comput. Optim. Appl., 45, 181-203, (2010) · Zbl 1189.90007
[12] Gassmann, H., Ma, J., Martin, K., Sheng, W.: Optimization services 2.9 users manual (2015). https://projects.coin-or.org/OS · Zbl 1009.90074
[13] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1972) · Zbl 0229.90024
[14] Jeroslow, R, There cannot be any algorithm for integer programming with quadratic constraints, Oper. Res., 21, 221-224, (1973) · Zbl 0257.90029
[15] Kocis, GR; Grossmann, IE, Computational experience with DICOPT solving MINLP problems in process systems engineering, Comput. Chem. Eng., 13, 307-315, (1989)
[16] Lastusilta, T; Bussieck, MR; Westerlund, T, An experimental study of the GAMS/alphaecp MINLP solver, Ind. Eng. Chem. Res., 48, 7337-7345, (2009)
[17] Leyffer, S, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309, (2001) · Zbl 1009.90074
[18] Lundell, A; Skjäl, A; Westerlund, T, A reformulation framework for global optimization, J. Glob. Optim., 57, 115-141, (2013) · Zbl 1277.90102
[19] Lundell, A; Westerlund, J; Westerlund, T, Some transformation techniques with applications in global optimization, J. Glob. Optim., 43, 391-405, (2009) · Zbl 1169.90453
[20] Lundell, A; Westerlund, T; Lee, J (ed.); Leyffer, S (ed.), Global optimization of mixed-integer signomial programming problems, No. 154, 349-369, (2012), New York · Zbl 1242.90137
[21] Mäkelä, M, Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw., 17, 1-29, (2002) · Zbl 1050.90027
[22] MINLP Library 2 (2014). http://www.gamsworld.org/minlp/minlplib2/html/ · Zbl 1189.90007
[23] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 1-24, (2014) · Zbl 1301.90063
[24] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0932.90001
[25] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[26] Veinott, AF, The supporting hyperplane method for unimodal programming, Oper. Res., 15, 147-152, (1967) · Zbl 0147.38604
[27] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[28] Westerlund, T; Petterson, F, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, s131-s136, (1995)
[29] Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 253-280, (2002) · Zbl 1035.90051
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.