Computational Approaches for Mixed Integer Optimal Control Problems with Indicator Constraints

Abstract

Optimal control problems with mixed integer control functions and logical implications, such as a state-dependent restriction on when a control can be chosen (so-called indicator or vanishing constraints) frequently arise in practice. A prominent example is the optimal cruise control of a truck. As every driver knows, admissible gear choices critically depend on the current velocity. A large variety of approaches has been proposed on how to numerically solve this challenging class of control problems. We present a computational study in which the most relevant of them are compared for a reference model problem, based on the same discretization of the differential equations. This comprehends dynamic programming, implicit formulations of the switching decisions, and a number of explicit reformulations, including mathematical programs with vanishing constraints in function spaces. We survey all of these approaches in a general manner, where several formulations have not been reported in the literature before. We apply them to a benchmark truck cruise control problem and discuss advantages and disadvantages with respect to optimality, feasibility, and stability of the algorithmic procedure, as well as computation time.

1 Introduction

Mixed integer optimal control problems (MIOCPs, also known as switched systems) have been gaining significantly increased interest. The underlying processes have a high potential for optimization, while at the same time, they are hard to assess manually due to their combinatorial, nonlinear, and dynamic nature. Typical examples are water or gas networks [14, 45], traffic flow [22, 28], supply chain networks [44], distributed autonomous systems [1], processes in chemical engineering that involve valves [35, 65], and the choice of gears in automotive control [13, 25, 42]. See [56] for an open benchmark library for MIOCPs. The truck benchmark problem we discuss in this article is motivated by work of [30, 33, 36,37,38, 40, 68].

Definition 1 (MIOCP)

In this article, we refer to the switched dynamic optimization problem given by

$$\begin{array}{@{}rcl@{}} &&\underset{\boldsymbol{Y}(\cdot)}{\min\limits_{{\boldsymbol{x}(\cdot), \boldsymbol{u}(\cdot),}}} e(\boldsymbol{x}(t_{\text{f}}))\\ &&\text{s.t.} \bigoplus\limits_{1 \leq i \leq n_{\omega}}\left[ \begin{array}{c} Y_{i}(t) \\ \dot{\boldsymbol{x}}(t) = \boldsymbol{f}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}^{i}) \\ \boldsymbol{0} \le \boldsymbol{c}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}^{i}) \end{array} \right]\quad t \in [0, t_{\text{f}}]~\text{ a.e.},\\ &&\qquad \boldsymbol{x}(0) = \boldsymbol{x}_{0},\\ &&\qquad \boldsymbol{0} \le \boldsymbol{d}(\boldsymbol{x}(t),\boldsymbol{u}(t))\quad t \in [0, t_{\text{f}}]~\text{ a.e}. \end{array} $$

as a mixed integer optimal control problem (MIOCP). The disjunction $\oplus$ over $1\leq i\leq n_{\omega }$ signifies that, at every point on the time horizon $t \in [0, t_{\text {f}}]$ in time, exactly one of the $n_{\omega }$ possible modes is chosen. This choice is represented here by time-dependent logical literals $Y_{i}(\cdot )$, $1 \leq i \leq n_{\omega }$. Setting $Y_{i}(t)=\text {true}$ selects a mode; the other literals then assume the value $Y_{j}(t)=\text {false}$ for $j\neq i$. The control $\boldsymbol {u}: [0, t_{\text {f}}] \rightarrow \mathbb {R}^{n_{\text {u}}}$ is assumed to be measurable and of bounded variation. The differential states $\boldsymbol {x}: [0, t_{\text {f}}] \rightarrow \mathbb {R}^{n_{x}}$ are assumed to be uniquely determined by $\boldsymbol {f}$ and $\boldsymbol {x}_{0}$ once a switching regime $Y(\cdot )$ and a control $\boldsymbol {u}(\cdot )$ are fixed. The vectors $\boldsymbol {v}^{i} \in \mathbb {R}^{n_{\text {v}}}$ comprise constant values specific for the given mode, and we let ${\Omega } := \{\boldsymbol {v}^{1}, \boldsymbol {v}^{2}, \dots , \boldsymbol {v}^{n_{\omega }}\}$. The objective function $e: \mathbb {R}^{n_{\text {x}}} \rightarrow \mathbb {R}$ of Mayer type and the constraint functions $\boldsymbol {c} : \mathbb {R}^{n_{\text {x}}} \times \mathbb {R}^{n_{\text {u}}} \times \mathbb {R}^{n_{\text {v}}} \rightarrow \mathbb {R}^{n_{\text {c}}}$ and $\boldsymbol {d:} \mathbb {R}^{n_{\text {x}}} \times \mathbb {R}^{n_{\text {u}}}\rightarrow \mathbb {R}^{n_{\text {d}}}$ are assumed to be twice continuously differentiable.

A challenging part of solving a MIOCP is to find optimal discrete mode choices $\boldsymbol {Y}(\cdot )$. We are particularly interested in the indicator constraint $0 \le c(\boldsymbol {x}(t), \boldsymbol {u}(t), \boldsymbol {v}^{i})$ in Definition 1, which only plays a role if mode i is active (indicated) at time t. In this article, we discuss several approaches to formulating these and to computationally solving the arising optimization problems.

• In direct methods with explicit switching, the boolean literals $\boldsymbol {Y}(\cdot )$ are included as optimization variables, giving rise to nonlinear non-convex mixed integer optimization problems. Typically, continuous relaxations are solved within methods that provide integer solutions, such as Branch & Bound or rounding.

• In direct methods with implicit switching, the truth values of the boolean literals $\boldsymbol {Y}(\cdot )$ are computed from a switching function that uniquely determines the current mode and makes sure that the indicator constraints $0 \le c(\boldsymbol {x}(t),\boldsymbol {u}(t),\boldsymbol {v}^{i})$ are fulfilled.

• Dynamic programming provides a global solution on a given discretization and allows an enumerative treatment of integrality and indicator constraints.

There are of course connections between the different formulations; e.g., a transcription method from implicit switching to explicit switching on a time discretization grid is proposed in [11]. And there are further approaches that we are not addressing in this paper. Indirect methods use necessary optimality conditions for (MIOCP) in function space, compare [26], and solve the resulting boundary value problem. Moment relaxations use polynomial optimization for switched systems [16, 58]. Time transformation approaches transform the problem into one where the stage lengths become continuous optimization variables, [25]. See [50] for an extension to indicator constraints. See [60] for a survey with further references and a discussion of advantages of different formulations for MIOCPs without indicator constraints.

There are several reformulations of logical relationships in the literature. Generalized disjunctive programming results directly from a logical modeling paradigm. It generalizes the disjunctive programming approach of [4]. Logical variables are usually either incorporated by means of big-M constraints or via a convex hull formulation (see [27, 49, 51, 67]). From a different point of view, disjunctive programming formulations can be interpreted as the result of reformulation-linearization technique (RLT) steps [64]. For both, the convex hull relaxation uses perspective functions. Based on this, the use of perspective cuts to strengthen convex MINLP relaxations has been proposed in various articles, for example, [15, 21, 29]. MINLP techniques are surveyed in [8].

Complementarity and indicator/vanishing constraints are another way to look at logical implications. The general concept of nonlinear optimization over non-convex structures is discussed in [62, 63]. For the comparatively new problem class of MPVCs, we refer to [2, 31]. Due to the lack of constraint qualification, various approaches for the computational solution of MPCCs and MPVCs have been devised and include regularizations [31, 54, 66], smoothing [17, 31], and combinations thereof (see [23] for an overview). Nonlinear programming for MPCCs is addressed in [3, 19, 46, 47]. Active set methods tailored to the non-convex structure are discussed in [18, 36, 41]. Formulations of MPCCs and MPVCs in optimal control can be found in [5, 36, 43, 52, 53].

In this article, we propose a new implicit approach to solve mixed integer optimal control problems with indicator constraints, and tailor it to the case of truck control. In addition, we provide the first comprehensive numerical assessment of different explicit, implicit, local, and global solution approaches to this problem class. Some of the results concerning explicit approaches have already been published in the book contribution [33] and the PhD thesis [32]. They are extended here by new variants of perspective reformulations, and also by considerations of dynamic programming [13] and implicit switching approaches. Several aspects play a role in this comparison:

• Some approaches provide an integer solution, while others solve a relaxed problem. For integer-feasible solutions, a small objective function value is obviously desirable, preferably the global minimum of (MIOCP). For fractional solutions of relaxed problems, the situation is different: in addition to local vs. global minimality, the aspect of the tightness of the relaxation plays a role. For relaxed solutions, a higher objective function value may indicate that the relaxation is tighter and of better use in a Branch & Bound scheme.

• Due to discretization (e.g., the discretization of the state space in dynamic programming) or rounding solutions may be infeasible in a forward simulation.

• The computation of optimal controls for the autonomous vehicle problem has to take place in real-time in order to enable a near instantaneous reaction to speed limits, slope changes, and to unforeseen alterations of traffic conditions. At the same time, all computations need to be performed by an on-board embedded system with limited computational resources.

We compare all approaches with respect to objective function value, fractionality, infeasibility, and CPU time.

In Section 2, we describe a benchmark MIOC problem, the control of a heavy duty truck, including two scenarios. In Section 3, we describe a family of so-called explicit approaches to MIOC, including relaxations from partial inner and outer convexification, and we propose several relaxations based on the perspective. In Section 4, we propose a new family of formulations belonging to the so-called implicit solution approach to MIOC. In Section 5, we describe a dynamic programming approach to MIOC. We describe and discuss the setting and the numerical results of the computational study in Section 6 and conclude with a summary in Section 7.

2 A Heavy-Duty Truck Cruise Control Problem

We present a mathematical model for a truck cruise control problem that is the base of all following comparisons. For more detailed expositions of various related models, we refer the reader to [12, 32, 33, 36, 38].

2.1 Controls and Dynamic System

The independent variable of the model is the traveled distance s in the range $[0, s_{\text {f}}]$ (in m). There are two control functions with continuous domain, the indicated engine torque $M_{\text {ind}}$ and the engine brakes torque $M_{\text {brk}}$ (both in Nm). The gear choice $\mu : [0,s_{\text {f}}] \mapsto \{1,\ldots ,n_{\mu }\}$ is a discrete control. There are two differential states, velocity v (in m/s), and accumulated fuel consumption Q (in l/s). The longitudinal dynamics are given by the ordinary differential equation

$$\begin{array}{@{}rcl@{}} \dot{v} &=&\tfrac{1}{m v}\left( \tfrac{i_{\text{A}}}{r_{\text{stat}}}\left( i_{\text{T}}(\mu)\eta_{\text{T}}(\mu)M_{\text{ind}} - M_{\text{brk}} - i_{\text{T}}(\mu)M_{\text{fric}}(v)\right) + M_{\text{ext}}(v,\gamma)\right)\\ &=:& f_{v}(v,M_{\text{ind}},M_{\text{brk}},i_{\text{T}}(\mu), \eta_{\text{T}}(\mu),\gamma), \end{array} $$

(1)

and the accumulated fuel consumption is given by

$$\begin{array}{@{}rcl@{}} \dot{Q} &=& \tfrac{1}{v} \left( c_{0} + \left( c_{1} n_{\text{eng}}(v, i_{\text{T}}(\mu)) + c_{2} M_{\text{ind}} \right)^{2} \right) \\ &=:& f_{Q}(v,M_{\text{ind}},i_{\text{T}}(\mu)), \end{array} $$

(2)

with engine speed

$$ n_{\text{eng}}(v, i_{\text{T}}(\mu)) := v i_{\text{A}} i_{\text{T}}(\mu) 60/(2\pi r_{\text{stat}}), $$

(3)

engine friction (in Nm)

$$ M_{\text{fric}}(v) := \left( c_{4} n_{\text{eng}}(v, i_{\text{T}}(\mu))^{2} + c_{5} n_{\text{eng}}(v, i_{\text{T}}(\mu)) + c_{6} \right), $$

(4)

and the influence of air, gravity, and the influence of the road slope $\gamma$ (in rad) via rolling friction as part of the external engine torque $M_{\text {ext}}$ (in Nm)

$$ M_{\text{ext}}(v,\gamma) := - \tfrac12 c_{w} A \rho v^{2} - m g \sin(\gamma) + c_{7} \cos(\gamma). $$

The values $i_{\text {A}}$, $r_{\text {stat}}$ (in m), $i_{\text {T}}$, $\eta _{\text {T}}$, $\boldsymbol {c}$, m, g, $c_{w}$, A are constant model parameters and are independent of s, while all other quantities depend on the position s.

2.2 Objective Function

The cost to be minimized on the time horizon $[0,s_{\text {f}}]$ comprises three contributing terms, namely a penalty term for the deviation of the velocity from the desired one

$$ {\Phi}_{\text{dev}}(s_{\text{f}}) := {\int}_{0}^{s_{\text{f}}}\left( v(s)-v_{\text{des}}(s)\right)^{2} \text{d}s, $$

(5a)

and the overall fuel consumption

$$ {\Phi}_{\text{fuel}}(s_{\text{f}}) := Q(s_{\text{f}}). $$

(5b)

The terms are weighted by weights $\lambda _{\text {d}}$, $\lambda _{\text {f}} \geq 0$ and summed up. A comfort term that penalizes rapid torque changes

$$ {\Phi}_{\text{comf}}(s_{\text{f}}) := {\int}_{0}^{s_{\text{f}}} \dot{M}_{\text{ind}}^{2}(s) + \dot{M}_{\text{brk}}^{2}(s) \text{d}s $$

(5c)

could also be included, but would require $\dot {M}_{\text {ind}}$ and $\dot {M}_{\text {brk}}$ to be the controls subject to optimization in order to obtain a differentiable objective.

2.3 Constraints

We account for mechanical constraints on the engine speed (3) with

$$ n^{\min}_{\text{eng}} \le n_{\text{eng}}(v(s), i_{\text{T}}(\mu(s))) \le n_{\text{eng}}^{\max} $$

(6)

and on the torques with

$$\begin{array}{@{}rcl@{}} M_{\text{ind}}(s) &\leq & M_{\text{ind}}^{\max} (v(s), i_{\text{T}}(\mu(s))), \end{array} $$

(7a)

$$\begin{array}{@{}rcl@{}}0 &\leq & M_{\text{ind}}(s), \end{array} $$

(7b)

$$\begin{array}{@{}rcl@{}}0 &\leq& M_{\text{brk}}(s) \leq M_{\text{brk}}^{\max}, \end{array} $$

(7c)

for $s \in [0,s_{\text {f}}]$. The maximum engine torque is given by

$$M_{\text{ind}}^{\max}(v, i_{\text{T}}(\mu)) := c_{7} - (n_{\text{eng}}(v, i_{\text{T}}(\mu)) - c_{8})^{2} / c_{9}. $$

There may be speed limits, e.g., by law,

$$ v(s) \leq v_{\text{law}}(s), \quad s \in [0,s_{\text{f}}]. $$

(8)

2.4 Problem Formulation

Summarizing, this leads to the following problem formulation for the heavy-duty truck control problem on the time horizon $s\in [0,s_{\text {f}}]$:

$$\begin{array}{@{}rcl@{}} &&\min\limits_{\boldsymbol{x}(\cdot), \boldsymbol{u}(\cdot),\mu(\cdot)} {\lambda_{\text{d}}{\Phi}_{\text{dev}}(s_{\text{f}}) + \lambda_{\text{f}}{\Phi}_{\text{fuel}}(s_{\text{f}})}\\ &&\text{s.t.}~\bigoplus\limits_{1 \leq i \leq n_{\mu}} \left[\begin{array}{l} \mu(s)=i \\ \text{ODE system}~(1), (2) \\ \text{Constraints}~(6), (7a) \end{array} \right]\qquad s \in [0, s_{\text{f}}]~\text{ a.e.},\\ &&\boldsymbol{x}(0) = \boldsymbol{x}_{0},\\ &&\text{Constraints}~(7b), (7c), (8)\qquad s \in [0, s_{\text{f}}]~\text{a.e.}, \end{array} $$

(9)

with state vector $\boldsymbol {x}(s)=(v(s), Q(s))^{T}$, continuous control vector $\boldsymbol {u}(s)=(M_{\text {ind}}(s)$, $M_{\text {brk}}(s))^{T}$, the integer control μ(s), and fixed initial state $\boldsymbol {x}_{0}$.

3 Explicit Switching Formulations

We investigate explicit approaches to reformulate problem (MIOCP), with a special focus on problem (10). They all use binary control functions $\boldsymbol {y}: [0,s_{\text {f}}] \mapsto \{0,1\}^{n_{\mu }}$ that indicate whether gear i is chosen at position s or not. These reformulations are by construction equivalent for integer gear choices, but their relaxations to $\boldsymbol {y}: [0,s_{\text {f}}] \mapsto [0,1]^{n_{\mu }}$ may have completely different characteristics. As the relaxations play an important role in mixed integer algorithms (such as Branch & Bound or rounding heuristics), a thorough study of the tightness of the relaxations and of numerical properties is needed.

The character of the exclusive disjunction in (10) is captured via the special ordered set type 1 constraints

$$ \sum\limits_{j = 1}^{n_{\mu}} y_{j}(s) = 1 \quad \forall s\in[0,s_{\text{f}}]. $$

For a more compact notation, we leave away the argument $(s)$ for the states $v,Q$ and the controls $M_{\text {ind}},M_{\text {brk}},\boldsymbol {y}$ in the following.

3.1 Inner Convexification (IC)

For problem (10), it is possible to reformulate the time-dependent disjunctions by means of a function $\boldsymbol {g}: [1, n_{\mu }] \rightarrow \mathbb {R}^{2}$ that can be inserted into the right-hand side function $f(\cdot )$ and into the constraints $c(\cdot )$ and has the property

$$\boldsymbol{g}(\mu) = \left( i_{\text{T}}(\mu), \eta_{\text{T}}(\mu)\right)^{T} $$

for $\mu \in \{1, \ldots , n_{\mu }\}$. One possibility is a convex combination of the tabulated values,

$$ \boldsymbol{g}(\boldsymbol{y} ) = \sum\limits_{j = 1}^{n_{\mu}} y_{j} \left( i_{\text{T}}(j), \eta_{\text{T}}(j)\right)^{T}. $$

(10)

Other possibilities are a piecewise linear representation with special ordered set type 2 variables or fitted smooth convex functions $g(\cdot )$ as suggested in [24].

Applying IC to the ODEs (1), (2) and the constraints (6), (7a) in problem (10), we obtain

$$\begin{array}{@{}rcl@{}} \dot{v} &=& f_{v}(v,M_{\text{ind}},M_{\text{brk}},g_{1}(\boldsymbol{y}), g_{2}(\boldsymbol{y}),\gamma), \end{array} $$

(11a)

$$\begin{array}{@{}rcl@{}} \dot{Q} &=& f_{Q}(v,M_{\text{ind}},g_{1}(\boldsymbol{y})) \end{array} $$

(11b)

and

$$\begin{array}{@{}rcl@{}} {n}_{\text{eng}}^{\min} &\le& {n}_{\text{eng}}(v, g_{1}(\boldsymbol{y})) \le {n}_{\text{eng}}^{\max}, \end{array} $$

(12a)

$$\begin{array}{@{}rcl@{}} {M}_{\text{ind}} &\leq& {M}_{\text{ind}}^{\max}(v, g_{1}(\boldsymbol{y})). \end{array} $$

(12b)

3.2 Outer Convexification (OC)

Partial outer convexification [39, 55, 57, 60] uses a convex combination of all function evaluations on the top (outermost) level. The resulting problem may still be non-convex in the differential states or continuous controls; thus, it may only be a partial convexification. Applying OC to the ODEs (1)–(2) and the constraints (6)–(7a) in problem (10), we obtain the one-row relaxations

$$\begin{array}{@{}rcl@{}} \dot{v} &=& \sum\limits_{j = 1}^{n_{\mu}} y_{j} f_{v}(v,M_{\text{ind}},M_{\text{brk}},i_{\text{T}}(j), \eta_{\text{T}}(j),\gamma), \end{array} $$

(13a)

$$\begin{array}{@{}rcl@{}} \dot{Q} &=& \sum\limits_{j = 1}^{n_{\mu}} y_{j} f_{Q}(v,M_{\text{ind}},i_{\text{T}}(j)) \end{array} $$

(13b)

and

$$\begin{array}{@{}rcl@{}} {n}_{\text{eng}}^{\min} &\le& \sum\limits_{j = 1}^{n_{\mu}} y_{j} n_{\text{eng}}(v, i_{\text{T}}(j)) \le {n}_{\text{eng}}^{\max}, \end{array} $$

(14a)

$$\begin{array}{@{}rcl@{}} {M}_{\text{ind}} &\leq& \sum\limits_{j = 1}^{n_{\mu}} y_{j} {M}_{\text{ind}}^{\max}(v, i_{\text{T}}(j)). \end{array} $$

(14b)

3.3 Big M Constraints (bigM)

A classical way to reformulate indicator constraints of the type $y = 1 \Rightarrow c(x) \le 0$ are Big-M formulations $c(x) \le M (1 - y)$ with $M \ge \max _{x} c(x)$. The constraints (6)–(7a) in problem (10) are reformulated as

$$\begin{array}{@{}rcl@{}} - n_{\text{eng}}(v, i_{\text{T}}(j)) &\le& - n_{\text{eng}}^{\min} + M (1 - y_{j}), \end{array} $$

(15a)

$$\begin{array}{@{}rcl@{}} n_{\text{eng}}(v, i_{\text{T}}(j)) &\le& n_{\text{eng}}^{\max} + M (1 - y_{j}), \end{array} $$

(15b)

$$\begin{array}{@{}rcl@{}} M_{\text{ind}} &\le& {M}_{\text{ind}}^{\max}(v, i_{\text{T}}(j)) + M (1 - y_{j}). \end{array} $$

(15c)

Problem-specific values M can be found in [33, p. 181].

3.4 Relaxed Vanishing Constraints (relVC)

We formulate the constraints (6)–(7a) via a multiplication with the indicating variable $y_{j}$ and a relaxation by $\varepsilon$, i.e.,

$$\begin{array}{@{}rcl@{}} y_{j} n_{\text{eng}}^{\min} - \varepsilon & \le& y_{j} n_{\text{eng}}(v, i_{\text{T}}(j)) \le y_{j} n_{\text{eng}}^{\max} + \varepsilon, \end{array} $$

(16a)

$$\begin{array}{@{}rcl@{}} y_{j} M_{\text{ind}} - \varepsilon & \le& y_{j} M_{\text{ind}}^{\max}(v, i_{\text{T}}(j)). \end{array} $$

(16b)

3.5 Smoothened Vanishing Constraints (smoVC)

We reformulate (6)–(7a) using a smoothing-relaxation formulation suggested by [31],

$$ \phi^{\text{VC}}_{\varepsilon}(a,b)=\frac{1}{2}\left( ab + \sqrt{a^{2}b^{2}+\varepsilon^{2}} +\sqrt{b^{2}+\varepsilon^{2}}-b\right) - \varepsilon. $$

(17)

This results in

$$\begin{array}{@{}rcl@{}} 0 &\geq& \phi_{\varepsilon}^{\text{VC}}\left( n_{\text{eng}}^{\min} - n_{\text{eng}}\left( v, i_{\text{T}}(j)\right), y_{j}\right), \end{array} $$

(18a)

$$\begin{array}{@{}rcl@{}} 0 &\geq& \phi_{\varepsilon}^{\text{VC}}\left( n_{\text{eng}}\left( v, i_{\text{T}}(j)\right)-n_{\text{eng}}^{\max}, y_{j}\right), \end{array} $$

(18b)

$$\begin{array}{@{}rcl@{}} 0 &\geq& \phi_{\varepsilon}^{\text{VC}}\left( M_{\text{ind},j}-M_{\text{ind}}^{\max}(v, i_{\text{T}}(j)),y_{j} \right). \end{array} $$

(18c)

3.6 Perspective and Full Lifting (PFL)

In generalized disjunctive programming (GDP, [27]) two concepts are combined: lifting and convex hull relaxations via the perspectives of constraint functions.

Definition 2

(Perspective function) The perspective of a function $f: \mathbb {R}^{n_{1}} \times {\dots } \times \mathbb {R}^{n_{n}}\rightarrow \mathbb {R}$ with respect to the first p arguments $\boldsymbol {x}_{\boldsymbol {1}}, \dots , \boldsymbol {x}_{\boldsymbol {p}}$ is the function $\hat {f}: \mathbb {R}\times \mathbb {R}^{n_{1}} \times {\dots } \times \mathbb {R}^{n_{n}}\rightarrow \mathbb {R}$ defined by

$$\begin{array}{@{}rcl@{}} && \hat{f}(y;~\boldsymbol{x}_{\boldsymbol{1}},\dots,\boldsymbol{x}_{\boldsymbol{n}})\\ && := \left\{ \begin{array}{cl} y f(\tfrac{\boldsymbol{x}_{\boldsymbol{1}}}{y},\dots,\tfrac{\boldsymbol{x}_{\boldsymbol{p}}}{y},\boldsymbol{x}_{p + 1}, \dots, \boldsymbol{x}_{\boldsymbol{n}}) & \text{ if } y > 0, \\ 0 & \text{ if } y = 0,~ \boldsymbol{x}_{\boldsymbol{j}} = \boldsymbol{0}\text{ for some }j\leq p,\\ \infty & \text{ otherwise}. \end{array} \right. \end{array} $$

It is well known that, for fixed index p, this function is convex if f is convex. In this case, it yields the convex hull of the feasible disjunctive set if the binary variable $y \in \{0,1\}$ is relaxed and the variables are linked via

$$ \boldsymbol{x}_{\boldsymbol{j}} \le y \boldsymbol{x}^{\max}_{j},\quad 1 \leq j \leq p $$

compare, e.g., [29]. The tightness of perspective-based relaxations is often very good, compare the study of [48] for switched affine control systems. Perspectives are, however, well known to cause numerical issues for small values of y. For computational purposes, we use the smooth perspective, defined as follows.

Definition 3

(Smooth perspective [61]) The function

$$\tilde{f}(y; \boldsymbol{x}) := \hat{f}((1-\varepsilon)y + \varepsilon; \boldsymbol{x}) + \varepsilon (y-1) f(\underbrace{\boldsymbol{0},\ldots,\boldsymbol{0}}_{p\textup{ times}},\boldsymbol{x}_{p + 1}, \dots, \boldsymbol{x}_{\boldsymbol{n}}) $$

is called smooth perspective function.

In GDP, auxiliary (lifted) variables are introduced, one copy for each disjunction. It is an open question, though, if really all variables should be lifted. In our full lifting formulation, we introduce trajectories $v_{j}, Q_{j}, M_{\text {ind},j}, M_{\text {brk},j}: [0,s_{\text {f}}] \mapsto \mathbb {R}$ for all states and continuous controls, and for all $j \in \{1, \ldots , n_{\mu }\}$. We couple them via constraints

$$\begin{array}{@{}rcl@{}} v &=& \sum\limits_{j = 1}^{n_{\mu}} v_{j},\quad M_{\text{ind}} = \sum\limits_{j = 1}^{n_{\mu}} M_{\text{ind},j}, \end{array} $$

(19a)

$$\begin{array}{@{}rcl@{}}{eq_perspective_vM}{} Q &=& \sum\limits_{j = 1}^{n_{\mu}} Q_{j},\quad M_{\text{brk}} = \sum\limits_{j = 1}^{n_{\mu}} M_{\text{brk},j} \end{array} $$

(19b)

that allow to evaluate the objective function. All constraints have to hold for all $n_{\mu }$ vectors of lifted variables, i.e., (7b), (7c), (8) are replaced by

$$\begin{array}{@{}rcl@{}} 0 \leq M_{\text{ind},j}, && \end{array} $$

(20a)

$$\begin{array}{@{}rcl@{}} 0 \leq M_{\text{brk},j} & \leq& y_{j} M_{\text{brk}}^{\max}, \end{array} $$

(20b)

$$\begin{array}{@{}rcl@{}}{eq:v-law-j}{} v_{j} & \leq& y_{j} v_{\text{law}}. \end{array} $$

(20c)

Applying perspectives to (1), (2) we obtain for $y_{j}>0$

$$\begin{array}{@{}rcl@{}} \dot{v_{j}} &=& \hat{f}_{v}\left( y_{j}; v_{j},{M}_{\text{ind},j},M_{\text{brk},j},i_{\text{T}}(j), \eta_{\text{T}}(j),\gamma\right) \end{array} $$

(21a)

$$\begin{array}{@{}rcl@{}} &=& y_{j} f_{v}\left( \tfrac{v_{j}}{y_{j}},\tfrac{M_{\text{ind},j}}{y_{j}},\tfrac{M_{\text{brk},j}}{y_{j}},i_{\text{T}}(j), \eta_{\text{T}}(j),\gamma\right) \end{array} $$

(21b)

$$\begin{array}{@{}rcl@{}} \dot{Q_{j}} &=& \hat{f}_{Q}\left( y_{j}; v_{j},M_{\text{ind},j},i_{\text{T}}(j)\right) \end{array} $$

(21c)

$$\begin{array}{@{}rcl@{}} &=& y_{j} {f}_{Q}\left( \tfrac{v_{j}}{y_{j}},\tfrac{M_{\text{ind},j}}{y_{j}},i_{\text{T}}(j)\right), \end{array} $$

(21d)

or the respective smoothed counterparts.

Definition 4

(Smoothed dynamics) After eliminating $y_{j}$ in the denominators of $\hat {f}_{v}$ or $\hat {f}_{Q}$ where possible, any gear indicator variables $y_{j}$ remaining in the denominators are replaced by the smoothing

$$ S\left( \frac{v_{j}}{y_{j}},\varepsilon\right):=\frac{(1-\varepsilon)v_{j}}{(1-\varepsilon)y_{j} + \varepsilon}+\varepsilon. $$

(22)

Applying perspectives to the constraints (6), (7a) yields

$$\begin{array}{@{}rcl@{}} y_{j} n_{\text{eng}}^{\min} &\le& y_{j} n_{\text{eng}}\left( \tfrac{v_{j}}{y_{j}}, i_{\text{T}}(j)\right) \le y_{j} n_{\text{eng}}^{\max}, \end{array} $$

(23a)

$$\begin{array}{@{}rcl@{}} M_{\text{ind},j} &\le& y_{j} M_{\text{ind}}^{\max}\left( \tfrac{v_{j}}{y_{j}}, i_{\text{T}}(j)\right). \end{array} $$

(23b)

Because $n_{\textup {eng}}$ is linear in its first argument, elimination of all denominator occurrences of $y_{j}$ is possible. Only constraint (23b) needs a smoothing that formally reads

$$M_{\text{ind},j} \le y_{j} M_{\text{ind}}^{\max}\left( S\left( \tfrac{v_{j}}{y_{j}},\varepsilon\right), i_{\text{T}}(j)\right), $$

and wherein the $y_{j}$ occurrence associated with the linear term of $M_{\text {ind}}^{\max }$ is eliminated before smoothing.

3.7 Perspective and Partial Lifting (PPL)

We further study whether a partial lifting is beneficial. Looking closer at (1), (2) and (21), it appears tempting to only introduce lifted trajectories $v_{j}, M_{\text {ind},j}: [0,s_{\text {f}}] \mapsto \mathbb {R}$ for all $j \in \{1, \ldots , n_{\mu }\}$, as $M_{\text {brk}}$ and Q enter the dynamics and the objective function independently of the disjunction. This leaves only the constraints (19b), (20a), and (20c) to be considered. Additionally, we split the right-hand side $f_{v}$ into disjunction-dependent and independent parts. This allows to choose the $v_{j}$ as algebraic variables instead of differential states,

$$\begin{array}{@{}rcl@{}} \dot{v} &=& \tfrac{1}{mv}\left( M_{\text{ext}}(v,\gamma)- \frac{i_{\textup{A}}}{r_{\textup{stat}}}M_{\text{brk}} \right. \end{array} $$

(24a)

$$\begin{array}{@{}rcl@{}} &&\left.+ \tfrac{i_{\text{A}}}{r_{\text{stat}}} \sum\limits_{j = 1}^{n_{\mu}} y_{j} \left( i_{\text{T}}(j) \eta_{\text{T}}(j)S\left( \tfrac{M_{\text{ind},j}}{y_{j}},\varepsilon\right) - M_{\text{fric}}\left( S\left( \tfrac{v_{j}}{y_{j}},\varepsilon\right), i_{\text{T}}(j)\right)\right)\right) \\ \dot{Q} &=& \sum\limits_{j = 1}^{n_{\mu}} y_{j} f_{Q}\left( S\left( \tfrac{v_{j}}{y_{j}},\varepsilon\right),S\left( \tfrac{M_{\text{ind},j}}{y_{j}},\varepsilon\right),i_{\text{T}}(j)\right) \end{array} $$

(24b)

and indicator constraints (23). After elimination of denominator $y_{j}$ occurrences where possible, remaining velocities in the denominators of $f_{v}$ and $f_{Q}$ are smoothed using (22).

Additionally, not lifting the term $\frac {1}{mv}$ even though v is an aggregate of the lifted velocities $v_{j}$ is justified by observing that

$$\sum\limits_{j = 1}^{n_{\mu}}(v_{j}\dot{v}_{j}) = \left( \sum\limits_{j = 1}^{n_{\mu}}v_{j}\right)\left( \sum\limits_{j = 1}^{n_{\mu}}\dot{v}_{j}\right)\quad \text{ if }~v_{i}\dot v_{k}= 0,~i\neq k. $$

In binary feasible points $y_{j}$, the condition $v_{i}\cdot \dot v_{k}= 0$ for $i\neq k$ is implied by feasibility of the constraint (21a).

3.8 Perspective and Minimal Lifting (PML)

Compared to Section 3.7, we reduce the number of lifted trajectories further using the projections $v_{j} = y_{j} v$ and $M_{\textup {ind},j} = y_{j} M_{\textup {ind}}$ as first suggested in [32, 33]. The single ODEs can be written as

$$y_{j} \dot{v} = \dot{v}_{j} = y_{j} f_{v}\left( y_{j}; v,M_{\text{ind},j},M_{\text{brk}},i_{\text{T}}(j), \eta_{\text{T}}(j),\gamma\right). $$

Summing up over j we obtain

$$\begin{array}{@{}rcl@{}} \dot{v} &=& \sum\limits_{j = 1}^{n_{\mu}} y_{j} f_{v}\left( y_{j}; v,M_{\text{ind},j},M_{\text{brk}},i_{\text{T}}(j), \eta_{\text{T}}(j),\gamma\right), \end{array} $$

(25a)

$$\begin{array}{@{}rcl@{}} \dot{Q} &=& \sum\limits_{j = 1}^{n_{\mu}} y_{j} f_{Q}\left( y_{j}; v,M_{\text{ind},j},i_{\text{T}}(j)\right). \end{array} $$

(25b)

As we do not use lifted velocities $v_{j}$ anymore, we formulate the indicator constraints using the smoothing-relaxation (17) and obtain the constraints (18). Again, the perspectives and the velocities in the denominators of $f_{v}$ and $f_{Q}$ are smoothed according Definition 3 and to (22).

4 Implicit Switching Formulations

In this section, we propose a new family of implicit approaches to MIOCP. The general idea is to reformulate problem (10) by eliminating the integer control through introduction of implicit, i.e., state-dependent switches, before solving it numerically. This way, we obtain a nonlinear optimal control problem with continuous domain of feasibility, but with implicitly discontinuous system dynamics. We consider the following class of problems:

Definition 5

(Switched system) In this article, we refer to the optimal control problem

$$\begin{array}{@{}rcl@{}} &&\min\limits_{\boldsymbol{x}(\cdot), \boldsymbol{u}(\cdot)}{e(\boldsymbol{x}(t_{\text{f}}))}\\ &&\text{s.t. }~\dot{\boldsymbol{x}}(t) = \boldsymbol{f}(\boldsymbol{x}(t), \boldsymbol{u}(t), \text{sign} \boldsymbol{\sigma}(\boldsymbol{x}(t))),\quad t \in [0, t_{\text{f}}]~\text{a.e.},\\ &&\qquad\boldsymbol{x}(0) = \boldsymbol{x}_{0},\\ &&\qquad\boldsymbol{0} \le \boldsymbol{d}(\boldsymbol{x}(t),\boldsymbol{u}(t)),\quad t\in [0, t_{\text{f}}]~\text{a.e}. \end{array} $$

(26)

with right-hand side function $\boldsymbol {f}$ depending on the sign structure of a vector-valued switching function $\boldsymbol {\sigma :} \mathbb {R}^{n_{\text {x}}}\to \mathbb {R}^{n_{\sigma }}$ that satisfies the transversality condition

$$ \lim\limits_{t\nearrow t_{\ast}}\frac{\text{d}\sigma_{j}}{\text{d}t}(\boldsymbol{x}(t))\lim\limits_{t\searrow t_{\ast}}\frac{\text{d}\sigma_{j}}{\text{d}t}(\boldsymbol{x}(t)) >0 $$

(27)

for all $t_{\ast }\in [0,t_{\text {f}}]$ with $\sigma _{j}(t_{\ast })= 0$ for some index $1\leq j \leq n_{\sigma }$, as a switched system control problem.

For the particular case of the truck MIOCP, we obtain a switched system by modeling the discrete gear choice using a fixed dependency on a differential state, e.g., the current velocity. Whenever certain switching velocities $\bar {v}$ are reached, a gear shift takes place.

Definition 6

(Switching velocity and set) The set $\bar {V}=\{\bar {v}_{1},\ldots ,\bar {v}_{n_{\mu }+ 1}\}$ is called switching set, if

$$v_{\min} = \bar{v}_{1} < \bar{v}_{2} < {\cdots} < \bar{v}_{n_{\mu}+ 1} = v_{\max} $$

and the gear $\mu (s)$ is chosen according to

$$\mu(s)=j \quad\Longleftrightarrow \quad v(s) \in [\bar{v}_{j},\bar{v}_{j + 1}) \quad\forall s \in [0,s_{\text{f}}] $$

for a given trajectory $v: [0,s_{\text {f}}] \mapsto \mathbb {R}$ and given $v_{\min }$ and $v_{\max }$. The elements $\bar {v}_{\mu }$ are called switching velocities.

4.1 Switching Velocities for Torque

We may define switching velocities for problem (10) based on any selected gear dependency. The gear choice enters the dynamics (1) and (2) as well as the constraints on the engine speed $n_{\text {eng}}$ (6) and on the indicated engine torque (7a). In fact, the gear choice selects from a number of possible modes, each of which is characterized by a different pair of values (i_T, η_T) and affects the algebraic variables $n_{\text {eng}}$, $M_{\text {ind}}^{\max }$, $f_{Q}$ and $M_{\text {fric}}$. Via the constraint on the engine speed n_eng (6), gear choice and velocity are linked. This results in restrictions on the switching velocities as shown in Fig. 1a.

Fig. 1

Details of implicit modeling

On the other hand, gear choice and velocity restrict the indicated engine torque $M_{\text {ind}}$ via the constraint (7a). The largest feasible domain for $M_{\text {ind}}$ is obviously obtained for the switching velocities that result in the maximum upper bound, as illustrated in Fig. 1b. This results in the following switching set $\bar V_{\text {M}_{\text {ind}}^{\max }}$:

μ	1	2	3	4	5	6	7	8
$\bar v_{\mu }$	$v_{\min }$	2.1767	2.6363	3.2093	3.9358	4.8226	5.8154	7.0174
μ	9	10	11	12	13	14	15	16
$\bar v_{\mu }$	8.2176	9.5819	11.6467	14.1881	17.3212	21.2210	25.6023	30.8988

4.2 Switching Velocities for Fuel Consumption

Another approach to determine a switching set $\bar {V}$ is to pick switching velocities according to $f_{Q}$. Such switching velocities help to minimize the fuel consumption Q that depends on $f_{Q}=f_{Q}(v,M_{\text {ind}},i_{\text {T}}(\mu ))$, c.f. (2). The behavior of the quotient is depicted in Fig. 1 for two different choices of ${M}_{\text {ind}}$. In Fig. 1a, $M_{\text {ind}}$ is fixed to $2,800~\text {Nm}$, a value that is often close to optimal in solutions using explicit formulations. In Fig. 1b, the control $M_{\text {ind}}$ is fixed to its maximum value ${M}_{\text {ind}}^{\max }$.

Figures 1 shows that the fuel consumption increases at a slower rate if higher gears are chosen. Hence, the fuel consumption can effectively be minimized by shifting to a higher gear at the earliest convenience, i.e., the lowest admissible velocity. This early switching may however also have an adverse affect. Choosing a high gear may prevent acceleration, or make it more costly. This line of thought is confirmed by the numerical results presented in Section 6. Hence, this approach for determining a switching set is discarded and we determine the switching set $\bar V_{\text {Q}}$ according to $f_{Q}$ by computing the intersection points of the curves in Fig. 1b.

μ	1	2	3	4	5	6	7	8
$\bar v_{\mu }$	$v_{\min }$	2.3095	2.7965	3.4047	4.173	5.1166	6.1695	7.4453
μ	9	10	11	12	13	14	15	16
$\bar v_{\mu }$	8.7239	10.1661	12.3530	15.0533	18.3689	22.5149	27.1612	32.7830

4.3 Further Switching Sets

Investigating $M_{\text {fric}}$ for switching points does not yield new insights because the engine friction is minimized, too, if the highest admissible gear is chosen. In order to obtain further switching sets for computational comparison, we define

$$\bar{V}_{\text{ave}}=\left\{\tfrac12\left( \bar{v}_{\text{Q},i}+\bar{v}_{\text{Mindmax},i}\right),~1 \leq i \leq 17\right\} $$

and via

$$\hat{v}_{i}:=\bar{v}_{\text{Q},i}-\bar{v}_{\text{ave},i}=\tfrac{1}{2}(\bar{v}_{\text{Q},i}-\bar{v}_{\text{ave},i}) $$

the sets

$$\begin{array}{@{}rcl@{}} \bar{V}_{\text{plus}}&=&\{\bar{v}_{\text{Q},i}+ 1\cdot\hat{v}_{i},~1 \leq i \leq 17\},\\ \bar{V}_{\text{pp}}&=&\{\bar{v}_{\text{Q},i}+ 2\cdot\bar{v}_{i},~1 \leq i \leq 17\},\\ \bar{V}_{\text{ppp}}&=&\{\bar{v}_{\text{Q},i}+ 4\cdot\bar{v}_{i},~1 \leq i \leq 17\}. \end{array} $$

For an overview, all calculated switching velocities are shown in Fig. 2a. Switching velocities are depicted as lower bounds for all gear choices to improve clarity of exposition. The switching velocity of gear j then is the upper bound on the velocity of gear $j-1$ according to condition (iii) of Definition 6.

Fig. 2

Visualization of switching velocity sets and switching functions

4.4 Switching Function

Given a set $\bar {V}$, we can determine the switching function $\boldsymbol {\sigma }$ that relates the current velocity $v(s)$ uniquely to the current gear choice $\mu (s)$.

Definition 7

(Switching function) A switching function for problem (5a) is a function

$$\boldsymbol{\sigma:}~[v_{\min},v_{\max}]\to \mathbb{R}^{n_{\mu}} $$

that satisfies transversality (27) and

$$\begin{array}{@{}rcl@{}} \text{sign} \sigma_{j}(v)= \left\{\begin{array}{l} + 1 \text{ if }~v \in (\bar{v}_{j},\bar{v}_{j + 1})\quad \stackrel{\text{Definition~6}}{\Longleftrightarrow} \quad \mu=j, \\ -1 ~~\text{otherwise.} \end{array}\right. \end{array} $$

In addition, we define the indicator functions

$$\tilde\sigma_{j}(v):=\frac12(\textup{sign} \sigma_{j}(v)+ 1)\in\{0,1\}. $$

This definition implies that $\tilde \sigma _{j}$ is a binary algebraic variable that equals 1 if and only if gear j is chosen. Hence, we have

$$ \mu(s)=\sum\limits_{j = 0}^{n_{\mu}} j\cdot \tilde\sigma_{j}(v(s)) \quad\forall s\in[0,s_{\text{f}}]. $$

As a consequence, the gear choice $\mu$ and all algebraic variables that depend on the gear choice are non-smooth step functions. For use with derivative-based solvers like the interior point code IPOPT [69], the resulting OCP violates the requirement of second order continuous differentiability, and this will in general cause convergence difficulties.

To address this issue, the smooth function

$$ \sigma_{j}(v) := \left( \tfrac{1}{\pi}\arctan(c_{\text{sw}}\cdot(v-\bar{v}_{j}))+\tfrac{1}{2}\right) \cdot \left( \tfrac{1}{\pi}\arctan(c_{\text{sw}}\cdot(\bar{v}_{j + 1}-v))+\tfrac{1}{2}\right), $$

(28)

with switching parameter $c_{\text {sw}} >0$ may be used in place of the switching indicator function $\tilde {\boldsymbol {\sigma }}$. As can be seen in Fig. 2b, this function meets Definition 7 for $c_{\text {sw}} \rightarrow \infty$. However, choosing $c_{\text {sw}}$ too big results in a large derivative when the current velocity is close to a switching velocity, which may also cause difficulties for derivative based solvers. As a compromise with regard to the equivalence of the implicit approach and the original problem formulation as well as the convergence properties of a derivative solver, we chose c_sw = 500 for the numerical results of Section 6.

4.5 Reformulation

As in the explicit approaches, the switching function can be used in an Inner Convexification or an Outer Convexification setting. By using

$$ \boldsymbol{g}(\boldsymbol{v}) = \sum\limits_{j = 1}^{n_{\mu}} \sigma_{j}(v(s)) (i_{\text{T}}(j), \eta_{\text{T}}(j))^{T} $$

analogously to (10), the IC formulations (11) and (12) can be used. Substituting $y_{j}$ by $\sigma _{j}(v(s))$ in (13), (14) provides OC formulations.

5 Dynamic Programming

All approaches described so far relied on the ability to compute a local minimum of a nonlinear program (NLP). In the course of our later assessment of the merits of these approaches, we are also interested in the quality of the local solutions obtained, i.e., in their distance from global optimality. A well-known path to (approximately) solving optimal control problems to global optimality is dynamic programming, see [6, 7, 9, 10], and [13].

5.1 Dynamic Programming

Dynamic programming computes optimal control trajectories by enumerating all possible control values. Hence, it relies on a discretized approximation of the control space, but cannot get stuck in local optima. Like all enumerative schemes, it suffers from the curse of dimensionality and may require excessive computational effort for larger instances. With some exceptions, e.g. [30], dynamic programming is seldom used for real-time optimization purposes, but has significant merit as a means of obtaining a reference value for comparison.

5.2 Bellman’s Principle of Optimality for MIOCP

DP is based on Bellman’s principle of optimality, c.f. [7], stating that “An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.” To describe this principle with formulas, we define the cost-to-go function for a MIOCP:

Definition 8

(Cost-to-go) The optimal cost-to-go function $J:[0,t_{\text {f}}]\times \mathbb {R}^{n_{\text {x}}} \to \mathbb {R}$ for the MIOCP of Definition 1, a starting time $\bar t\in [0,t_{\text {f}}]$, and an initial value ${\boldsymbol {\bar x}}\in \mathbb {R}^{n_{\text {x}}}$ reads

$$\begin{array}{@{}rcl@{}} J(\bar{t},\bar{\boldsymbol{x}}) &:=& \min\limits_{\boldsymbol{x}(\cdot), \boldsymbol{u}(\cdot)}{e(\boldsymbol{x}(t_{\text{f}}))}\\ &&\text{s.t. } \bigoplus\limits_{1 \leq i \leq n_{\omega}}~\left[ \begin{array}{c} Y_{i}(t)\\ \dot{\boldsymbol{x}}(t) = \boldsymbol{f}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}^{i}) \\ \boldsymbol{0} \le \boldsymbol{c}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}^{i}) \end{array} \right],\qquad t \in [\bar t, t_{\text{f}}]~\textup{a.e.},\\ &&\qquad \boldsymbol{0} \le \boldsymbol{d}(\boldsymbol{x}(t),\boldsymbol{u}(t)),\qquad t \in [\bar t, t_{\text{f}}]~\text{a.e.},\\ &&\qquad \boldsymbol{x}(\bar t) = \boldsymbol{\bar x}, \end{array} $$

Bellman’s principle of optimality implies that, for the time discretization grid $0=t_{0} < t_{1} < {\cdots } < t_{N}=t_{\text {f}}$, we have the following recurrence relation for the cost-to-go function:

$$J(t_{k},\boldsymbol{x}_{\boldsymbol{k}})=J(t_{k + 1},\boldsymbol{x}_{\boldsymbol{k + 1}}) + \min\limits_{\boldsymbol{x}(\cdot), \boldsymbol{u}(\cdot)} {\Phi}(t_{k + 1}; t_{k},\boldsymbol{x}_{\boldsymbol{k}},\boldsymbol{u}(\cdot)), $$

where the evaluation of the contribution ${\Phi }(t_{k + 1})$ on $[t_{k},t_{k + 1}]$ for a given initial value $\boldsymbol {x}_{\boldsymbol {k}}$ and control trajectories $\boldsymbol {u}(\cdot )$, $\boldsymbol {v}(\cdot )$ requires solving the boundary-value problem

$$\begin{array}{@{}rcl@{}} \boldsymbol{\dot x}(t) &=& \boldsymbol{f}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}(t)), \quad t \in [t_{k},t_{k + 1}]~\text{a.e.}, \\ \boldsymbol{0} &\le& \boldsymbol{c}(\boldsymbol{x}(t), \boldsymbol{u}(t), \boldsymbol{v}(t)), \\ \boldsymbol{0} &\le& \boldsymbol{d}(\boldsymbol{x}(t),\boldsymbol{u}(t)), \quad t \in [t_{k},t_{k + 1}]~\textup{a.e}.,\\ \boldsymbol{x}(t_{k}) &=& \boldsymbol{x}_{\boldsymbol{k}}, \\ \boldsymbol{x}(t_{k + 1}) &=&\boldsymbol{x}_{k + 1}. \end{array} $$

Furthermore, $J(t_{N},\boldsymbol {x}_{\boldsymbol {N}})=e(\boldsymbol {x}_{N})$ provides a starting point and minimizing the function $J(t_{0},\boldsymbol {x}_{\boldsymbol {0}})$ over all admissible values for $\boldsymbol {x}_{\boldsymbol {0}}$ yields the optimal objective function value and the solution of problem (1).

5.3 Dynamic Programming Algorithm for MIOCP

The main idea of dynamic programming is to compute all values $J(t_{k},\boldsymbol {x}_{\boldsymbol {k}})$ in a backward loop $k=N,N-1,\ldots ,0$ that determines the resulting states $\boldsymbol {x}_{\boldsymbol {k}}$ and optimal controls $\boldsymbol {u}(\cdot )$ on $t \in [t_{k},t_{k + 1}]$. To this end, we introduce appropriately chosen discrete subsets $X_{\text {D}}\subset X$, $U_{\text {D}}\subset U$ of the bounded admissible state space $X\subset \mathbb {R}^{n_{\text {x}}}$ and control space $U\subset \mathbb {R}^{n_{\text {u}}}$,

$$X_{\text{D}} := \{\boldsymbol{x}^{\boldsymbol{1}},\ldots,\boldsymbol{x}^{N_{\text{x}}}\},\quad U_{\text{D}} := \{\boldsymbol{u}^{\boldsymbol{1}},\ldots,\boldsymbol{u}^{N_{\text{u}}}\}, $$

let $\boldsymbol {u}(t):=\boldsymbol {u}_{k}$ on $t \in [t_{k},t_{k + 1}]$, and examine the sets $X_{\text {D}}$, $U_{\text {D}}$ and ${\Omega }$ by exhaustive search as follows:

A fixed initial value and/or small admissible state or control domains accelerate the algorithm. It is easy to see that Algorithm 1 has a runtime complexity of $\mathscr{O}(N \cdot N_{x}\cdot N_{u}\cdot n_{\omega })$ and a storage requirement of $\mathscr{O}(N\cdot N_{x})$ memory locations. For a uniform discretization granularity ${\Delta }$ of $X\subset \mathbb {R}^{n_{\text {x}}}$, we observe $N_{\text {x}}\in \mathscr{O}({\Delta }^{n_{\text {x}}})$, and the same is true for the control spaces. Hence, both computational effort and memory requirements grow exponentially with the number of states $n_{\text {x}}$ and the numbers of continuous controls $n_{\text {u}}$. This observation is often referred to as curse of dimensionality. The discrete choices, however, are easily included in the enumeration scheme. For more details on dynamic programming, we refer the reader to Bellman [6, 7] and, e.g., Bertsekas [9, 10].

To accelerate the algorithm, it is possible to terminate the for-loop(s) early if the solution clearly becomes infeasible. For example, the ODE system need not be solved if the particular new gear choice is found to violate the engine speed constraint (6) for the given current velocity. Furthermore, monotonicity properties may be used, i.e., if a given value of the engine torque is found to result in a new velocity in violation of the upper bound, even larger values of the engine torque need not be examined. On top of this, results of the ODE solver are stored in look-up tables to avoid repeating multiple identical computations. For more details on the efficient implementation we used, see Buchner [12].

6 Numerical Results and Comparison

6.1 Scenarios, Initial Values, and Parameter Values

All problem parameters and initial values, such as the number of gears $n_{\mu } = 16$ or $v_{0} = v_{\text {des}} = 22.2 \frac {\text {m}}{\text {s}}$, can be found on the web page mintoc.de, a benchmark library for MIOCPs [56]. We consider two scenarios, for which the numerical data can also be found on mintoc.de.

Scenario 1 is characterized by a linear slope on the first half of the horizon, and a general speed limit of $27.8 \frac {\text {m}}{\text {s}} \approx 100 \frac {\text {km}}{\text {h}}$, cf. the left-hand part of Fig. 3. The weights for the objective are set to $\lambda _{\text {d}}= 1.0$, $\lambda _{\text {f}}= 25.0$, and $\lambda _{\text {c}}= 1.0$, i.e., we primarily minimize fuel consumption. In Scenario 2 the truck has to transit a valley. The speed on the way down is limited to $22.2 \frac {\text {m}}{\text {s}} \approx 80 \frac {\text {km}}{\text {h}}$ as can be seen on the right-hand side of Fig. 3. For this scenario, we set $\lambda _{\text {d}}= 100.0$, $\lambda _{\text {f}}= 10.0$, i.e., the main aspect is to minimize the deviation of velocity from the desired one. The considered horizons have a length of 1000m in both scenarios, which was shown to be a good prediction horizon in a moving horizon context, [12].

Fig. 3

Track elevations and velocity limits of the considered scenarios

6.2 Implementation Details

To make the numerical results as comparable as possible, we use an identical discretization throughout. All optimal control problems are discretized on the same grids, using 40 equidistant intervals for the piecewise constant controls (i.e., 25m) and 400 equidistant intervals for the states. The dynamics are discretized using an implicit Euler method. Due to the different algorithmic approaches a comparison of solutions has to consider numerical errors, compare Fig. 4.

Fig. 4

Impact of rounding to state discretization grid in Dynamic Programming. Shown are the deviations of a forward simulation from the rounded values using ${\Delta } v = 0.05 \frac {\text {m}}{\text {s}}$ for Scenario 1 and Scenario 2 . This error makes an accurate comparison difficult

All results in this article were computed on a single core of a x64-based Intel(R) Xeon(TM) E5-2640 v3 CPU with 2.60GHz and 32GB memory. For the solution of the direct collocation problems of all explicit and implicit formulations, we used IPOPT 3.12.4 [69] with standard solver options, invoked from 64-bit AMPL [20] version 20171002. The Dynamic Programming solution was obtained from a C++ implementation of Algorithm 1.

6.3 Comparison of Solutions

For the assessment of solutions, we use the indicators fractionality and feasibility that measure the violation of the integrality constraints $y_{j} \in \{0,1\}$ and of the gear-dependent model constraints (6) and (7a).

Definition 9

(Fractionality of solutions) The fractionality of piecewise constant control functions $y_{j}: [0,s_{\text {f}}] \mapsto [0,1]$ on a grid $0=s_{0} < {\cdots } < s_{N}=s_{\text {f}}$ is given by the value

$$\frac{1}{N}\sum\limits_{i = 0}^{N-1}\sum\limits_{j = 1}^{n_{\mu}}(0.5-|y_{j}(s_{i})-0.5|). $$

Definition 10

(Infeasibility of solutions) The infeasibility of states v and piecewise constant controls $M_{\text {ind}}, \boldsymbol {y}$ on a grid $0=s_{0} < {\cdots } < s_{N}=s_{\text {f}}$ is given by the value

$$\frac{1}{3(N + 1)n_{\mu}} \sum\limits_{i = 0}^{N} \sum\limits_{j = 1}^{n_{\mu}} \sum\limits_{k = 1}^{3} \max\{0,y_{j}(s_{i}) {\delta^{k}_{j}}(s_{i})\} $$

Table 1 Results of all approaches, compare Section 6.3 for explanation. Fractionality and infeasibility of the integer solutions are 0 by construction. Dynamic Programming results directly in integer controls. (i infeasible, m maximum number of iterations exceeded, p presolve)

with the residuals of the indicator constraints

$$\begin{array}{@{}rcl@{}} {\delta^{1}_{j}}(s_{i}) &=& M_{\text{ind}}(s_{i})-M_{\text{ind}}^{\max}(v(s_{i}), i_{\text{T}}(j)), \\ {\delta^{2}_{j}}(s_{i}) &=& n_{\text{eng}}^{\min} - n_{\text{eng}}(v(s_{i}), i_{\text{T}}(j)), \\ {\delta^{3}_{j}}(s_{i}) &=& n_{\text{eng}}(v(s_{i}), i_{\text{T}}(j)) - n_{\text{eng}}^{\max}. \end{array} $$

Definition 11

(Relaxed solutions) For explicit approaches of Section 3, we call the solution of a control problem relaxed, if the constraints $y_{j}(s) \in \{0,1\}$ have been relaxed to $y_{j}(s) \in [0,1]$ for all $j \in \{1, \ldots , n_{\mu }\}$ and all $s \in [0,s_{\text {f}}]$. For implicit approaches of Section 4 relaxation refers to the use of the smoothed switching functions $\sigma _{j}(v) \in [0,1]$. Typically, relaxed solutions have fractionality and infeasibility larger zero.

Definition 12

(Integer solutions) We call a solution integer solution, if a relaxed solution is rounded by setting the largest of all $n_{\mu }$ entries of either $\boldsymbol {y}(s)$ or $\boldsymbol {\sigma }(s)$ to 1, all others to 0. The continuous controls and states are optimized in a second optimization run to obtain feasibility with respect to all constraints in (10). For the implicit approach, the additional constraints

$$\sum\limits_{j = 1}^{n_{\mu}} \sigma_{j}(s) \bar{v}_{j} \le v(s) \le \sum\limits_{j = 1}^{n_{\mu}} \sigma_{j}(s) \bar{v}_{j + 1} $$

are included. If integer solutions are feasible, they have a fractionality and infeasibility of zero.

Note that different strategies to obtain integer solutions from relaxed solutions for MIOCPs have been proposed in the literature, such as combinatorial integral approximation [34, 59]. We do not apply and compare these strategies here to focus on the main aspect, the tightness of relaxations. We shortly summarize all formulations for the truck problem (10) that are compared in Table 1.

IC :

Inner Convexification as described in Section 3.1 has differential states v, Q and controls $M_{\text {ind}}$, $M_{\text {ind}}$, $\boldsymbol {y}$. The dynamics are specified by (11), the indicator constraints are given by (12).

OC :

Outer Convexification (Section 3.2) is identical to IC, but with dynamics (13) and indicator constraints (14).

bigM :

The Big-M approach (Section 3.3) is identical to OC, but with indicator constraints (14).

relVC :

The relaxed Vanishing Constraint approach (Section 3.4) is identical to OC, but with indicator constraints (16) that are relaxed by $\varepsilon$. The value of $\varepsilon$ is reduced by a homotopy from $10^{5}$ to $10^{-4}$ in multiplicative steps of 0.6, using solutions as initialization for the next problem. For details on the homotopy, see [33].

smoVC :

The smoothed Vanishing Constraint approach (Section 3.5) is identical to relVC (also with a similar homotopy), but with indicator constraints (16) that are $\varepsilon$-smoothened using an NCP function.

PFL, PPL, PML:

The Perspective approaches (Sections 3.6, 3.7, and 3.8) are obtained by lifting the Outer Convexification formulation and, for PPL and PML, by subsequent aggregation.

Implicit Approaches :

All implicit approaches (Section 4) use an OC formulation of the dynamics and of the constraints, substituting $y_{j}$ by $\sigma _{j}(v(s))$ in (13) and (14). They differ in the choice of the switching velocity sets $\bar {V}_{\text {Mindmax}}$, $\bar {V}_{\text {ave}}$, $\bar {V}_{\text {Q}}$, $\bar {V}_{\text {plus}}$, $\bar {V}_{\text {pp}}$, and $\bar {V}_{\text {ppp}}$.

Dynamic Programming :

Five different discretizations ${\Delta } v$ of the state v and ${\Delta } M$ of the engine torque M were applied for an enumeration of the admissible state space $X\subset \mathbb {R}^{n_{\text {x}}}$ and control space $U\subset \mathbb {R}^{n_{\text {u}}}$ (Section 5).

Further combinations like using OC dynamics (13) and IC constraints (12), or using implicit approaches based on IC dynamics and constraints are possible. They are not promising, though, as Fig. 5 shows for the case of implicit switching.

Fig. 5

$M_{\text {ind}}^{\max }$ as a function of velocity with exact switching , IC-like switching and OC-like switching , using $\bar {V}_{\text {Mindmax}}$. IC leads to undesirable spikes

6.4 Discussion

The numerical results for the different approaches and the two scenarios are shown in Table 1 and Figs. 6, 7, 8, and 9. The figures show relaxed gear choices using grey intensities, overlayed with the resulting velocity profiles.

Fig. 6

Velocities and gear choices for scenario 1 and explicit approaches

Fig. 7

Velocities and gear choices for scenario 1 and implicit and two DP approaches

Fig. 8

Velocities and gear choices for scenario 2 and explicit approaches

Fig. 9

Velocities and gear choices for scenario 2 and implicit and two DP approaches

Concerning computational times, IC, OC, and bigM are close to being real-time feasible with a CPU times on the order of a few seconds. The other explicit approaches and implicit approaches show CPU times around one minute. The perspective formulation PFL could not be brought to convergence for both Scenarios evaluated. A possible explanation for this adverse behavior of the nonlinear optimization method may be found in the ill-posedness of the perspective of a nonlinear nonconvex function near the points $y = 0$, which appears to persist even after smoothing. Aggregation of variables helps to ameliorate the situation, as is seen in Scenario 2 where both aggregated variants PPL and PML converge after several minutes. Expectedly, the runtimes of Dynamic Programming increase exponentially due to the curse of dimensionality.

Looking at the relaxed solutions, bigM and IC result in small objective function values at the price of high values for fractionality and infeasibility. Looking at the relaxed gear choices in Figs. 6 and 8, one observes the unphysical combination of low and high gears which result in very poor performance when rounding. This is due to large deviations between relaxed and rounded velocity (compare Figs. 6 and 8). This situation is much improved for OC, where both velocities are similar. This result is also expected from the supporting approximation theorem, c.f. [57].

Slightly higher objective function values for the relaxed problems in smoVC and relVC are justified by very small fractionality and numerically zero infeasibility. The obtained solutions come at the expense of slightly increased runtime due to the homotopy approach for smoothing-relaxation. Most importantly, they can be rounded to integer feasible solutions with an almost identical function value. These solution approaches are ranked best among the explicit ones for both Scenarios.

For the implicit approaches, rounded solutions are similar to the relaxed ones. Concerning performance, however, a more diffuse picture emerges. For scenario 1, two approaches lead to convergence to infeasible points, and none of the objective function values is competetive. For scenario 2, however, the four lowest objective function values result from implicit approaches. The relaxed solutions are slightly infeasible (infeas. $\approx 2.5$), though.

The solution quality of Dynamic Programming results strongly depends on the underlying discretization grid. The enumerative nature of the subproblems and the curse of dimensionality impair using discretizations that are fine enough to compete with the local optimization approaches. In addition, as shown in Fig. 4, the solutions come with an additional mismatch when exact forward simulation is used.

7 Conclusion

An explicit approach using outer convexification for the dynamics and a good way to treat the vanishing constraints outperformed implicit formulations and dynamic programming concerning computational time, performance, and robustness of solution quality. Better algorithms to numerically solve optimization problems with vanishing constraints need to be developed to reliably harness these advantages also in larger scale applications.