×

zbMATH — the first resource for mathematics

Regularized optimization methods for convex MINLP problems. (English) Zbl 1358.90086
Summary: We propose regularized cutting-plane methods for solving mixed-integer nonlinear programming problems with nonsmooth convex objective and constraint functions. The given methods iteratively search for trial points in certain localizer sets, constructed by employing linearizations of the involved functions. New trial points can be chosen in several ways; for instance, by minimizing a regularized cutting-plane model if functions are costly. When dealing with hard-to-evaluate functions, the goal is to solve the optimization problem by performing as few function evaluations as possible. Numerical experiments comparing the proposed algorithms with classical methods in this area show the effectiveness of our approach.

MSC:
90C11 Mixed integer programming
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
52A39 Mixed volumes and related topics in convex geometry
90B50 Management decision making, including multiple objectives
Software:
Bonmin; AlphaECP; OPTI
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arnold, T; Henrion, R; Moller, A; Vigerske, US, A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints, Pac J Optim, 10, 5-20, (2014) · Zbl 1294.90014
[2] Belotti, P; Kirches, C; Leyffer, S; Linderoth, J; Luedtke, J; Mahajan, A, Mixed-integer nonlinear optimization, Acta Numer, 22, 1-131, (2013) · Zbl 1291.65172
[3] Ben Amor, H; Desrosiers, J; Frangioni, A, On the choice of explicit stabilizing terms in column generation, Discret Appl Math, 157, 1167-1184, (2009) · Zbl 1169.90395
[4] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; WäChter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discret Optim, 5, 186-204, (2008) · Zbl 1151.90028
[5] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discret Optim, 5, 186-204, (2008) · Zbl 1151.90028
[6] Bruno SV, Moraes LA, de Oliveira W (2015) Optimization techniques for the Brazilian natural gas network planning problem. Energy Syst:1-21
[7] Currie J, Wilson DI (2012) OPTI: lowering the barrier between open source optimizers and the Industrial MATLAB User. In: Sahinidis N, Pinto J (eds) Foundations of Computer-Aided Process Operations. Savannah, Georgia, pp 8-11 · Zbl 1202.90238
[8] D’Ambrosio, C; Frangioni, A; Liberti, L; Lodi, A, On interval-subgradient and no-good cuts, Oper Res Lett, 38, 341-345, (2010) · Zbl 1202.90238
[9] Oliveira, W; Sagastizábal, C, Bundle methods in the xxist century: a birds’-eye view, Pesquisa Oper, 34, 647-670, (2014)
[10] Oliveira, W; Solodov, M, A doubly stabilized bundle method for nonsmooth convex optimization, Math Program, 156, 125-159, (2016) · Zbl 1346.90675
[11] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program, 91, 201-213, (2002) · Zbl 1049.90004
[12] 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
[13] Eronen, V-P; Makela, MM; Westerlund, T, On the generalization of ecp and oa methods to nonsmooth convex MINLP problems, Optimization, 63, 1057-1073, (2014) · Zbl 1295.90022
[14] Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math Program, 66, 327-349, (1994) · Zbl 0833.90088
[15] Frangioni, A; Gentile, C, Perspective cuts for a class of convex 0-1 mixed integer programs, Math Program, 106, 225-236, (2006) · Zbl 1134.90447
[16] Geoffrion, A, Generalized benders decomposition, J Optim Theory Appl, 10, 237-260, (1972) · Zbl 0229.90024
[17] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim Eng, 3, 227-252, (2002) · Zbl 1035.90050
[18] Hemmecke, R; Kppe, M; Lee, J; Weismantel, R; Jnger, M (ed.); Liebling, TM (ed.); Naddef, D (ed.); Nemhauser, GL (ed.); Pulleyblank, WR (ed.); Reinelt, G (ed.); Rinaldi, G (ed.); Wolsey, LA (ed.), Nonlinear integer programming, 561-618, (2010), Berlin, Heidelberg · Zbl 1187.90270
[19] Kelley, J, The cutting-plane method for solving convex programs, J Soc Ind Appl Math, 8, 703-712, (1960) · Zbl 0098.12104
[20] Kiwiel, K; Lemaréchal, C, An inexact bundle variant suited to column generation, Math Program, 118, 177-206, (2009) · Zbl 1163.65039
[21] Lemaréchal, C; Nemirovskii, A; Nesterov, Y, New variants of bundle methods, Math Program, 69, 111-147, (1995) · Zbl 0857.90102
[22] Leyffer, S, Integrating sqp and branch-and-bound for mixed integer nonlinear programming, Comput Optim Appl, 18, 295-309, (1998) · Zbl 1009.90074
[23] Lubin, M; Martin, K; Petra, CG; Sandiki, B, On parallelizing dual decomposition in stochastic integer programming, Oper Res Lett, 41, 252-258, (2013) · Zbl 1286.90102
[24] Mayer J (2000) On the numerical solution of jointly chance constrained problems. Chapter 12 in [31], 1st edn. Springer, New York · Zbl 1295.90022
[25] Munari, P; Gondzio, J, Using the primal-dual interior point algorithm within the branch-price-and-cut method, Comput Oper Res, 40, 2026-2036, (2013) · Zbl 1348.90478
[26] Quesada, I; Grossmann, I, An lp/nlp based branch and bound algorithm for convex MINLP optimization problems, Comput Chem Eng, 16, 937-947, (1992)
[27] Sagastizábal, C, Divide to conquer: decomposition methods for energy optimization, Math Program, 134, 187-222, (2012) · Zbl 1254.90238
[28] Schütz, P; Tomasgard, A; Ahmed, S, Supply chain design under uncertainty using sample average approximation and dual decomposition, Eur J Oper Res, 199, 409-419, (2009) · Zbl 1176.90447
[29] Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on stochastic programming: modeling and theory, MPS-SIAM series on optimization, SIAM—Society for Industrial and Applied Mathematics and Mathematical Programming Society. Philadelphia · Zbl 1169.90395
[30] Stubbs, RA; Mehrotra, S, A branch-and-cut method for 0-1 mixed convex programming, Math Program, 86, 515-532, (1999) · Zbl 0946.90054
[31] Uryas’ev S (ed) (2000) Probabilistic constrained optimization: methodology and applications. Kluwer Academic Publishers, Berlin · Zbl 0959.00019
[32] Ackooij, W; Oliveira, W, Level bundle methods for constrained convex optimization with various oracles, Comput Optim Appl, 57, 555-597, (2014) · Zbl 1329.90109
[33] Ackooij, W; Minoux, M, A characterization of the subdifferential of singular Gaussian distribution functions, Set Valued Var Anal, 23, 465-483, (2015) · Zbl 1327.90159
[34] Westerlund T, Lundqvist K (2005) Alpha-ecp, version 5.101: an interactive minlp-solver based on the extended cutting plane method, Tech. Report 01-178-A, Process Design Laboratory at Abo Akademi University. Updated version of 2005-10-21. http://www.abo.fi/ twesterl/A-ECPManual · Zbl 1294.90014
[35] Westerlund T, Pettersson F (1995) An extended cutting plane method for solving convex minlp problems. Comput Chem Eng 19(Supplement 1):131-136 (European Symposium on Computer Aided Process Engineering)
[36] 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.