Discrete optimal control with dynamic switches : outer approximation and branch-and-bound

Abstract

Many real life applications lead to optimal control problems whose control is given in form of a finite set of switches. These switches can be operated within a given continuous time horizon and admit only a finite number of states. Examples include gear-switches in automotive engineering or valves and compressors in gas networks. Solving optimal control problems with discrete control variables is challenging, and this thesis aims at developing a branch-and-bound algorithm to globally solve such problems. We here focus on parabolic control problems with binary switches that have only finitely many switching points and possibly need to satisfy further combinatorial constraints. When no restrictions on the binary switches are considered, the straightforward continuous relaxations of the binary problems are closely related to the original problems, since any relaxed control can be approximated arbitrarily well by a sequence of binary switches using an increasing number of switchings. However, solving these relaxed problems and rounding the relaxed solution to produce a binary control, often fails when considering natural combinatorial switching constraints, such as, e.g. a minimum time span between two switchings of the same switch, or an upper bound on the total number of switchings. These constraints are typically treated in a heuristic postprocessing. In contrast, the combinatorial switching constraints are at the heart of our proposed branch-and-bound algorithm to globally solve the problems. The natural branching strategy, which fixes the value of the switches in finitely many points, combined with the bounded variation of the switches, guarantees that the non-fixed part of the switching pattern vanishes. Moreover, tight dual bounds are computed by completely describing the convex hull of feasible controls in function space. This description is built by cutting planes lifted from finite-dimensional projections of the set of feasible switches. The convexified problems can be solved by means of outer approximation. In this way, we compute safe dual bounds for the binary control problems, as long as we do not take the discretization error into account. To solve the problems in function space, we estimate the discretization error contained in the bounds. An adaptive refinement strategy is then specified to handle situations where the discretization-independent bound does not exclude that a solution of desired quality might exist in the current branch. Our branch-and-bound returns an ε -optimal solution in finite time for any given tolerance ε>0. Computational results illustrate the strength of our dual bounds and the potential of the proposed branch-and-bound algorithm.