×

Combinatorial optimal control of semilinear elliptic PDEs. (English) Zbl 1397.49030

Summary: Optimal Control Problems (OCPs) containing both integrality and Partial Differential Equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, which results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we propose a novel outer approximation approach to efficiently solve such OCPs in the case of certain semilinear elliptic PDEs with static integer controls over arbitrary combinatorial structures, where we assume the nonlinear part of the PDE to be non-decreasing and convex. The basic idea is to decompose the OCP into an Integer Linear Programming (ILP) master problem and a subproblem for calculating linear cutting planes. These cutting planes rely on the pointwise concavity or submodularity of the PDE solution with respect to the control variables. The decomposition allows us to use standard solution techniques for ILPs as well as for PDEs. We further benefit from reoptimization strategies for the PDE solution due to the iterative structure of the algorithm. Experimental results show that the new approach is capable of solving the combinatorial OCP of a semilinear Poisson equation with up to 180 binary controls to global optimality within a 5 h time limit. In the case of the screened Poisson equation, which yields semi-infinite integer linear programs, problems with as many as 1400 binary controls are solved.

MSC:

49K20 Optimality conditions for problems involving partial differential equations
90C10 Integer programming
90C05 Linear programming
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation

Software:

Bonmin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alibert, J-J; Raymond, J-P, Boundary control of semilinear elliptic equations with discontinuous leading coefficients and unbounded controls, Numer. Funct. Anal. Optim., 18, 235-250, (1997) · Zbl 0885.49010 · doi:10.1080/01630569708816758
[2] Avraam, M; Shah, N; Pantelides, C, Modelling and optimisation of general hybrid systems in the continuous time domain, Comput. Chem. Eng., 22, s221-s228, (1998) · Zbl 1122.49026 · doi:10.1016/S0098-1354(98)00058-1
[3] Balakrishna, S; Biegler, LT, A unified approach for the simultaneous synthesis of reaction, energy, and separation systems, Ind. Eng. Chem. Res., 32, 1372-1382, (1993) · doi:10.1021/ie00019a012
[4] Bansal, V; Sakizlis, V; Ross, R; Perkins, JD; Pistikopoulos, EN, New algorithms for mixed-integer dynamic optimization, Comput. Chem. Eng., 27, 647-668, (2003) · doi:10.1016/S0098-1354(02)00261-2
[5] Baumann, F; Berckey, S; Buchheim, C; Jünger, M (ed.); Reinelt, G (ed.), Exact algorithms for combinatorial optimization problems with submodular objective functions, 271-294, (2013), Berlin · Zbl 1317.90251 · doi:10.1007/978-3-642-38189-8_12
[6] 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 · doi:10.1017/S0962492913000032
[7] Boehme, T.J., Schori, M., Frank, B., Schultalbers, M., Lampe B.: Solution of a hybrid optimal control problem for parallel hybrid vehicles subject to thermal constraints. In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), IEEE, pp. 2220-2226 (2013)
[8] Bonami, P; Biegler, L; Conn, A; Cornuéjols, G; Grossmann, I; 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 · doi:10.1016/j.disopt.2006.10.011
[9] Casas, E, Control of an elliptic problem with pointwise state constraints, SIAM J. Control Optim., 24, 1309-1318, (1986) · Zbl 0606.49017 · doi:10.1137/0324078
[10] Casas, E, Boundary control of semilinear elliptic equations with pointwise state constraints, SIAM J. Control Optim., 31, 993-1006, (1993) · Zbl 0798.49020 · doi:10.1137/0331044
[11] Chandra, R.: Partial differential equations constrained combinatorial optimization on an adiabatic quantum computer. Master’s thesis, Purdue University (2013) · Zbl 1170.65055
[12] Santis, M; Pillo, G; Lucidi, S, An active set feasible method for large-scale minimization problems with bound constraints, Comput. Optim. Appl., 53, 395-423, (2012) · Zbl 1284.90075 · doi:10.1007/s10589-012-9506-7
[13] Deckelnick, K; Hinze, M, Convergence of a finite element approximation to a state constrained elliptic control problem, SIAM J. Numer. Anal., 45, 1937-1953, (2007) · Zbl 1154.65055 · doi:10.1137/060652361
[14] Dimitriadis, VD; Pistikopoulos, EN, Flexibility analysis of dynamic systems, Ind. Eng. Chem. Res., 34, 4451-4462, (1995) · doi:10.1021/ie00039a036
[15] 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 · doi:10.1007/BF02592064
[16] Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization—Eureka, You Shrink!, vol. 2570 of LNCS, pp. 11-26. Springer (2003) · Zbl 1024.90054
[17] Fügenschuh, A., Geissler, B., Martin, A., Morsi, A.: The transport PDE and mixed-integer linear programming. In: Barnhart, C., Clausen, U., Lauther, U., Möhring, R.H. (eds.) Models and Algorithms for Optimization in Logistics, no. 09261 in Dagstuhl Seminar Proceedings, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany (2009) · Zbl 1272.49026
[18] Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics. Elsevier, Amsterdam (1991) · Zbl 0728.90056
[19] Geissler, B; Kolb, O; Lang, J; Leugering, G; Martin, A; Morsi, A, Mixed integer linear models for the optimization of dynamical transport networks, Math. Methods Oper. Res., 73, 339-362, (2011) · Zbl 1245.90070 · doi:10.1007/s00186-011-0354-5
[20] Gerdts, M, A variable time transformation method for mixed-integer optimal control problems, Optim. Control Appl. Methods, 27, 169-182, (2006) · doi:10.1002/oca.778
[21] Grisvard, P.: Elliptic Problems in Nonsmooth Domains. Classics in Applied Mathematics. SIAM, Philadelphia (1985) · Zbl 0695.35060
[22] Haller-Dintelmann, R; Meyer, C; Rehberg, J; Schiela, A, Hölder continuity and optimal control for nonsmooth elliptic problems, Appl. Math. Optim., 60, 397-428, (2009) · Zbl 1179.49041 · doi:10.1007/s00245-009-9077-x
[23] Hante, FM; Sager, S, Relaxation methods for mixed-integer optimal control of partial differential equations, Comput. Optim. Appl., 55, 197-225, (2013) · Zbl 1272.49026 · doi:10.1007/s10589-012-9518-3
[24] Hintermüller, M; Kunisch, K, PDE-constrained optimization subject to pointwise constraints on the control, the state, and its derivative, SIAM J. Optim., 20, 1133-1156, (2009) · Zbl 1195.49037 · doi:10.1137/080737265
[25] Incropera, F., Witt, D.D.: Fundamentals of Heat and Mass Transfer. Wiley, Chichester (1985)
[26] Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications, vol. 31. SIAM, Philadelphia (2000) · Zbl 0988.49003 · doi:10.1137/1.9780898719451
[27] Kirches, C., Lenders, F.: Approximation properties and tight bounds for constrained mixed-integer optimal control. Technical report, Interdisciplinary Center for Scientific Computing (IWR), Heidelberg University (2016) · Zbl 1154.65055
[28] Kirches, C; Sager, S; Bock, HG; Schlöder, JP, Time-optimal control of automobile test drives with gear shifts, Optim. Control Appl. Methods, 31, 137-153, (2010) · Zbl 1204.49033 · doi:10.1002/oca.892
[29] Lovász, L; Bachem, A (ed.); Korte, B (ed.); Grötschel, M (ed.), Submodular functions and convexity, 235-257, (1983), Berlin · doi:10.1007/978-3-642-68874-4_10
[30] Meyer, C, Error estimates for the finite-element approximation of an elliptic control problem with pointwise state and control constraints, Control Cybern., 37, 51-85, (2008) · Zbl 1170.65055
[31] Meyer, C; Prüfert, U; Tröltzsch, F, On two numerical methods for state-constrained elliptic control problems, Optim. Methods Softw., 22, 871-899, (2007) · Zbl 1172.49022 · doi:10.1080/10556780701337929
[32] Mohideen, MJ; Perkins, JD; Pistikopoulos, EN, Optimal design of dynamic systems under uncertainty, AIChE J., 42, 2251-2272, (1996) · doi:10.1002/aic.690420814
[33] Quesada, I; Grossmann, I, An LP/NLP based branched and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1992) · doi:10.1016/0098-1354(92)80028-8
[34] Sager, S; Bock, H; Diehl, M, The integer approximation error in mixed-integer optimal control, Math. Program., 133, 1-23, (2012) · Zbl 1259.90077 · doi:10.1007/s10107-010-0405-3
[35] Sager, S; Jung, M; Kirches, C, Combinatorial integral approximation, Math. Methods Oper. Res., 73, 363-380, (2011) · Zbl 1220.90073 · doi:10.1007/s00186-011-0355-4
[36] Schiela, A; Wollner, W, Barrier methods for optimal control problems with convex nonlinear gradient state constraints, SIAM J. Optim., 21, 269-286, (2011) · Zbl 1279.90194 · doi:10.1137/080742154
[37] Till, J; Engell, S; Panek, S; Stursberg, O, Applied hybrid system optimization: an empirical investigation of complexity, Control Eng. Practice, 12, 1291-1303, (2004) · doi:10.1016/j.conengprac.2004.04.003
[38] Tröltzsch, F.: Optimal Control of Partial Differential Equations: Theory, Methods, and Applications. Graduate studies in Mathematics. American Mathematical Society, Providence (2010) · Zbl 1195.49001 · doi:10.1090/gsm/112
[39] von Stryk, O., Glocker, M.: Decomposition of mixed-integer optimal control problems using branch and bound and sparse direct collocation. In: Engell, S., Kowalewski, S., Zaytoon, J. (eds.) Proceedings of ADPM 2000—The 4th International Conference on Automation of Mixed Processes: Hybrid Dynamic Systems, Dortmund, pp. 99-104, Sept. 2000
[40] Zhang, P., Romero, D., Beck, J., Amon, C.: Solving wind farm layout optimization with mixed integer programming and constraint programming. In: Gomes, C., Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, vol. 7874 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 284-299 (2013) · Zbl 1382.90050
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.