Combinatorial Optimal Control of Semilinear Elliptic PDEs

Optimal control problems (OCP) 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, it 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 operator in terms of 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 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 five hour time limit. In the case of the screened Poisson equation, which yields semi-infinite integer linear programs, problems with even 1400 binary controls are solved.



View Combinatorial Optimal Control of Semilinear Elliptic PDEs