×

Partially distributed outer approximation. (English) Zbl 1473.90094

Summary: This paper presents a novel partially distributed outer approximation algorithm, named PaDOA, for solving a class of structured mixed integer convex programming problems to global optimality. The proposed scheme uses an iterative outer approximation method for coupled mixed integer optimization problems with separable convex objective functions, affine coupling constraints, and compact domain. PaDOA proceeds by alternating between solving large-scale structured mixed-integer linear programming problems and partially decoupled mixed-integer nonlinear programming subproblems that comprise much fewer integer variables. We establish conditions under which PaDOA converges to global minimizers after a finite number of iterations and verify these properties with an application to thermostatically controlled loads and to mixed-integer regression.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alguacil, N.; Motto, AL; Conejo, AJ, Transmission expansion planning: a mixed-integer lp approach, IEEE Trans. Power Syst., 18, 3, 1070-1077 (2003)
[2] Andersson, J.A.E., Gillis, J., Horn, G., Rawlings, J.B., Diehl, M.: CasADi—a software framework for nonlinear optimization and optimal control. Math. Program. Comput. (2018) (in press) · Zbl 1411.90004
[3] Andreani, R.; Birgin, EG; Martinez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 1286-1309 (2007) · Zbl 1151.49027
[4] Arora, JS, Introduction to Optimum Design (2004), Amsterdam: Elsevier, Amsterdam
[5] Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer. Mat., 4, 1, 238-252 (1962) · Zbl 0109.38302
[6] Bertsekas, DP, Nonlinear Programming (1999), Belmont: Athena Scientific, Belmont · Zbl 1015.90077
[7] 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, Discrete Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028
[8] Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed integer nonlinear programs. In: Mixed Integer Nonlinear Programming, vol. 154, pp. 1-39. Springer, New York (2012) · Zbl 1242.90121
[9] Borchers, B.; Mitchell, JE, An improved branch and bound algorithm for mixed integer nonlinear programs, Comput. Oper. Res., 21, 359-368 (1994) · Zbl 0797.90069
[10] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[11] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[12] Carrion, M.; Arroyo, JM, A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem, IEEE Trans. Power Syst., 21, 3, 1371-1378 (2006)
[13] Conforti, M., Cornuéjols, G., Zambelli, G.: Polyhedral approaches to mixed integer linear programming. In: 50 Years of Integer Programming 1958-2008, pp. 343-385. Springer, New York (2009) · Zbl 1187.90002
[14] Dantzig, GB; Wolfe, P., Decomposition principle for linear programs, Oper. Res., 8, 1, 101-111 (1960) · Zbl 0093.32806
[15] Deutscher Wetterdienst. ftp://ftp-cdc.dwd.de/pub/CDC/observations_germany/climate/10_minutes/solar/historical/ (2017)
[16] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052
[17] Eckstein, J.; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073
[18] Eronen, V.; Mäkelä, MM; Westerlund, T., On the generalization of ECP and OA methods to nonsmooth convex MINLP problems, Optimization, 63, 7, 1057-1073 (2014) · Zbl 1295.90022
[19] Everett, H., Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, Oper. Res., 11, 3, 399-417 (1963) · Zbl 0113.14202
[20] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1-3, 327-349 (1994) · Zbl 0833.90088
[21] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034
[22] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) (1979), New York: W. H. Freeman, New York · Zbl 0411.68039
[23] Geoffrion, A., Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260 (1972) · Zbl 0229.90024
[24] Gupta, OK; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 1533-1546 (1985) · Zbl 0591.90065
[25] Hijazi, H.; Bonami, P.; Ouorou, A., An outer-inner approximation for separable mixed-integer nonlinear programs, INFORMS J. Comput., 26, 1, 31-44 (2014) · Zbl 1356.90091
[26] Houska, B.; Frasch, J.; Diehl, M., An augmented Lagrangian based algorithm for distributed Non-Convex optimization, SIAM J. Optim., 26, 2, 1101-1127 (2016) · Zbl 1345.90069
[27] IBM: Using the CPLEX callable library, version 12 (2009)
[28] Kesavan, P.; Allgor, RJ; Gatzke, EP; Barton, PI, Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs, Math. Program., 100, 3, 517-535 (2004) · Zbl 1136.90024
[29] Kilinç, MR; Linderoth, J.; Luedtke, J., Lift-and-project cuts for convex mixed integer nonlinear programs, Math. Program. Comput., 9, 4, 499-526 (2017) · Zbl 1387.90159
[30] Kocuk, B.; Dey, SS; Sun, X., New formulation and strong MISOCP relaxations for AC optimal transmission switching problem, IEEE Trans. Power Syst., 32, 6, 4161-4170 (2017)
[31] Kohlhepp, P.; Hagenmeyer, V., Technical potential of buildings in Germany as flexible power-to-heat storage for smart-grid operation, Energy Technol., 5, 7, 1084-1104 (2017)
[32] Kronqvist, J.; Bernal, DE; Grossmann, IE, Using regularization and second order information in outer approximation for convex MINLP, Math. Program., 180, 1, 285-310 (2020) · Zbl 1461.65168
[33] Kronqvist, J.; Lundell, A.; Westerlund, T., Reformulations for utilizing separability when solving convex MINLP problems, J. Global Optim., 71, 3, 571-592 (2018) · Zbl 1402.90098
[34] Kuindersma, S.; Deits, R.; Fallon, M.; Valenzuela, A.; Dai, H.; Permenter, F.; Koolen, T.; Marion, P.; Tedrake, R., Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot, Auton. Robot., 40, 3, 429-455 (2016)
[35] Leyffer, S., Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309 (2001) · Zbl 1009.90074
[36] Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Polyhedral approximation in mixed-integer convex optimization. Math. Program. (2017) · Zbl 1401.90158
[37] Lundell, A., Kronqvist, J., Westerlund, T.: The supporting hyperplane optimizationtoolkit—a polyhedral outer approximation based convex MINLP solver utilizing a single branchingtree approach. Optim. Online (Preprint) (2018)
[38] Marriott, K.; Stuckey, PJ, Programming with Constraints: An Introduction (1998), Cambridge: MIT Press, Cambridge · Zbl 0935.68098
[39] Murray, A., Faulwasser, T., Hagenmeyer, V.: Mixed-integer vs. real-valued formulations of distributed battery scheduling problems. In: 10th Symposium on Control of Power and Energy Systems (CPES 2018) (2018)
[40] Murty, KG; Kabadi, SN, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39, 117-129 (1987) · Zbl 0637.90078
[41] Muts, P.; Nowak, I.; Hendrix, EMT, The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 75, 1-22 (2020) · Zbl 1441.90100
[42] Muts, P., Nowak, I., Hendrix, E.M.T.: On decomposition and multiobjective-based column and disjunctive cut generation for MINLP. Optim. Eng. 1-30 (2020)
[43] Necoara, I.; Suykens, JAK, Application of a smoothing technique to decomposition in convex optimization, IEEE Trans. Autom. Control, 53, 11, 2674-2679 (2008) · Zbl 1367.90085
[44] Nocedal, J.; Wright, SJ, Sequential Quadratic Programming (2006), New York: Springer, New York
[45] Nowak, I.; Breitfeld, N.; Hendrix, EMT; Njacheun-Njanzoua, G., Decomposition-based inner-and outer-refinement algorithms for global optimization, J. Global Optim., 72, 2, 305-321 (2018) · Zbl 1417.90122
[46] Nowak, I., Muts, P., Hendrix, E.M.T.: Multi-tree decomposition methods for large-scale mixed integer nonlinear optimization. In: Large Scale Optimization in Supply Chains and Smart Manufacturing, pp. 27-58. Springer (2019) · Zbl 1446.90109
[47] Gurobi Optimization: Gurobi optimizer reference manual (2009)
[48] Powell, MJD; Fletcher, R., A method for nonlinear constraints in minimization problems, Optimization (1969), Cambridge: Academic Press, Cambridge · Zbl 0194.47701
[49] Quesada, I.; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947 (1992)
[50] Ravemark, DE; Rippin, DWT, Optimal design of a multi-product batch plant, Comput. Chem. Eng., 22, 177-183 (1998)
[51] Rockafellar, R.T.: Convex analysis (1970) · Zbl 0193.18401
[52] Rückmann, J.; Shapiro, A., Augmented Lagrangians in semi-infinite programming, Math. Program. Ser. B, 116, 499-512 (2009) · Zbl 1165.90030
[53] Sawaya, N.: Reformulations, relaxations and cutting planes for generalized disjunctive programming. Ph.D. thesis, Carnegie Mellon University (2006)
[54] Shapiro, A.; Sun, J., Some properties of the augmented Lagrangian in cone constrained optimization, Math. Oper. Res., 29, 3, 479-491 (2004) · Zbl 1082.90109
[55] Takapoui, R.; Möhle, N.; Boyd, S.; Bemporad, A., A simple effective heuristic for embedded mixed-integer quadratic programming, Int. J. Control, 86, 1-11 (2016)
[56] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249 (2005) · Zbl 1099.90047
[57] Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl., 109, 3, 475-494 (2001) · Zbl 1006.65062
[58] Vielma, JP; Dunning, I.; Huchette, J.; Lubin, M., Extended formulations in mixed integer conic quadratic programming, Math. Program. Comput., 95, 1-50 (2016) · Zbl 1387.90165
[59] Westerlund, T.; Pettersson, F., A cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136 (1995)
[60] Wright, S., Coordinate descent algorithms, Math. Program. Ser. B, 151, 1, 3-34 (2015) · Zbl 1317.49038
[61] Zhang, W., Kalsi, K., Fuller, J., Elizondo, M., Chassin, D.: Aggregate model for heterogeneous thermostatically controlled loads with demand response. In: 2012 IEEE Power and Energy Society General Meeting, pp. 1-8 (2012)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.