# Compact Extended Formulations for
Binary Optimal Control Problems ††thanks: This work was partially supported by
Deutsche Forschungsgemeinschaft under grant no. BU 2313/7-1. The author would
like to thank Alexandra Grütering and Christian Meyer for many valuable
comments that helped to improve this paper significantly.

Christoph Buchheim  Fakultät für Mathematik, Technische Universität Dortmund

###### Abstract

Extended formulations are an important tool in polyhedral combinatorics. Many
combinatorial optimization problems require an exponential number of
inequalities when modeled as a linear program in the natural space of
variables. However, by adding artificial variables, one can often find a
compact linear formulation, i.e., one containing a polynomial number of
variables and constraints, such that the projection to the original space of
variables yields the exact linear formulation. Motivated by binary optimal
control problems with switching constraints, we show that a similar approach
can be useful also for optimization problems in function space, in order to
model the closed convex hull of feasible controls in a compact way. More
specifically, we present compact extended formulations for switches with
bounded variation and for dwell-time constraints. For general linear switching
point constraints, we devise an extended model linearizing the problem, but
show that a compact extended formulation that is compatible with
discretization cannot exist unless P$\,=\,$NP.

Keywords. binary optimal control, switching time optimization,
convexification, extended formulations

##  1 Introduction

Optimal control problems with discrete-valued control variables are a highly
topical subject in infinite-dimensional optimization. The joint consideration
of ODE- or PDE-constraints with combinatorial restrictions leads to new
challenges and insights both on the optimal control and on the discrete
optimization side. In this paper, we focus on the setting where a binary
control function varies over a continuous time horizon $[0,T]$ and assume that
a set of admissible controls $D$ is given, containing all feasible switching
patterns $u\colon[0,T]\to\\{0,1\\}$. Moreover, we assume throughout that all
$u\in D$ have bounded variation, i.e., that $u$ switches between $0$ and $1$
only a finite number of times. However, unlike in other approaches, we do not
discretize the problem a priori, so that every point in $[0,T]$ remains a
potential switching point. A rigorous formulation of these assumptions
requires a formal introduction of the function spaces in which we model the
set $D$, for this we refer to Section 2.

While many approaches presented in the literature for solving optimal control
problems over such a set $D$ are heuristic and depend on a predefined
discretization [13, 14, 15], we recently proposed a branch-and-bound algorithm
for solving such problems to global optimality in function space [5, 6, 7].
The core of the latter approach is the understanding of the closed convex hull
$\overline{\operatorname{conv}}(D)$ of the feasible set $D$ and its outer
description by linear inequalities in function space. Depending on the
structure of $D$, the separation problem for
$\overline{\operatorname{conv}}(D)$ may be intractable even for a given
discretization. For two classes of constraints, namely for the case of bounded
variation and for the so-called minimum dwell-time constraints, we however
exploit that the separation problem after discretization can be solved in
polynomial time. Both types of constraints have been considered in the
literature before. The former constraint just bounds the number of switchings
by a constant [13, 14], while the latter requires that two switchings do not
follow each other too closely in time [15].

From a combinatorial optimization perspective, this situation suggests a
closer look at the complexity of a given class of switching constraints. It
turns out, however, that a simple extension of the NP-hardness concept of
finite-dimensional optimization to function spaces is not possible, since the
complexity of the discretized problem may actually depend on the
discretization, or, more precisely, on the number of grid cells used; see
Example 6.5. Nevertheless, the tractability of relevant classes of switching
constraints in finite dimension paves the way for the transfer of well-studied
tools from discrete optimization to the infinite-dimensional setting.

One such tool are extended formulations. Many combinatorial optimization
problems require an exponential number of inequalities when modeled as a
linear program in the natural space of variables. However, by adding
artificial variables, one can often find a compact linear formulation, i.e.,
one containing a polynomial number of variables and constraints, such that the
projection to the original space of variables yields the convex hull of the
original feasible set; see [9] for a survey containing both examples and
abstract results. In the present paper, we argue that the same approach can be
useful also for optimization problems in function space. More specifically,
our aim is to devise compact extended formulations in function space for some
relevant types of constraints $D$, such that the projection to the original
space of variables agrees with $\overline{\operatorname{conv}}(D)$; see
Section 3 for a precise definition.

For the above-mentioned cases of bounded variation and dwell-time constraints,
we show that such compact extended formulations indeed exist; see Section 4
and Section 5. Both proofs are based on corresponding results about the
existence of extended formulations in the finite-dimensional case. Roughly
speaking, the extended formulations in function space can be viewed as limits
of the finite-dimensional formulations when the number of grid cells goes to
infinity. In particular, the formulations are compatible with discretization
in a certain sense. The use of these extended formulations within the branch-
and-bound algorithm of [7] could be an alternative for the outer approximation
algorithm presented in [6], leading to the same dual bounds without the need
of any separation loop.

It follows that, for the two mentioned types of constraints, discretization
leads to extended formulations in finite dimension that are already known in
the literature. However, the advantage of having at hand an extended
formulation in function space, as opposed to the first-discretize-then-
optimize paradigm, is twofold. Firstly, it shows that “in the limit” the model
is consistent, so that it can be excluded that only the discretization makes a
problem well-defined or solvable. Secondly, discretization leads to a smaller
feasible region and thus only allows to derive a primal bound for the problem
in function space. Instead, an extended formulation in function space could,
e.g., be dualized in function space and then discretized, so that a safe
_dual_ bound be computed, which would be much more valuable within a branch-
and-bound algorithm or similar approaches.

The situation is different for general switching point constraints as
considered in Section 6. Here, we parametrize the binary control by the
finitely many switching points and require that these switching points satisfy
certain linear constraints; this generalizes the minimum dwell-time
constraints. For this class, we show that a compact extended formulation that
is compatible with discretization cannot exist unless P$\,=\,$NP. This is not
only the case for a fixed discretization, but also when the discretization may
be refined. This result is essentially obtained by showing that the
corresponding sets $D$ after discretization become intractable, i.e., it is
NP-hard to optimize a given linear objective function over the latter sets.

##  2 Function Spaces and Discretization

In order to show our main results about the existence of extended
formulations, or even to define the concept of extended formulations in
infinite dimension, we first need to introduce some notation concerning
appropriate function spaces and discretization. However, we will limit
ourselves to essential definitions and observations here. For more details, we
refer the reader to the monographs [1, 4] or [2].

###  2.1 The Space $L^{2}$ and Distributional Derivatives

Given an open subset $\Omega\subseteq\mathbb{R}$, we address optimization
problems in the reflexive Banach space $L^{2}(\Omega)$ consisting of all
measurable functions $u\colon\Omega\to\mathbb{R}$ such that $|u|^{2}$ is
Lebesgue integrable, equipped with the norm

$||u||_{L^{2}(\Omega)}:=\Big{(}\int_{\Omega}|u(t)|^{2}\,\textnormal{d}t\Big{)}^{\nicefrac{{1}}{{2}}}\;.$

In $L^{2}(\Omega)$, two functions are identified if they only differ on a null
set, i.e., elements of $L^{2}(\Omega)$ are formally defined as equivalence
classes of functions. In particular, pointwise evaluations are not well-
defined for $u\in L^{2}(\Omega)$, and all constraints on $u$ discussed in the
following can only be required almost everywhere (a.e.) in $\Omega$.
Nevertheless, as is common, we will frequently specify an element $u\in
L^{2}(\Omega)$ by a pointwise definition of a representative of the
equivalence class $u$.

We write $u_{n}\to u$ if $u_{n}$ converges strongly to $u$ in $L^{2}(\Omega)$,
i.e., if $||u-u_{n}||_{L^{2}(\Omega)}\to 0$ for $n\to\infty$. For $u\in
L^{2}(\Omega)$, the distributional derivative $Du$ is the distribution defined
by

$Du(\varphi):=-\int_{\Omega}u(t)\varphi^{\prime}(t)\,\textnormal{d}t\quad\forall\varphi\in{\cal
C}^{\infty}_{c}(\Omega)\;,$

where ${\cal C}^{\infty}_{c}(\Omega)$ denotes the set of all smooth functions
$\varphi\colon\Omega\to\mathbb{R}$ with compact support. If $u$ is a
differentiable function in the classical sense, the distributional derivative
$Du$ agrees with the usual deriative $u^{\prime}$, i.e.,

$Du(\varphi)=u^{\prime}(\varphi):=\int_{\Omega}u^{\prime}(t)\varphi(t)\,\textnormal{d}t\quad\forall\varphi\in{\cal
C}^{\infty}_{c}(\Omega)\;,$

which follows from partial integration. In the following, we will write
$Du\geq 0$ if

$Du(\varphi)\geq 0\quad\forall\varphi\in{\cal
C}^{\infty}_{c}(\Omega),\varphi\geq 0\;.$

In this case, the function $u$ is monotonously increasing (outside a null
set).

The following observation shows that non-negativity of the distributional
derivative is a closed condition.

######  Lemma 2.1.

Let $u_{n}\in L^{2}(\Omega)$ with $Du_{n}\geq 0$ for all $n\in\mathbb{N}$. If
$u_{n}$ converges strongly to $u$ in $L^{2}(\Omega)$, then $Du\geq 0$.

###### Proof.

Given any fixed $\varphi\in{\cal C}^{\infty}_{c}(\Omega)$ with $\varphi\geq
0$, we have

$Du(\varphi)=\int_{\Omega}u(t)(-\varphi^{\prime}(t))\,\textnormal{d}t=\lim_{n\to\infty}\int_{\Omega}u_{n}(t)(-\varphi^{\prime}(t))\,\textnormal{d}t=\lim_{n\to\infty}Du_{n}(\varphi)\geq
0\;.$

This shows that $Du\geq 0$. ∎

###  2.2 Functions of Bounded Variation

Throughout this paper, we will consider functions of bounded variation defined
on $\Omega$. For a precise definition, consider the seminorm on
$L^{2}(\Omega)$ given by

$|u|_{BV(\Omega)}:=\sup_{\begin{subarray}{c}\varphi\in{\cal
C}^{\infty}_{c}(\Omega)\\\ ||\varphi||_{\infty}\leq
1\end{subarray}}\,\int_{\Omega}u(t)\varphi^{\prime}(t)\,\textnormal{d}t\;.$

We then define

$BV(\Omega):=\\{u\in L^{2}(\Omega)\colon|u|_{BV(\Omega)}<\infty\\}\;.$

The distributional derivative $Du$ of a function $u\in BV(\Omega)$ is a finite
signed regular Borel measure on $\Omega$. More formally, for each $u\in
BV(\Omega)$ there exists such a measure $\mu$ with

$Du(\varphi)=\int_{\Omega}\varphi(t)\,\textnormal{d}\mu\quad\forall\varphi\in{\cal
C}^{\infty}_{c}(\Omega)\;,$

and, by a slight abuse of notation, we will identify $\mu$ with $Du$. The
Jordan decomposition theorem then allows to write $Du=(Du)^{+}-(Du)^{-}$,
where $(Du)^{+}$ and $(Du)^{-}$ are non-negative measures on $\Omega$, and
this decomposition is unique. Setting $|Du|:=(Du)^{+}+(Du)^{-}$, we have
$|u|_{BV(\Omega)}=|Du|(\Omega)$ by the Radon-Riesz theorem, i.e., the
variation of $u$ is the total variation of the measure $Du$. In our proofs, we
will make extensive use of $u^{+},u^{-}\in L^{2}(\Omega)$ defined by

$u^{+}(t):=(Du)^{+}(\Omega\cap(-\infty,t)),\leavevmode\nobreak\
u^{-}(t):=(Du)^{-}(\Omega\cap(-\infty,t))$

for $u\in BV(\Omega)$. We then obtain $Du^{+}=(Du)^{+}\geq Du$ and
$Du^{-}=(Du)^{-}\geq-Du$ using Fubini’s theorem. Moreover,
$|u^{+}|_{BV(\Omega)}+|u^{-}|_{BV(\Omega)}=|u|_{BV(\Omega)}$ and hence
$u^{+},u^{-}\in BV(\Omega)$.

In this paper, we are mostly interested in functions $u\in BV(\Omega)$ with
$u\in\\{0,1\\}$ a.e. in $\Omega$. Up to null sets, these functions can thus be
viewed as binary switches that change only a finite number of times in
$\Omega$. In our formulations, we will assume moreover that the considered
time horizon is $[0,T]$, for $T\in\mathbb{Q}_{+}$, and that the switch is zero
at the beginning of this time horizon. For modeling this, given any
$S\subseteq\mathbb{R}$, we introduce the notation

$BV_{0}(0,T;S):=\\{u\in BV\big{(}(-\infty,T)\big{)}\colon u=0\text{ a.e.\ in\
}(-\infty,0),\leavevmode\nobreak\ u\in S\text{ a.e.\ in\ }(0,T)\\}\;.$

This definition ensures $Du\big{(}(-\infty,0)\big{)}=0$ and

$|u|_{BV(-\infty,T)}=|Du|(\\{0\\})+|u|_{BV(0,T)}$

for all $u\in L^{2}\big{(}(-\infty,T)\big{)}$, i.e., the initial value of $u$
in the time horizon $[0,T]$ is taken into account. Analogously, we will use
the notation

$L^{2}_{0}(0,T;S):=\\{u\in L^{2}\big{(}(-\infty,T)\big{)}\colon u=0\text{
a.e.\ in\ }(-\infty,0),\leavevmode\nobreak\ u\in S\text{ a.e.\ in\ }(0,T)\\}$

and shortly write $L^{2}_{0}(0,T)$ and $BV_{0}(0,T)$ for
$L^{2}_{0}(0,T;\mathbb{R})$ and $BV_{0}(0,T;\mathbb{R})$, respectively. By
these definitions, each function $u\in BV_{0}(0,T)$ now has a representative
$t\mapsto Du([0,t])$.

###  2.3 Discretization and Approximation by Piecewise Constant Functions

Since we are mostly interested in binary functions, a natural approach for
discretization uses piecewise constant functions. For simplicity, we will
concentrate on equidistant grids throughout the paper. Given a number
$N\in\mathbb{N}$ of grid cells and $v\in\mathbb{R}^{N}$, let $\overline{v}\in
L^{2}_{0}(0,T)$ be the piecewise constant function defined by

$\overline{v}=v_{i}\text{ on
}\Big{(}(i-1)\tfrac{T}{N},i\tfrac{T}{N}\Big{)},\leavevmode\nobreak\
i=1,\dots,N\;.$

Conversely, given $u\in L^{2}_{0}(0,T)$, let $u_{N}\in\mathbb{R}^{N}$ be
defined by the piecewise averages

$(u_{N})_{i}:=\tfrac{N}{T}\int_{(i-1)\frac{T}{N}}^{i\frac{T}{N}}u(t)\,\textnormal{d}t$

for $i=1,\dots,N$. Clearly, we then have $\overline{v}_{N}=v$ for all
$v\in\mathbb{R}^{N}$. For the following, we further introduce the notation
${u}_{[N]}:=\overline{u_{N}}\in L^{2}_{0}(0,T)$ for $u\in L^{2}_{0}(0,T)$.

######  Definition 2.2.

Let $D\subseteq L^{2}_{0}(0,T)$ and $N\in\mathbb{N}$. Then the
_discretization_ $D_{N}$ of $D$ is defined as the subset
$D\cap\\{\bar{u}\colon u\in\mathbb{R}^{N}\\}$ of $D$.

By this definition, the discretization $D_{N}$ consists of piecewise constant
functions. However, we will sometimes identify $D_{N}$ with a subset of
$\mathbb{R}^{N}$ in the obvious way.

######  Lemma 2.3.

For every $D\subseteq L^{2}_{0}(0,T)$, we have
$\operatorname{conv}(D_{N})\subseteq\operatorname{conv}(D)_{N}$.

###### Proof.

Let $u\in\operatorname{conv}(D_{N})\subseteq L^{2}_{0}(0,T)_{N}$ and choose
$\lambda_{i}\geq 0$ and $u^{i}\in D_{N}\subseteq D$ for $i=1,\dots,k$ such
that $\sum_{i=1}^{k}\lambda_{i}=1$ and $u=\sum_{i=1}^{k}\lambda_{i}u^{i}$.
Then $u\in\operatorname{conv}(D)$ and hence $u\in\operatorname{conv}(D)_{N}$.
∎

Note that $\operatorname{conv}(D_{N})\neq\operatorname{conv}(D)_{N}$ in
general. For a simple example, let $D=\\{\chi_{[0,1]},\chi_{[1,2]}\\}$ with
$T=2$, where $\chi_{A}$ denotes the characteristic function of
$A\subseteq\mathbb{R}$. Then $D_{N}=\emptyset$ for all odd $N\in\mathbb{N}$,
since each $u\in D_{N}$ must be constant on $[\tfrac{N-1}{N},\tfrac{N+1}{N}]$,
but then $u\not\in D$. On the other hand, we have
$\tfrac{1}{2}\chi_{[0,2]}\in\operatorname{conv}(D)_{N}$ for all $N$.

The following observation is a central ingredient in our proofs presented in
the subsequent sections. It shows that a function $u\in L^{2}(0,T)$ can be
approximated by its piecewise averages provided that $u$ has bounded
variation; see Figure 1 for an illustration.

Figure 1: Approximation of a function of bounded variation by its piecewise
averages according to Lemma 2.4: a given function $u\in BV_{0}(0,T)$ (upper
left) and the piecewise averages $u_{[4]}$, $u_{[8]}$, and $u_{[16]}$.

######  Lemma 2.4.

Let $u\in BV_{0}(0,T)$. Then the piecewise averages ${u}_{[N]}$ strongly
converge to $u$ in $L^{2}_{0}(0,T)$ for $N\to\infty$.

###### Proof.

Using the above definitions, we obtain

$\displaystyle||u-{u}_{[N]}||_{L^{2}(0,T)}^{2}$ $\displaystyle=$
$\displaystyle\int_{0}^{T}|u(t)-{u}_{[N]}(t)|^{2}\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\int_{(i-1)\frac{T}{N}}^{i\frac{T}{N}}|u(t)-(u_{N})_{i}|^{2}\,\textnormal{d}t$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\tfrac{T}{N}||u-(u_{N})_{i}||_{L^{\infty}((i-1)\frac{T}{N},i\frac{T}{N})}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \tfrac{T}{N}|u|_{BV(-\infty,T)}^{2}\;,$

and the latter expression converges to zero for $N\to\infty$. ∎

We finally note that, if $Du\geq 0$, the monotonicity of $u$ is also reflected
in the discretization:

######  Lemma 2.5.

Let $u\in L^{2}_{0}(0,T)$ with $Du\geq 0$. Then
$(u_{N})_{N}\geq(u_{N})_{N-1}\geq\dots\geq(u_{N})_{1}\geq 0$.

###### Proof.

For $i=0,\dots,N$, define $\varphi_{i}\colon\mathbb{R}\to\mathbb{R}$ by

$\varphi_{i}(t)=\begin{cases}\begin{array}[]{ll}0&\text{for
}t\in(-\infty,(i-1)\tfrac{T}{N}]\;,\\\ t-(i-1)\tfrac{T}{N}&\text{for
}t\in[(i-1)\tfrac{T}{N},i\tfrac{T}{N}]\;,\\\ \tfrac{T}{N}&\text{for
}t\in[i\tfrac{T}{N},\infty)\;.\end{array}\end{cases}$

Then, for $i=1,\dots,N$, the function $\varphi_{i}-\varphi_{i-1}$ vanishes at
$-\tfrac{T}{N}$ and $T$, hence it can be approximated arbitrarily well by
functions in ${\cal C}^{\infty}_{c}((-\infty,T))$ with respect to the
$||\cdot||_{\infty}$\- and the $||\cdot||_{H^{1}}$-norm. Thus

$\int_{-\infty}^{T}(\varphi_{i}^{\prime}(t)-\varphi_{i-1}^{\prime}(t))u(t)\,\textnormal{d}t\geq
0$

since $\varphi_{i}-\varphi_{i-1}\leq 0$ and $Du\geq 0$ by assumption. This
implies

$(u_{N})_{i}=\tfrac{N}{T}\int_{-\infty}^{T}\varphi^{\prime}_{i}(t)u(t)\,\textnormal{d}t\geq\tfrac{N}{T}\int_{-\infty}^{N}\varphi^{\prime}_{i-1}(t)u(t)\,\textnormal{d}t$

and the latter integral is $(u_{N})_{i-1}$ for $i=2,\dots,N$ and zero for
$i=1$. ∎

##  3 Extended Formulations

Our aim is to devise extended formulations for binary switching constraints on
a continuous time horizon $[0,T]$. More precisely, we investigate specific
subsets $D\subseteq BV_{0}(0,T;\\{0,1\\})$ that are bounded in
$BV_{0}(0,T;\\{0,1\\})$, meaning that there exists a uniform bound
$\sigma\in\mathbb{Q}_{+}$ such that $|u|_{BV(-\infty,T)}\leq\sigma$ for all
$u\in D$. Using the lower semicontinuity of $|\cdot|_{BV(-\infty,T)}$, one can
show that this assumption guarantees that $\overline{\operatorname{conv}}(D)$
is still contained in $BV_{0}(0,T)$. Here and in the following, all closures
are taken in $L^{2}_{0}(0,T)$.

######  Definition 3.1.

An _extended formulation_ of $D\subseteq BV_{0}(0,T)$ is a set
$D^{\textnormal{ext}}\subseteq L^{2}_{0}(0,T)^{d+1}$ satisfying the following
conditions:

  * (e1)

The projection of $D^{\textnormal{ext}}$ to the first coordinate agrees with
$\overline{\operatorname{conv}}(D)$.

  * (e2)

The formulation is _linear_ , i.e., the elements $(u,z_{1},\dots,z_{d})\in
D^{\textnormal{ext}}$ can be characterized by finitely many constraints, each
of which is either of the form

$L(u,z_{1},\dots,z_{d})\geq 0\text{ a.e.\ in\ }(0,T)$

or of the form

$DL(u,z_{1},\dots,z_{d})\geq 0$

for a continuous affine-linear operator $L\colon L^{2}_{0}(0,T)^{d+1}\to
L^{2}_{0}(0,T)$.

The extended formulation is called _compact_ if the number of controls $d+1$
as well as the number of constraints describing $D^{\textnormal{ext}}$
according to (e2) are polynomial in the input size.

Polynomiality in the input size is a very common requirement in combinatorial
optimization. Nonetheless, in the infinite-dimensional setting, it calls for
some clarification. Obviously, the concept is only well-defined when the sets
$D$ under consideration belong to a class that can be finitely parametrized,
i.e., an individual instance $D$ from the class is fully determined by a
finite input. To emphasize this, all input parameters except for $T$ will be
part of the notation for all problem classes investigated in the subsequent
sections.

The term “compact” in Definition 3.1 is quite ambiguous, since it could also
refer to the compactness of the set $D^{\textnormal{ext}}$ in the Banach space
$L^{2}_{0}(0,T)^{d+1}$. However, in finite-dimensional optimization,
especially in the context of extended formulations, it is a common term for
polynomial-size formulations, so that we decided to keep this notation.
Throughout this paper, the term “compact” will only be used in the sense of
Definition 3.1.

The next result shows that every extended formulation is closed in
$L^{2}_{0}(0,T)^{d+1}$. Moreover, the projection in Definition 3.1 is always
closed if the extended formulation is bounded.

######  Lemma 3.2.

Every extended formulation $D^{\textnormal{ext}}$ is convex and closed in
$L^{2}_{0}(0,T)^{d+1}$. Moreover, if $D^{\textnormal{ext}}$ is bounded in
$L^{2}_{0}(0,T)^{d+1}$, then the projection of $D^{\textnormal{ext}}$ to the
first coordinate is convex and closed in $L^{2}_{0}(0,T)$.

###### Proof.

Clearly, all constraints described in Condition (e2) of Definition 3.1 are
convex. To show closedness, let $L\colon L^{2}_{0}(0,T)^{d+1}\to
L^{2}_{0}(0,T)$ be any continuous and affine-linear operator. Then constraints
of type $L(u,z_{1},\dots,z_{d})\geq 0$ are obviously closed, while constraints
of type $DL(u,z_{1},\dots,z_{d})\geq 0$ are closed by Lemma 2.1.

Now assume that $D^{\textnormal{ext}}$ is bounded in $L^{2}_{0}(0,T)^{d+1}$
and let $D^{\prime}$ be the projection of $D^{\textnormal{ext}}$ to the first
coordinate. Then clearly $D^{\prime}$ is convex. To show closedness, let
$u_{n}$ be a sequence in $D^{\prime}$ that strongly converges to some $u\in
L^{2}_{0}(0,T)$. For $n\in\mathbb{N}$, choose
$(z_{1})_{n},\dots,(z_{d})_{n}\in L^{2}_{0}(0,T)$ with
$(u_{n},(z_{1})_{n},\dots,(z_{d})_{n})\in D^{\textnormal{ext}}$. Since
$D^{\textnormal{ext}}$ is bounded and closed in $L^{2}_{0}(0,T)^{d+1}$ and
since $L^{2}_{0}(0,T)$ is a reflexive Banach space, there exists a subsequence
of $(u_{n},(z_{1})_{n},\dots,(z_{d})_{n})$ converging weakly to some
$(u^{\prime},z_{1},\dots,z_{d})\in D^{\textnormal{ext}}$. But $u_{n}\to u$,
hence we must have $u^{\prime}=u$, so that $u$ belongs to $D^{\prime}$. ∎

In finite dimension, the main relevance of compact extended formulations stems
from the fact that they provide efficient and elegant approaches to solving
combinatorial optimization problems, by reformulating them as polynomial-size
linear programs. In order to derive a similar result in function space, it is
necessary that the extended formulations carry over to the discretization of
the problem. This is formalized in the following definition.

######  Definition 3.3.

An extended formulation $D^{\textnormal{ext}}$ of $D$ is _compatible with
discretization_ if for all $N\in\mathbb{N}$ the following conditions hold:

  * (c1)

the projection of $(D^{\textnormal{ext}})_{N}$ to the first coordinate agrees
with $\operatorname{conv}(D_{N})$,

  * (c2)

the affine-linear operators $L$ defining $D^{\textnormal{ext}}$ map
$L^{2}_{0}(0,T)^{d+1}_{N}$ to $L^{2}_{0}(0,T)_{N}$, and

  * (c3)

the coefficients of the resulting affine-linear functions
$L_{N}\colon\mathbb{R}^{(d+1)N}\to\mathbb{R}^{N}$ can be computed in
polynomial time.

Using this definition, we now have

######  Theorem 3.4.

Assume that $D$ admits a compact extended formulation $D^{\textnormal{ext}}$
that is compatible with discretization. Then, for fixed $N\in\mathbb{N}$, the
discretization $D_{N}$ of $D$ is tractable, i.e., for any $c\in
L^{2}_{0}(0,T)$ given by its piecewise averages $c_{N}$, the linear objective
function

(3.1) $\int_{0}^{T}c(t)u(t)\,\textnormal{d}t$

can be minimized over $u\in D_{N}$ in polynomial time.

###### Proof.

Given $(u,z_{1},\dots,z_{d})\in L^{2}_{0}(0,T)_{N}$, we have
$(u,z_{1},\dots,z_{d})\in(D^{\textnormal{ext}})_{N}$ if and only if the
constraints in Condition (e2) of Definition 3.1 are satisfied by
$(u,z_{1},\dots,z_{n})$. By Condition (c1), minimizing (3.1) over $u\in D_{N}$
or, equivalently, over $u\in\operatorname{conv}(D_{N})$, thus reduces to
minimizing the same linear function over
$(u,z_{1},\dots,z_{d})\in(D^{\textnormal{ext}})_{N}$. Identifying elements of
$L^{2}_{0}(0,T)_{N}$ with vectors in $\mathbb{R}^{N}$, the latter in turn
reduces to the minimization of $c_{N}^{\top}u$ subject to constraints of type
$L(\overline{u},\overline{z_{1}},\dots,\overline{z_{d}})\geq 0$ and
$DL(\overline{u},\overline{z_{1}},\dots,\overline{z_{d}})\geq 0$, where the
variables are $u,z_{1},\dots,z_{d}\in\mathbb{R}^{N}$. By the compactness of
the extended formulation and by (c2), the latter constraints translate to
polynomially many affine-linear constraints in $(u,z_{1},\dots,z_{d})$, the
coefficients of which can be computed efficiently by Condition (c3). In
summary, the minimization problem reduces to the solution of a polynomial-size
linear program in dimension $(d+1)N$. ∎

Note that the running time for minimization over $D_{N}$ obtained in the above
proof is only pseudopolynomial in $N$, as $N$ enters the dimension of the
resulting linear program.

Formally, the set $(D^{\textnormal{ext}})_{N}$ is _not_ an extended
formulation of $D_{N}$ when interpreting elements of $D_{N}$ and
$(D^{\textnormal{ext}})_{N}$ as piecewise constant functions rather than
finite-dimensional vectors, as in Definition 2.2. Indeed, the linear
description derived from $D^{\textnormal{ext}}$ does not guarantee that the
functions are piecewise constant, i.e., it does not completely describe
$(D^{\textnormal{ext}})_{N}$.

Theorem 3.4 states that compact and compatible extended formulations
immediately lead to tractable discretizations, independent of the chosen
number $N$ of grid cells. However, depending on the context, it may be enough
from a practical point of view to obtain a tractable discretization after a
suitable refinement of the grid. As we will see in the following, it may well
happen that a discretization turns tractable only after increasing the number
of grid cells. For this reason, we also consider the following weaker
condition:

######  Definition 3.5.

An extended formulation $D^{\textnormal{ext}}$ of $D$ is _weakly compatible
with discretization_ if for all $M\in\mathbb{N}$ one can efficiently compute
some $\ell\in\mathbb{N}$ which is polynomial in $M$ such that Conditions (c1)
to (c3) of Definition 3.3 hold for $N=\ell M$.

To clarify the polynomiality condition in this definition, it is required that
$\ell$ can be computed in polynomial time from the input of the problem, i.e.,
the input defining the instance $D$ within the given class of feasible sets,
and from $M$. Moreover, the value of $\ell$ must be polynomial in the value of
$M$. This is crucial since the dimension of the linear programs resulting from
discretization is linear in the number of grid cells. For a fixed problem
input, the size of the linear program thus increases only polynomially by the
refinement.

If $D$ admits a compact and weakly compatible extended formulation, it follows
directly from Theorem 3.4 that for any $M\in\mathbb{N}$ one can efficiently
compute some $\ell\in\mathbb{N}$ polynomial in $M$ such that $D_{\ell M}$ is
tractable. It depends on the given setting which of the two concepts of
compatibility is appropriate: if the discretization can be arbitrarily refined
by the user, a weakly compatible extended formulation is enough to obtain
tractable discretizations.

##  4 Fixed Bound on the Variation

Our first goal is to devise an extended formulation for the case where a fixed
bound on the variation is the only restriction on the set of feasible
controls; this case has been investigated in [13, 14, 5]. We thus consider the
set

$D(\sigma):=\\{u\in
BV_{0}(0,T;\\{0,1\\})\colon|u|_{BV(-\infty,T)}\leq\sigma\\}$

for given $\sigma\in\mathbb{N}$. A natural convex relaxation of $D(\sigma)$
arises from omitting the binarity constraint on the control, we then obtain

$D(\sigma)^{\textnormal{rel}}:=\big{\\{}u\in
BV_{0}(0,T;[0,1])\colon\;|u|_{BV(-\infty,T)}\leq\sigma\big{\\}}\;.$

Note that the set $D(\sigma)^{\textnormal{rel}}$ is convex and, by the lower
semicontinuity of $|\cdot|_{BV(0,T)}$ and the boundedness of
$D(\sigma)^{\textnormal{rel}}$ in $BV(0,T)$, also closed in $L^{2}_{0}(0,T)$.
We now show that $D(\sigma)^{\textnormal{rel}}$ can be obtained as the
projection of a very compact extended formulation, where a single additional
function $z$ keeps track of the accumulated variation of $u$.

######  Theorem 4.1.

The set

$D(\sigma)^{\textnormal{rel,ext}}:=\big{\\{}u\in
L^{2}_{0}(0,T;[0,1]),\leavevmode\nobreak\ z\in L^{2}_{0}(0,T;[0,\sigma])\colon
Dz\geq Du,\leavevmode\nobreak\ Dz\geq-Du\big{\\}}$

is a compact extended formulation of $D(\sigma)^{\textnormal{rel}}$ which is
compatible with discretization.

###### Proof.

In the format of Definition 3.1, the constraints in the above formulation
explicitly read $u\geq 0$, $-u+\boldsymbol{1}\geq 0$, $z\geq 0$,
$-z+\boldsymbol{\sigma}\geq 0$, $D(z-u)\geq 0$, and $D(z+u)\geq 0$, where
$\boldsymbol{1}$ and $\boldsymbol{\sigma}$ denote the functions being
constantly $1$ and $\sigma$, respectively. Condition (e2) of Definition 3.1 as
well as compactness are thus obvious, so it suffices to show Condition (e1)
and compatibility with discretization.

We first show Condition (e1). Given $(u,z)\in
D(\sigma)^{\textnormal{rel,ext}}$, we observe that $z$ is essentially bounded
by $\sigma$ and monotonously increasing by $Dz\geq 0$. Thus $z\in
BV_{0}(0,T)$, such that $Dz$ is a regular Borel measure satisfying
$Dz((-\infty,T))\leq\sigma$. Now for every $\varphi\in{\cal
C}^{\infty}_{c}((-\infty,T))$, we have $\varphi_{+},\varphi_{-}\in
H^{1}(-\infty,T)$ for $\varphi_{+}:=\max\\{\varphi,0\\}$ and
$\varphi_{-}:=-\min\\{\varphi,0\\}$, and the weak derivatives satisfy
$\varphi^{\prime}=\varphi_{+}^{\prime}-\varphi_{-}^{\prime}$. From $Dz\geq Du$
and $Dz\geq-Du$ we derive

$\displaystyle\int_{-\infty}^{T}\varphi^{\prime}(t)u(t)\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle-\int_{-\infty}^{T}\varphi_{+}^{\prime}(t)(-u(t))\,\textnormal{d}t-\int_{-\infty}^{T}\varphi_{-}^{\prime}(t)u(t)\,\textnormal{d}t$
$\displaystyle\leq$
$\displaystyle-\int_{-\infty}^{T}\varphi_{+}^{\prime}(t)z(t)\,\textnormal{d}t-\int_{-\infty}^{T}\varphi_{-}^{\prime}(t)z(t))\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{T}\varphi_{+}\,\textnormal{d}Dz+\int_{-\infty}^{T}\varphi_{-}\,\textnormal{d}Dz$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{T}|\varphi|\,\textnormal{d}Dz\leavevmode\nobreak\
\leq\leavevmode\nobreak\ ||\varphi||_{\infty}\,\sigma\;.$

Since $\varphi$ was arbitrary, this implies $u\in BV_{0}(0,T)$ with
$|u|_{BV(-\infty,T)}\leq\sigma$, thus $u\in D(\sigma)^{\textnormal{rel}}$. For
the other direction, let $u\in D(\sigma)^{\textnormal{rel}}$ and define $z\in
L^{2}_{0}(0,T)$ by $z(t):=|Du|\big{(}(-\infty,t)\big{)}$ for $t\in[0,T]$. Then
clearly $(u,z)\in D(\sigma)^{\textnormal{rel,ext}}$ and hence $u$ belongs to
the projection of $D(\sigma)^{\textnormal{rel,ext}}$ to the first coordinate.

Moreover, the latter construction yields $z\in L^{2}_{0}(0,T)_{N}$ whenever
$u\in BV_{0}(0,T)_{N}$, showing that $(D(\sigma)^{\textnormal{rel}})_{N}$
belongs to the projection of $(D(\sigma)^{\textnormal{rel,ext}})_{N}$. Since
the reverse inclusion follows from the reasoning above, we obtain that
Condition (c1) of Definition 3.3 holds, while Conditions (c2) and (c3) are
obviously satisfied: given $N\in\mathbb{N}$, the discretized constraints read
$u_{i}\in[0,1]$, $z_{i}\in[0,\sigma]$, $z_{i}-z_{i-1}\geq u_{i}-u_{i-1}$, and
$z_{i}-z_{i-1}\geq u_{i-1}-u_{i}$ for $i=1,\dots,N$. ∎

By Theorem 4.1, the projection of $D(\sigma)^{\textnormal{rel,ext}}$ to the
first coordinate yields a relaxation for the set $D(\sigma)$. However, it can
be shown that $\overline{\operatorname{conv}}(D(\sigma))$ is _strictly_
contained in $D(\sigma)^{\textnormal{rel}}$ in general; see [5, Counterexample
3.1]. In other words, the formulation in Theorem 4.1 is _not_ an extended
formulation for $D(\sigma)$ in general. Our next goal is thus to devise an
extended formulation that instead projects to
$\overline{\operatorname{conv}}(D(\sigma))$.

We construct such a formulation by first considering the discretized problem,
for which an extended formulation has been presented in [8, Section 4.5]:
assuming that $\sigma$ is even, the projection of

$\displaystyle(D(\sigma)_{N})^{\textnormal{ext}}:=\big{\\{}$ $\displaystyle
u\in[0,1]^{N},\leavevmode\nobreak\ z\in\mathbb{R}^{N}\colon$ $\displaystyle
u_{i}-u_{i-1}\leq z_{i}-z_{i-1}\quad\text{for }i=1,\dots,N,$ $\displaystyle
0\leq z_{1}\leq z_{2}\leq\dots\leq z_{N}\leq\tfrac{\sigma}{2}\big{\\}}$

to the $u$-space coincides with $\operatorname{conv}(D(\sigma)_{N})$, where
again we identify piecewise constant functions with finite-dimensional
vectors. This follows from [8, Lemma 4.29] using the substitution
$z_{i}\leftarrow\sum_{j=1}^{i}z_{j}$. In this model, we define
$z_{0}=u_{0}=0$, but do not eliminate these variables for sake of a simpler
formulation. The first constraint thus reduces to $u_{1}\leq z_{1}$.

We now turn our attention back to the infinite-dimensional setting and show
that $\overline{\operatorname{conv}}(D(\sigma))$ can be described by an
extended formulation that is inspired by the formulation
$(D(\sigma)_{N})^{\textnormal{ext}}$. For this, define

$D(\sigma)^{\textnormal{ext}}:=\big{\\{}u\in
L^{2}_{0}(0,T;[0,1]),\leavevmode\nobreak\ z\in
L^{2}_{0}(0,T;[0,\tfrac{\sigma}{2}])\colon Dz\geq Du,\leavevmode\nobreak\
Dz\geq 0\big{\\}}\;.$

For an illustration of this construction, see Figure 2. Using this, we now
obtain an extended formulation of $D(\sigma)$.

$0$$1$$T$$u$

$0$$3$$T$$u^{+}$

Figure 2: Illustration of the extended formulation
$D(\sigma)^{\textnormal{ext}}$ for $\sigma=6$. A feasible control $u$ is shown
on the left hand side, the control $z:=u^{+}$ is added on the right hand side.

######  Theorem 4.2.

Let $\sigma$ be even. Then $D(\sigma)^{\textnormal{ext}}$ is a compact
extended formulation of $D(\sigma)$ which is compatible with discretization.

###### Proof.

Again, Condition (e2) of Definition 3.1 and compactness are easily verified,
so it suffices to show Condition (e1) as well as compatibility. First assume
that $(u,z)\in D(\sigma)^{\textnormal{ext}}$. By Lemma 2.4, we then have
$({u}_{[N]},{z}_{[N]})\to(u,z)$ for $N\to\infty$. By construction, it follows
that $u_{N}\in[0,1]^{N}$ and $z_{N}\in[0,\tfrac{\sigma}{2}]^{N}$ for all
$N\in\mathbb{N}$. Moreover, applying Lemma 2.5 to both $z$ and $z-u$ yields
$(z_{N})_{i}-(z_{N})_{i-1}\geq 0$ and
$(z_{N})_{i}-(z_{N})_{i-1}\geq(u_{N})_{i}-(u_{N})_{i-1}$. In summary, we thus
have $(u_{N},z_{N})\in(D(\sigma)_{N})^{\textnormal{ext}}$. Hence
$u_{N}\in\operatorname{conv}(D(\sigma)_{N})$ and thus
${u}_{[N]}\in\operatorname{conv}(D(\sigma))$, using the finite-dimensional
extended formulation. This shows
$u\in\overline{\operatorname{conv}}(D(\sigma))$.

Now let $u\in\overline{\operatorname{conv}}(D(\sigma))$. For showing that $u$
belongs to the projection of $D(\sigma)^{\textnormal{ext}}$ to the first
coordinate, we may assume $u\in D(\sigma)$ by Lemma 3.2. Define $z:=u^{+}$.
Then $z\in L^{2}_{0}(0,T)$ with $Dz\geq Du$ and $Dz\geq 0$, thus also $z\geq
0$ almost everywhere. Moreover,

$Du^{+}([0,T))+Du^{-}([0,T))\leq|u|_{BV(-\infty,T)}\leq\sigma$

and, since $u\leq 1$ almost everywhere, we have

$Du^{+}([0,T))-Du^{-}([0,T))=Du([0,T))\leq 1\;.$

Summing up, we derive $Dz([0,T))=Du^{+}([0,T))\leq\tfrac{\sigma+1}{2}$. Since
$Dz([0,T))$ is integer and $\sigma$ is even, this implies
$Dz([0,T))\leq\tfrac{\sigma}{2}$ and hence $z\leq\tfrac{\sigma}{2}$ almost
everywhere.

Finally, Condition (c1) of Definition 3.3 follows directly from the fact that
$(D(\sigma)^{\textnormal{ext}})_{N}$ corresponds to the finite-dimensional
extended formulation $(D(\sigma)_{N})^{\textnormal{ext}}$ of $D(\sigma)_{N}$,
while (c2) and (c3) are again obvious. ∎

The preceding proof is a blueprint for similar results on extended
formulations in function space, provided that an extended formulation for the
discretized problem is known. The compatibility with discretization follows
easily in this situation. The first inclusion of (e1) is shown by
approximating an element of the supposed extended formulation by piecewise
constant functions according to Lemma 2.4 and then using the finite-
dimensional result, while for the other inclusion an explicit construction of
$z_{1},\dots,z_{d}$ from $u$ is proposed.

Note that the exact extended formulation $D(\sigma)^{\textnormal{ext}}$ of
$D(\sigma)$ is defined by the same number of constraints as the extended
formulation $D(\sigma)^{\textnormal{ext,rel}}$ of the relaxation
$D(\sigma)^{\textnormal{rel}}$. The difference between the two formulations is
that the exact formulation only counts the positive variation and bounds it by
$\tfrac{\sigma}{2}$, while the relaxed formulation bounds the total variation
by $\sigma$.

In the case of odd $\sigma$, one can use [8, Lemma 4.30] to show that an
extended formulation of $D(\sigma)$ is given by

$D(\sigma)^{\textnormal{ext}}:=\big{\\{}u\in
L^{2}_{0}(0,T;[0,1]),\leavevmode\nobreak\ z\in
L^{2}_{0}(0,T;[0,\tfrac{\sigma-1}{2}])\colon Dz\geq-Du,\leavevmode\nobreak\
Dz\geq 0\big{\\}}\;.$

The proof is very similar to the proof of Theorem 4.2. Instead of bounding the
positive variation by $\tfrac{\sigma}{2}$, as in the case of even $\sigma$, we
now bound the negative variation by $\tfrac{\sigma-1}{2}$.

##  5 Minimum Dwell-time Constraints

We next consider the important class of minimum dwell-time constraints, which
are also called min-up/min-down constraints in the literature; see [11, 12, 3]
for the finite-dimensional and [15] for the infinite-dimensional case. Given
$L,l\in\mathbb{Q}_{+}$ with $L+l>0$ as input, the feasible set $D(L,l)$ now
consists of all $u\in BV_{0}(0,T;\\{0,1\\})$ such that, when switching up $u$
at time $\tau$, no switching down occurs in $[\tau,\tau+L)$, and analogously,
when switching down $u$ at $\tau$, no switching up occurs in $[\tau,\tau+l)$.
Rajan and Takriti [12] have devised the following extended formulation for
$D(L,l)_{N}$, where we have applied the same substitution of $z$-variables as
in the previous section:

$\displaystyle(D(L,l)_{N})^{\textnormal{ext}}:=\big{\\{}$ $\displaystyle
u\in[0,1]^{N},\leavevmode\nobreak\ z\in\mathbb{R}_{+}^{N}\colon$
$\displaystyle z_{i}-z_{i-L}\leq u_{i}$ $\displaystyle\text{for
}i=L+1,\dots,N,$ $\displaystyle z_{i}-z_{i-l}\leq 1-u_{i-l}$
$\displaystyle\text{for }i=l+1,\dots,N,$ $\displaystyle z_{i}-z_{i-1}\geq
u_{i}-u_{i-1}$ $\displaystyle\text{for }i=1,\dots,N,$ $\displaystyle
z_{i}-z_{i-1}\geq 0$ $\displaystyle\text{for }i=1,\dots,N\big{\\}}\;.$

Here $z_{0}$ and $u_{0}$ are again defined as zero. In order to obtain an
extended formulation for the infinite-dimensional set
$\overline{\operatorname{conv}}(D(L,l))$, we first define a continuous linear
map

$V_{r}\colon L^{2}_{0}(0,T)\to L^{2}_{0}(0,T)$

for given $r\in\mathbb{R}_{+}$ by $V_{r}(z)(t)=z(t-r)$, i.e., $V_{r}$ shifts
$z$ to the right by $r$. Note that, by the definition of $L^{2}_{0}(0,T)$,
this implies $V_{r}(z)=0$ a.e. in $(-\infty,r)$. Now consider the following
formulation, inspired by the extended formulation of Rajan and Takriti:

$\displaystyle D(L,l)^{\textnormal{ext}}:=\big{\\{}$ $\displaystyle u\in
L^{2}_{0}(0,T;[0,1]),\leavevmode\nobreak\ z\in
L^{2}_{0}(0,T;[0,\sigma])\colon$ (5.1a) $\displaystyle z-V_{L}(z)\leq u,$
(5.1b) $\displaystyle z-V_{l}(z)\leq{\bf 1}-V_{l}(u),$ (5.1c) $\displaystyle
Dz\geq Du,\leavevmode\nobreak\ Dz\geq 0\big{\\}}\;.$

Here we define $\sigma:=\lceil\nicefrac{{2T}}{{L+l}}\rceil$. This value of
$\sigma$ is large enough to make the upper bound on $z$ redundant, it is only
used to ensure that $D(L,l)^{\textnormal{ext}}$ is bounded in
$L^{2}_{0}(0,T)^{2}$.

######  Theorem 5.1.

The set $D(L,l)^{\textnormal{ext}}$ is a compact extended formulation of
$D(L,l)$ which is weakly compatible with discretization.

###### Proof.

Again, Condition (e2) of Definition 3.1 as well as compactness are easily
verified, so it suffices to show Condition (e1) and weak compatibility. So let
$(u,z)\in D(L,l)^{\textnormal{ext}}$. We again have

$({u}_{[N]},{z}_{[N]})\to(u,z)\text{ for }N\to\infty$

by Lemma 2.4. Now choose $\ell\in\mathbb{N}$ such that $\nicefrac{{\ell
L}}{{T}}$ and $\nicefrac{{\ell l}}{{T}}$ are both integer and consider the
subsequence given by indices $N_{k}:=k\ell$, $k\in\mathbb{N}$. We claim that

(5.2)
$(u_{N_{k}},z_{N_{k}})\in(D(\nicefrac{{N_{k}L}}{{T}},\nicefrac{{N_{k}l}}{{T}})_{N_{k}})^{\textnormal{ext}}\leavevmode\nobreak\
\text{ for all }k\in\mathbb{N}\;.$

First note that $u_{N_{k}}\in[0,1]^{N_{k}}$ and
$z_{N_{k}}\in\mathbb{R}_{+}^{N_{k}}$ by construction. Moreover, Lemma 2.5
again yields
$(z_{N_{k}})_{i}-(z_{N_{k}})_{i-1}\geq(u_{N_{k}})_{i}-(u_{N_{k}})_{i-1}$ and
$(z_{N_{k}})_{i}-(z_{N_{k}})_{i-1}\geq 0$ using (5.1c). Finally,

$\displaystyle(z_{N_{k}})_{i}-(z_{N_{k}})_{i-\nicefrac{{N_{k}L}}{{T}}}$
$\displaystyle=$
$\displaystyle\tfrac{N_{k}}{T}\int_{(i-1)\frac{T}{N_{k}}}^{i\frac{T}{N_{k}}}z(t)\,\textnormal{d}t-\tfrac{N_{k}}{T}\int_{(i-\nicefrac{{N_{k}L}}{{T}}-1)\frac{T}{N_{k}}}^{(i-\nicefrac{{N_{k}L}}{{T}})\frac{T}{N_{k}}}z(t)\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\tfrac{N_{k}}{T}\int_{(i-1)\frac{T}{N_{k}}}^{i\frac{T}{N_{k}}}z(t)\,\textnormal{d}t-\tfrac{N_{k}}{T}\int_{(i-1)\frac{T}{N_{k}}}^{i\frac{T}{N_{k}}}V_{L}(z)(t)\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\tfrac{N_{k}}{T}\int_{(i-1)\frac{T}{N_{k}}}^{i\frac{T}{N_{k}}}\big{(}z(t)-V_{L}(z)(t)\big{)}\,\textnormal{d}t$
$\displaystyle\underset{\eqref{eq:v1}}{\leq}$
$\displaystyle\tfrac{N_{k}}{T}\int_{(i-1)\frac{T}{N_{k}}}^{i\frac{T}{N_{k}}}u(t)\,\textnormal{d}t=(u_{N_{k}})_{i}\;,$

and the remaining constraint can be shown analogously using (5.1b). This
concludes the proof of (5.2). The result of Rajan and Takriti now shows
$u_{N_{k}}\in\operatorname{conv}(D(\nicefrac{{N_{k}L}}{{T}},\nicefrac{{N_{k}l}}{{T}})_{N_{k}})$
for all $k\in\mathbb{N}$, yielding
${u}_{[N_{k}]}\in\operatorname{conv}(D(L,l))$, which implies
$u\in\overline{\operatorname{conv}}(D(L,l))$.

For showing the other inclusion, we may assume $u\in D(L,l)$ by Lemma 3.2.
Define $z:=u^{+}$. Then we have $Dz\geq Du$ and $Dz\geq 0$. Moreover, the
linear inequality (5.1a) follows from the definition of $D(L,l)$ then. Indeed,
we obtain $z-V_{L}(z)=u^{+}-V_{L}(u^{+})\in\\{0,1\\}$ a.e. from the definition
of $D(L,l)$, since $u$ can switch up at most once in any time interval of
length $L$. If $u^{+}-V_{L}(u^{+})=1$ a.e. in some interval
$(\tau_{1},\tau_{2})$, we derive that $Du^{+}(\\{\tau\\})=1$ for some
$\tau\in(\tau_{2}-L,\tau_{1})$. From the definition of $D(L,l)$, we obtain
$u=1$ a.e. in $(\tau_{1},\tau_{2})$, showing (5.1a). The constraint (5.1b)
follows by a similar reasoning. Thus $(u,z)$ satisfies all conditions of
$D(L,l)^{\textnormal{ext}}$, which shows that $u$ belongs to the projection of
$D(L,l)^{\textnormal{ext}}$ to the first coordinate.

From the proof so far, it follows that the extended formulation
$D(L,l)^{\textnormal{ext}}$ is compatible with discretization provided that
$N$ is a multiple of $\ell$. A feasible value for $\ell$ can be computed
efficiently from the rational numbers $L$, $l$, and $T$, e.g., by multiplying
the numerator of $T$ with the denominators of $L$ and $l$. We thus obtain that
the extended formulation is weakly compatible with discretization. ∎

As seen in the proof of Theorem 5.1, the refinement factor $\ell$ required to
obtain a compatible discretization does not depend on $N$, but on the input
consisting of $L$, $\l$, and $T$. Even when fixing $N$, the number of
necessary grid cells thus grows by a factor that is polynomial in these
numbers. In terms of $L$, $\l$, and $T$, we thus only obtain a
pseudopolynomial algorithm for solving the refined discretizations. However,
at least for the extended formulation $D(L,l)^{\textnormal{ext}}$ considered
here, this is unavoidable, since even Condition (c2) of Definition 3.3 is not
satisfied unless $\nicefrac{{T}}{{N}}$ is an integer multiple of $L$ and $l$.

##  6 Linear Switching Point Constraints

The minimum dwell-time constraints considered in the previous section form a
special case of linear switching point constraints. Since we assume $D$ to be
bounded in $BV_{0}(0,T;\\{0,1\\})$, each function $u\in D$ is defined by its
finitely many switching points $t_{1},\dots,t_{\sigma}$, i.e., the points
where the value of $u$ changes; see [5, Section 3.2] for a formal definition.
We assume again that $u$ starts being switched off and consider the set
$D(A,b)\subseteq BV_{0}(0,T;\\{0,1\\})$ consisting of all functions $u$ such
that its switching points satisfy given linear inequalities $At\leq b$ for
$A\in\mathbb{Q}^{m\times\sigma}$ and $b\in\mathbb{Q}^{m}$. More precisely,
taking into account that functions in $L^{2}_{0}(0,T)$ are only defined up to
null sets, we let $u$ belong to $D(A,b)$ if any only if there exists any
representative of $u$ with switching points $t_{1},\dots,t_{\sigma}$
satisfying $At\leq b$.

For simplicity, we assume that the constraints $At\leq b$ imply $0\leq
t_{1}\leq\dots\leq t_{\sigma}\leq T$, so that $u$ switches up at $t_{i}$ for
odd $i$ and down for even $i$. However, we do not require that any of the
inequalities $0\leq t_{1}\leq\dots\leq t_{\sigma}\leq T$ be strict. It is thus
allowed to switch up immediately at zero, to switch multiple times at the same
time point (so that the switchings neutralize each other), or to leave some of
the switchings to time point $T$ (so that they become irrelevant). In
particular, while the switching points uniquely determine $u\in
BV_{0}(0,T;\\{0,1\\})$, the vector of switching points belonging to some given
$u\in BV_{0}(0,T;\\{0,1\\})$ may not be unique.

###  6.1 Linearization

Different from the cases considered in the previous sections, there is no
obvious linear formulation of $D(A,b)$ in the original space, due to the non-
linear connection between the values of the function $u$ and the switching
points of $u$. The following model describing $D(A,b)$ by the use of
additional controls can thus be seen as a linearization of $D(A,b)$:

$\displaystyle D(A,b)^{\textnormal{lin}}:=\Big{\\{}$ $\displaystyle u\in
L^{2}_{0}(0,T;\\{0,1\\}),\leavevmode\nobreak\ z^{(1)},\dots,z^{(\sigma)}\in
L^{2}_{0}(0,T;[0,1])\colon$ (6.1a) $\displaystyle Dz^{(i)}\geq
0\,\quad\quad\text{ for all }i=1,\dots,\sigma,$ (6.1b) $\displaystyle
z^{(i)}\leq z^{(i-1)}\quad\text{ for all }i=2,\dots,\sigma,$ (6.1c)
$\displaystyle u=\sum_{i=1}^{\sigma}(-1)^{i+1}z^{(i)},$ (6.1d)
$\displaystyle\sum_{i=1}^{\sigma}a_{ji}\int_{0}^{T}(1-z^{(i)}(t))\,\textnormal{d}t\leq
b_{j}\text{ for all }j=1,\dots,m\Big{\\}}\;.$

Note that the constraints (6.1d) fit into the framework of Condition (e2) of
Definition 3.1 by considering the left and right hand side as constant
functions. However, this formulation contains binarity constraints on $u$.
Still, we can show

######  Theorem 6.1.

The projection of $D(A,b)^{\textnormal{lin}}$ to the first coordinate agrees
with $D(A,b)$.

###### Proof.

Given $u\in D(A,b)$, let $t_{1},\dots,t_{\sigma}$ be a vector of switching
points of $u$ satisfying $At\leq b$. Define $z^{(i)}:=\chi_{(t_{i},T)}$ for
all $i=1,\dots,\sigma$. Then $z^{(1)},\dots,z^{(\sigma)}\in BV_{0}(0,T;[0,1])$
and (6.1a), (6.1b), as well as (6.1c) are obviously satisfied. Moreover, we
obtain

$\textstyle\int_{0}^{T}(1-z^{(i)}(t))\,\textnormal{d}t=t_{i}$

for all $i=1,\dots,\sigma$ by construction, so that (6.1d) reduces to $At\leq
b$. In summary, we thus have $(u,z^{(1)},\dots,z^{(\sigma)})\in
D(A,b)^{\textnormal{lin}}$.

For showing the other direction, assume that
$(u,z^{(1)},\dots,z^{(\sigma)})\in D(A,b)^{\textnormal{lin}}$. First note that
constraint (6.1a), together with $z^{(i)}\in[0,1]$ a.e. in $(-\infty,T)$,
implies $|z^{(i)}|_{BV(-\infty,T)}\leq 1$, so that
$|u|_{BV(-\infty,T)}\leq\sigma$ by (6.1c). From the binarity of $u$, it
follows that $u$ has finitely many switching points $0\leq
t_{1}<\dots<t_{r}<T$ with $r\leq\sigma$. Define $t_{i}:=T$ for
$i=r+1,\dots,\sigma$. It remains to show that $At\leq b$.

For this, we first show by induction that $z^{(i)}=0$ a.e. in
$(-\infty,t_{i})$ for $i=\sigma,\dots,1$. If $i$ is even, we have $z^{(j)}=0$
a.e. in $(t_{i-1},t_{i})$ for $j=i+1,\dots,\sigma$ by the induction
hypothesis. So from (6.1c) and (6.1b) we obtain

$1=u=\underbrace{z^{(1)}}_{\leq 1}\underbrace{-z^{(2)}+z^{(3)}}_{\leq
0}-\dots-\underbrace{z^{(i-2)}+z^{(i-1)}}_{\leq 0}-z^{(i)}\leq 1-z^{(i)}\text{
a.e.\ in\ }(t_{i-1},t_{i})$

and hence $z^{(i)}=0$ a.e. in $(t_{i-1},t_{i})$. Using (6.1a), this implies
$z^{(i)}=0$ a.e. in $(-\infty,t_{i})$. Now let $i$ be odd. Then

$0=u=\underbrace{z^{(1)}-z^{(2)}}_{\geq
0}+\dots+\underbrace{z^{(i-2)}-z^{(i-1)}}_{\geq 0}+z^{(i)}\geq z^{(i)}\text{
a.e.\ in\ }(t_{i-1},t_{i})$

and hence $z^{(i)}=0$ a.e. in $(t_{i-1},t_{i})$, which again implies
$z^{(i)}=0$ a.e. in $(-\infty,t_{i})$ by (6.1a).

We next show $z^{(i)}=\chi_{(t_{i},T)}$ inductively for $i=1,\dots,\sigma$.
First, let $i$ be odd. By (6.1c), we have $1=u=z^{(i)}$ a.e. in
$(t_{i},t_{i+1})$, since by the induction hypothesis $z^{(j)}=1$ for $j<i$ and
we have already shown $z^{(j)}=0$ for $j>i$. Thus $z^{(i)}=\chi_{(t_{i},T)}$.
Similarly, for even $i$ we obtain $0=u=1-z^{(i)}$ on $(t_{i},t_{i+1})$ and
hence again $z^{(i)}=1$ a.e. in $(t_{i-1},t_{i})$, showing again that
$z^{(i)}=\chi_{(t_{i},T)}$.

In summary, we have $\int_{0}^{T}(1-z^{(i)}(t))\,\textnormal{d}t=t_{i}$ for
all $i=1,\dots,\sigma$, so that (6.1d) implies $At\leq b$ and hence $u\in
D(A,b)$. ∎

A closer look at this proof reveals that the main difficulty was to derive the
binarity of the auxiliary controls $z^{(1)},\dots,z^{(\sigma)}$, yielding
$z^{(i)}=\chi_{(t_{i},T)}$. If binarity of $z^{(1)},\dots,z^{(\sigma)}$ is
required directly in the model, then the above result follows much more
easily.

In terms of Definition 3.1, the set $D(A,b)^{\textnormal{lin,rel}}$, resulting
from replacing $\\{0,1\\}$ by $[0,1]$ in $D(A,b)^{\textnormal{lin}}$,
satisfies Condition (e2). Moreover, the resulting model is compact, assuming
that $A$ and $b$ are part of the problem input, and compatible with
discretization, since each $u\in D(A,b)_{N}$ can have switching points only in
$\\{0,\tfrac{T}{N},\dots,(N-1)\tfrac{T}{N}\\}$, so that the construction in
the proof of Theorem 6.1 yields $z^{(1)},\dots,z^{(\sigma)}\in
L^{2}_{0}(0,T)_{N}$. Hence, an obvious question is whether
$D(A,b)^{\textnormal{lin,rel}}$ is an extended formulation for
$\overline{\operatorname{conv}}(D(A,b))$, i.e., also satisfies Condition (e1).
The answer to this question is negative. In fact, even for the special case of
minimum dwell-time constraints considered in the previous section, the model
(6.1) does not yield a complete description.

######  Example 6.2.

To see this, consider the minimum dwell-time instance defined by $T=4$, $L=2$,
and $l=0$, so that (6.1d) essentially reduces to
$\int_{0}^{T}(z^{(1)}(t)-z^{(2)}(t))\,\textnormal{d}t\geq 2$. Let
$u=z^{(1)}-z^{(2)}$ with $z^{(1)}=\chi_{(1,T)}$ and
$z^{(2)}=\tfrac{1}{2}\chi_{(2,T)}$. Then $(u,z^{(1)},z^{(2)})$ satisfies all
constraints in (6.1) except for the binarity of $u$, but
$u\not\in\overline{\operatorname{conv}}(D(L,l))$, since all elements of the
latter set satisfy $u(2\tfrac{1}{4})\geq u(1\tfrac{1}{4})-u(\tfrac{3}{4})$.∎

However, it is possible to model the constraints $z-V_{L}(z)\leq u$ and
$z-V_{l}(z)\leq{\bf 1}-V_{l}(u)$ of the extended formulation
$D(L,l)^{\textnormal{lin}}$ in the variable space of (6.1): using
$z=\sum_{\,i\;\textnormal{odd}\,}z^{(i)}$ and hence
$z-u=\sum_{i\;\textnormal{even}}z^{(i)}$, we obtain

$\sum_{i\;\textnormal{even}}z^{(i)}\leq\sum_{\,i\;\textnormal{odd}\,}V_{L}(z^{(i)}),\quad\sum_{\,i\;\textnormal{odd}\,}z^{(i)}\leq\mathbf{1}+\sum_{i\;\textnormal{even}}V_{l}(z^{(i)})$

as another extended formulation for the case of dwell-time constraints.

In the following section, we try to convince the reader that a compact
extended formulation which is compatible with discretization most likely does
not exist for general linear switching point constraints, even in the weak
sense of Definition 3.5.

###  6.2 Negative Results

We now show that a compact and compatible extended formulation cannot exists
for general linear switching point constraints unless P$\,=\,$NP. Using
Theorem 3.4, it suffices to show that it is NP-complete to decide whether
$D(A,b)_{N}\neq\emptyset$ for given $A$ and $b$. For all hardness proofs, we
use reductions from the following elementary decision problem:

(BPF) Given $B\in\mathbb{Q}^{m\times n}$ and $d\in\mathbb{Q}^{m}$, does there
exist some $x\in\\{0,1\\}^{n}$ with $Bx\leq d$?

It is well-known that (BPF) is NP-complete [10]. We first show

######  Theorem 6.3.

Assume that $T\in\mathbb{Q}_{+}$, $\sigma,m\in\mathbb{N}$,
$A\in\mathbb{Q}^{m\times\sigma}$, $b\in\mathbb{Q}^{m}$, and $N\in\mathbb{N}$
are part of the input. Then it is NP-complete to decide whether
$D(A,b)_{N}\neq\emptyset$.

###### Proof.

We show the statement by reduction from (BPF). For this, we set $T=n$ and
$\sigma=2n$. For all $i=1,\dots,n$, we add the switching point constraints
$t_{2i-1}=i-1$ and $i-1\leq t_{2i}\leq i$. In words, the control $u$ switches
up at 0, then down again between 0 and 1, up again at 1, and so on. So far,
all these switchings are independent. We will model the variable $x_{i}$ by
$t_{2i}-(i-1)\in[0,1]$. Substituting all $x_{i}$ in $Bx\leq d$ by these
expressions, we obtain another set of linear constraints in $t$, which we add
to the switching point constraints. This concludes the construction of $A$ and
$b$, which can obviously be done in polynomial time.

Now let $N=n$. Then all switching points of $u$ belong to $\\{0,\dots,n\\}$,
hence $t_{2i}-(i-1)\in\\{0,1\\}$ and $t_{2i}-(i-1)=u_{i}$. Thus, by
construction, the given instance of (BPF) has a feasible solution if and only
if $D(A,b)_{N}\neq\emptyset$. Clearly, the problem of deciding whether
$D(A,b)_{N}$ is non-empty belongs to NP, the certificate being an element of
$D(A,b)_{N}$. ∎

Now using Theorem 6.3 and Theorem 3.4, considering, e.g, the objective
function $c=\mathbf{0}$, we immediately obtain

######  Corollary 6.4.

A compact extended formulation of $D(A,b)$ that is compatible with
discretization does not exist unless P$\,=\,$NP.

The proof of Theorem 6.3 relies on the possibility to choose the grid size $N$
in the reduction, i.e., on the fact that $N$ is part of the input. When
keeping the same instance but considering finer grids, it is no longer true
that $u$ must be constant between $i-1$ and $i$. Indeed, assuming that $N$ is
a multiple of $T$, the function $u$ can switch at any point
$(i-1)+j\tfrac{T}{N}$ for $j=0,\dots,\tfrac{N}{T}$. Thus $t_{2i}-(i-1)$ is no
longer binary, but can take any value in $\\{j\tfrac{T}{N}\colon
j=0,\dots,\tfrac{N}{T}\\}$. Hence, for large enough $N$, any vertex of the
polytope $\\{x\in[0,1]^{n}\colon Bx\leq d\\}$ can be represented by
$x_{i}=t_{2i}-(i-1)$ since $A$ and $b$ are rational, so that the decision
whether $D(A,b)_{N}\neq\emptyset$ reduces to deciding feasibility of a linear
program, which can be done in polynomial time. In other words, Theorem 6.3
does not rule out the existence of a compact extended formulation for $D(A,b)$
that is only _weakly_ compatible with discretization.

######  Example 6.5.

It can happen that different discretizations of the same problem are tractable
or NP-hard depending on the choice of $N$, and the two situations may even
alternate. As an example, consider the following fractional version of the
vertex cover problem: given a simple graph $G=(V,E)$, $\gamma\in\mathbb{N}$
and $K\in\mathbb{Q}$, decide whether there exists a solution
$x\in\mathbb{R}^{V}$ of

$\begin{array}[]{rcll}\sum_{v\in V}x_{v}&\leq&K\\\
x_{v}+x_{w}&\geq&1&\forall(v,w)\in E\\\ x_{v}&\in&[0,1]&\forall v\in
V\end{array}$

such that all entries of $x$ are integer multiples of
$\nicefrac{{1}}{{\gamma}}$. Theorem 6.3 shows that this problem can be reduced
to deciding whether $D(A,b)_{N}=\emptyset$ with $N=\gamma n$, for appropriate
$A$ and $b$. Since the vertex cover polytope is half-integral, meaning that
all vertices have entries being multiples of $\nicefrac{{1}}{{2}}$, the above
problem reduces to a linear program for even $\gamma$. For the problem
constructed in the proof of Theorem 6.3, it can thus be decided in polynomial
time whether $D(A,b)_{N}\neq\emptyset$ whenever $N$ is an even multiple of
$n$. However, the same decision problem turns NP-complete when $N$ is an odd
multiple of $n$. For this, it suffices to show that the above fractional
vertex cover problem is NP-complete for all odd values of $\gamma$, which is
done in Appendix A. ∎

However, by adding an objective function to the problem, we can show that even
a weakly compatible extended formulation for $D(A,b)$ cannot exist in general.

######  Theorem 6.6.

A compact extended formulation for $D(A,b)$ that is weakly compatible with
discretization cannot exists unless P$\,=\,$NP.

###### Proof.

Consider the problem

(6.2) $\left\\{\quad\begin{aligned} \min\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
&\int_{0}^{T}c(t)u(t)\;\textnormal{d}t\\\ \text{s.t.}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &u\in D(A,b)\end{aligned}\right.$

for the function $c\in L^{2}(0,T)$ defined by $c(t)=\tfrac{1}{2}-(t-\lfloor
t\rfloor)$. Then $c_{N}$ can be computed efficiently for each $N$ and the
discretized problem reads

(6.3) $\left\\{\quad\begin{aligned} \min\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
&\tfrac{1}{N}\sum_{i=1}^{N}(c_{N})_{i}u_{i}\\\ \text{s.t.}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
&u\in\mathbb{R}^{N},\leavevmode\nobreak\ \overline{u}\in
D_{N}(A,b)\;.\end{aligned}\right.$

It suffices to show that (BPF) can be polynomially reduced to Problem (6.3)
for $N=\ell(n)n$ whenever $\ell(n)$ is polynomial in $n$. Indeed, under the
assumption that a compact and weakly compatible extended formulation exists,
this yields an efficient algorithm for deciding (BPF) as follows: First,
choose $M=n$ and efficiently compute some $\ell$ as in Definition 3.3. Since
$\ell$ is required to be polynomial in $M$, we would then have that (BPF) can
be polynomially reduced to Problem (6.3) for $N=\ell M$, and by the
compatibility assumption, Problem (6.3) can be solved in polynomial time for
this $N$. This implies that (BPF) can be solved in polynomial time and hence
P$\,=\,$NP.

In order to construct the desired polynomial reduction, let an instance of
(BPF) be given by $B\in\mathbb{Q}^{m\times n}$ and $d\in\mathbb{Q}^{m}$. We
define $T$, $\sigma$, and the switching point constraints exactly as in the
first part of the proof of Theorem 6.3. We now claim that the given instance
of (BPF) is feasible if and only if the constructed instance of Problem (6.3)
for $N=\ell(n)n$ has an optimal value of zero. For this, the objective value
of $u\in\mathbb{R}^{N}$ with $\overline{u}\in D_{N}(A,b)$ can be computed as
follows: for $i=1,\dots,n$, we have

$\displaystyle\sum_{j=1}^{\ell(n)}(c_{N})_{(i-1)\ell(n)+j}u_{(i-1)\ell(n)+j}$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{(t_{2i}-(i-1))\ell(n)}(c_{N})_{(i-1)\ell(n)+j}$
$\displaystyle=$ $\displaystyle\int_{i-1}^{t_{2i}}c(t)\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\int_{0}^{t_{2i}-(i-1)}(\tfrac{1}{2}-t)\,\textnormal{d}t$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}\big{(}t_{2i}-(i-1)\big{)}\big{(}1-(t_{2i}-(i-1))\big{)}\;,$

so that

$\displaystyle c_{N}^{\top}u$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{\ell(n)}(c_{N})_{(i-1)\ell(n)+j}u_{(i-1)\ell(n)+j}$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}\sum_{i=1}^{n}\big{(}t_{2i}-(i-1)\big{)}\big{(}1-(t_{2i}-(i-1))\big{)}\;.$

The latter expression is always non-negative, since $t_{2i}-(i-1)\in[0,1]$ for
all $i=1,\dots,n$. It follows that all $u\in D(A,b)_{N}$ have a non-negative
objective value in the constructed instance, and the objective value is zero
if and only if $t_{2i}-(i-1)\in\\{0,1\\}$ for all $i=1,\dots,n$. This
concludes the proof. ∎

A closer look at the proof of Theorem 6.6 reveals that the difficulty of
linear optimization over $D(A,b)_{N}$ does _not_ stem from the binarity of the
switch $u$, but from the non-convex relation between the switching points of
$u$ and the value of $u$ at a given point $t\in[0,T]$. This however does not
rule out the existence of compact and compatible extended formulations in
special cases, as shown by Theorem 5.1.

## References

  * [1] Hans Wilhelm Alt.  Linear functional analysis: an application-oriented introduction.  Springer, 2016.
  * [2] Hedy Attouch, Giuseppe Buttazzo, and Gérard Michaille.  Variational Analysis in Sobolev and BV Spaces.  Society for Industrial and Applied Mathematics, 2014.
  * [3] Pascale Bendotti, Pierre Fouilhoux, and Cécile Rottner.  The min-up/min-down unit commitment polytope.  Journal of Combinatorial Optimization, 36:1024–1058, 2018.
  * [4] Haim Brezis.  Functional analysis, Sobolev spaces and partial differential equations, volume 2.  Springer, 2011.
  * [5] Christoph Buchheim, Alexandra Grütering, and Christian Meyer.  Parabolic optimal control problems with combinatorial switching constraints – Part I: Convex relaxations.  SIAM Journal on Optimization.  To appear.
  * [6] Christoph Buchheim, Alexandra Grütering, and Christian Meyer.  Parabolic optimal control problems with combinatorial switching constraints – Part II: Outer approximation algorithm.  SIAM Journal on Optimization.  To appear.
  * [7] Christoph Buchheim, Alexandra Grütering, and Christian Meyer.  Parabolic optimal control problems with combinatorial switching constraints – Part III: Branch-and-bound algorithm.  Technical report, 2024.
  * [8] Christoph Buchheim and Maja Hügging.  The polytope of binary sequences with bounded variation.  Discrete Optimization, 48:100776, 2023.
  * [9] Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli.  Extended formulations in combinatorial optimization.  Annals of Operations Research, 204:97–143, 2013.
  * [10] Richard M. Karp.  Complexity of Computer Computations, chapter Reducibility among Combinatorial Problems, pages 85–103.  The IBM Research Symposia Series. Springer, 1972.
  * [11] Jon Lee, Janny Leung, and François Margot.  Min-up/min-down polytopes.  Discrete Optimization, 1:77–85, 2004.
  * [12] Deepak Rajan and Samer Takriti.  Minimum up/down polytopes of the unit commitment problem with start-up costs.  Technical Report RC23628, IBM Research Report, 2005.
  * [13] Sebastian Sager, Michael Jung, and Christian Kirches.  Combinatorial integral approximation.  Mathematical Methods of Operations Research, 73(3):363–380, 2011\.
  * [14] Sebastian Sager and Clemens Zeile.  On mixed-integer optimal control with constrained total variation of the integer control.  Computational Optimization and Applications, 78(2):575–623, 2021\.
  * [15] Clemens Zeile, Nicolò Robuschi, and Sebastian Sager.  Mixed-integer optimal control under minimum dwell time constraints.  Mathematical Programming, pages 1–42, 2020.

##  Appendix A Fractional vertex cover

We claim that for odd $\gamma\in\mathbb{N}$, the following decision problem is
NP-complete: given a simple graph $G=(V,E)$ and $K\in\mathbb{Q}$, decide
whether there exists a solution $x\in\mathbb{Q}^{V}$ of

($\gamma$-VC) $\left\\{\quad\begin{array}[]{rcll}\sum_{v\in
V}x_{v}&\leq&K\\\\[4.30554pt] x_{v}+x_{w}&\geq&1&\forall(v,w)\in
E\\\\[4.30554pt] x_{v}&\in&[0,1]&\forall v\in V\\\\[4.30554pt]
x_{v}&\in&\tfrac{1}{\gamma}\mathbb{Z}&\forall v\in V\;.\end{array}\right.$

To show this claim, we reduce the NP-complete decision variant of the
(ordinary) vertex cover problem to the above problem. So given an instance of
the vertex cover problem, i.e., a graph $G^{\prime}=(V^{\prime},E^{\prime})$
and $K^{\prime}\in\mathbb{N}$, we construct $G=(V,E)$ from $G^{\prime}$ as
follows: for each $v\in V^{\prime}$, we add three new vertices
$v^{(1)},v^{(2)},v^{(3)}$ and four new edges

$(v,v^{(1)}),(v^{(1)},v^{(2)}),(v^{(2)},v^{(3)}),(v^{(3)},v^{(1)})\;.$

In words, we add a triangle $T_{v}$ for each vertex $v\in V^{\prime}$ and
connect it to $v$ by a bridge. We now claim that $G^{\prime}$ has a vertex
cover of size at most $K^{\prime}$ if and only if ($\gamma$-VC) has a solution
for $G$ and $K:=\tfrac{1}{\gamma}K^{\prime}+2|V^{\prime}|$.

First assume that $S\subseteq V^{\prime}$ is a vertex cover of $G^{\prime}$
with $|S|\leq K^{\prime}$. Then the following vector is a solution of
($\gamma$-VC): set $x_{v}=\tfrac{\gamma+1}{2\gamma}$ for $v\in
S\cup\\{v^{(1)},v^{(2)}\colon v\in V^{\prime}\\}$ and
$x_{v}=\tfrac{\gamma-1}{2\gamma}$ otherwise. Indeed, it is easy to verify that
$x$ satisfies the covering constraints. For the cardinality constraint, we
have

$\sum_{v\in
V}x_{v}=\tfrac{\gamma+1}{2\gamma}(|S|+2|V^{\prime}|)+\tfrac{\gamma-1}{2\gamma}(|V^{\prime}|-|S|+|V^{\prime}|)=\tfrac{1}{\gamma}|S|+2|V^{\prime}|\leq
K\;.$

For the other direction, let $x\in\mathbb{Q}^{V}$ solve ($\gamma$-VC). We may
assume $x_{v^{(1)}}=\tfrac{\gamma+1}{2\gamma}$ for all $v\in V^{\prime}$.
Indeed, using a smaller value does not allow to decrease the costs of covering
$T_{v}$ while contributing less to cover $(v,v^{(1)})$. On the other hand,
using a larger value increases the costs of covering $T_{v}$ by at least as
much as it would cost to increase $x_{v}$ instead. So we can assume
$x_{v}\geq\tfrac{\gamma-1}{2\gamma}$ for all $v\in V$ now. In particular, it
suffices to choose $x_{v}\leq\tfrac{\gamma+1}{2\gamma}$ to cover all edges in
$E$, hence

$x_{v}\in\\{\tfrac{\gamma-1}{2\gamma},\tfrac{\gamma+1}{2\gamma}\\}\quad\forall
v\in V^{\prime}$

without loss of generality. Then it is easy to verify that the set $S:=\\{v\in
V\colon x_{v}=\tfrac{\gamma+1}{2\gamma}\\}$ is a vertex cover of $G^{\prime}$
of size at most $K^{\prime}$.∎