×

zbMATH — the first resource for mathematics

Convex mixed integer nonlinear programming problems and an outer approximation algorithm. (English) Zbl 1327.90144
Summary: In this paper, we mainly study one class of convex mixed-integer nonlinear programming problems (MINLPs) with non-differentiable data. By dropping the differentiability assumption, we substitute gradients with subgradients obtained from KKT conditions, and use the outer approximation method to reformulate convex MINLP as one equivalent MILP master program. By solving a finite sequence of subproblems and relaxed MILP problems, we establish an outer approximation algorithm to find the optimal solution of this convex MINLP. The convergence of this algorithm is also presented. The work of this paper generalizes and extends the outer approximation method in the sense of dealing with convex MINLPs from differentiable case to non-differentiable one.

MSC:
90C11 Mixed integer programming
90C25 Convex programming
90C30 Nonlinear programming
Software:
AlphaECP; Bonmin; LaGO
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aubin, J.P., Frankowska, H.: Set-valued Analysis. Birkhäuser, Boston (1990) · Zbl 0713.49021
[2] Bonami, P; Biegler, L; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, C; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discrete. Optim., 5, 186-204, (2008) · Zbl 1151.90028
[3] Castillo, I; Westerlund, J; Emet, S; Westerlund, T, Optimization of block layout design problems with unequal areas: a comparison of MILP and MINLP optimization methods, Comput. Chem. Eng., 30, 54-69, (2005)
[4] Drewes, S; Ulbrich, S, Subgradient based outer approximation for mixed integer second order cone pogramming. mixed integer nonlinear prog, IMA Vol. Math. Appl., 154, 41-59, (2012) · Zbl 1242.90130
[5] Duran, M; Grossmann, IE, An outer approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[6] Eronen, V-P; 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
[7] Eronen, V-P; Mäkelä, MM; Westerlund, T, Extended cutting plane method for a class of nonsmooth nonconvex MINLP problems, Optimization, (2013) · Zbl 1311.90083
[8] Fletcher, R; Leyffer, S, Solving mixed-integer nonlinear programs by outer approximation, Math. Prog., 66, 327-349, (1994) · Zbl 0833.90088
[9] Decomposition in general mathematical programming, Flippo, O.E., rinnooy kan, A.H.G, Math. Prog., 60, 361-382, (1993) · Zbl 0784.90107
[10] Floudas, C.A.: Nonlinear and Mixed Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995) · Zbl 0886.90106
[11] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory. Appl., 10, 237-260, (1972) · Zbl 0229.90024
[12] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 227-252, (2002) · Zbl 1035.90050
[13] Grossmann, I. E., Sahinidis, N. V. (eds): Special Issue on Mixed-Integer Programming and Its Application to Engineering, Part I, Optim. Eng., vol. 3(4), Kluwer Academic Publishers, Netherlands (2002)
[14] Grossmann, I. E., Sahinidis, N. V. (eds): Special Issue on Mixed-Integer Programming and Its Application to Engineering, Part II, Optim. Eng., vol. 4(1), Kluwer Academic Publishers, Netherlands (2002)
[15] Leyffer, S, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309, (2001) · Zbl 1009.90074
[16] Liberti, L; Pantelides, C, An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms, J. Global. Optim., 36, 161-189, (2006) · Zbl 1131.90045
[17] Linderoth, JT; Ralphs, TK; Karlof, J (ed.), Noncommercial software for mixed-integer linear programming, 253-303, (2005), Boca Raton · Zbl 1137.90622
[18] Michelon, P; Maculan, N, Lagrangean decomposition for integer nonlinear programming with linear constraints, Math. Program., 52, 303-313, (1991) · Zbl 0753.90047
[19] Nowak, I; Vigerske, S, Lago: a (heuristic) branch and cut algorithm for nonconvex minlps, Cent. Eur. J. Oper. Res, 16, 127-138, (2008) · Zbl 1152.90665
[20] Phelps, R.R.: Convex functions, Monotone Operators and Differentiability. Lecture Notes in Math, vol. 1364. Springer, New York (1989) · Zbl 0658.46035
[21] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[22] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Netherlands (2002) · Zbl 1031.90022
[23] Wei, Z., Ali, M.M.: Outer approximation algorithm for one class of convex mixed-integer nonlinear programming problems with partial differentiability. J. Optim. Theory. Appl. doi:10.1007/s10957-015-0715-y · Zbl 1327.90145
[24] Westerlund, T; Pettersson, F, An extended cutting plane method for solving convex MINLP problems, Computer. Chem. Eng., 19, 131-136, (1995)
[25] 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
[26] Zǎlinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002) · Zbl 1023.46003
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.