Titel: Cutting planes for binary optimal control problems

Abstract:

Optimal control problems containing both integrality and partial differential
equation (PDE) constraints are very challenging in practice. The most
wide-spread solution approach is to directly discretize the entire problem,
resulting in huge nonlinear mixed-integer optimization problems that can be
solved to proven optimality only in very small dimensions. In this talk, we
propose an outer approximation approach to efficiently solve such problems in
the case of certain semilinear elliptic PDEs with static integer controls over
arbitrary combinatorial structures. The basic idea is to decompose the problem
into an integer linear programming master problem and a subproblem for
calculating linear cutting planes. These cutting planes rely on the pointwise
concavity of the PDE solution operator in terms of the control variables,
which we prove in the case of PDEs with a non-decreasing convex nonlinear
part. In particular, the projection of the feasible region to the control
space (after relaxing integrality) turns out to be convex, while the
continuous relaxations obtained in the direct discretization approach are
non-convex in general.