betaFeedback

WorksMathematics

Real-Time Nonlinear Mixed-Integer Model Predictive Control With Horizon-Tail Relaxations

Abstract

Model predictive control (MPC) of nonlinear systems with discrete decisions leads to mixed-integer nonlinear programs (MINLPs) whose combinatorial complexity often prevents real-time deployment. In this paper, we propose a decomposition-based MPC method that reorders and reduces computations to shorten the delay between receiving a state measurement and applying the control input. Before the measurement arrives, we solve a continuous relaxation of the MINLP at a predicted state and construct a mixed-integer quadratic program (MIQP). Once the measured state is available, we solve the MIQP that reconstructs the discrete controls and simultaneously performs one sequential quadratic programming step toward the corresponding nonlinear solution. To reduce the combinatorial complexity in the horizon length, we either fix the integer controls or relax their integrality over the prediction horizon tail, while retaining an integer-feasible first control input. We derive error bounds relating the nonlinear objective values obtained with the horizon-tail approximations to the optimal value of the original mixed-integer problem. In a data center cooling example, the proposed method reduces mean feedback computation time by 94% relative to a state-of-the-art MINLP method with a total closed-loop cost difference of less than 1%.

Introduction

Model predictive control (MPC) is a feedback control strategy that repeatedly solves optimal control problems. Its appeal lies in its ability to directly specify objectives and constraints while using predictive models to anticipate the effects of control decisions. MPC algorithms are well established for linear and nonlinear systems with continuous control inputs [1]. Yet, many real-world systems also require discrete controls.

Combined with nonlinear dynamics, these discrete decisions give rise to nonlinear mixed-integer optimal control problems (MIOCPs), whose time discretization yields mixed-integer nonlinear programs (MINLPs). Generic MINLP solvers [2], even when terminated early, are usually too slow for real-time MPC deployment. Particularly for nonlinear systems, this has motivated methods tailored to MIOCPs that rapidly compute high-quality approximate solutions, often with well-understood theoretical properties. These methods include, for example, switching-time optimization [3, 4], decomposition methods [5, 6] or machine-learning-based approaches [7, 8, 9].

Decomposition methods for MIOCPs solve continuous nonlinear programs (NLPs) related to the original MINLP, combined with a discrete reconstruction step [5, 6, 10], yielding high-quality approximations with well-understood error bounds [5, 6]. Discrete reconstruction recovers the integer controls using different methods ranging from OCP-tailored rounding [10] and variants accommodating dwell-time constraints [11, 12] to integer programming [5, 13] and tailored shortest-path methods incorporating combinatorial constraints [14]. However, recovering integer controls without explicitly accounting for their effects on the dynamics can cause performance losses or infeasibility on coarse time-discretization grids [15]. Reconstruction through a mixed-integer quadratic program (MIQP) incorporates local approximations of the dynamics and objective, improving solution quality at greater computational cost [16]. For real-time MPC, this trade-off motivates further approximations that reduce computation while preserving solution quality, a direction pursued in this paper.

Optimization problem solution approximations are already standard in real-time MPC with continuous controls, where their theoretical properties are well understood [17]. Rawlings and Risbeck Rawlings and Risbeck [18] show how these properties extend conceptually to approximate mixed-integer MPC. This motivates us to adapt algorithmic ideas from real-time continuous MPC to the mixed-integer setting [1].

A shared idea in many of these algorithms is to reorder optimization computations to reduce the feedback delay [1]. The computations are split into a preparation phase, which performs operations before the next state measurement xˉ0\bar{x}_0 is known, such as evaluating functions and derivatives or presolving related problems, and a feedback phase, which computes a suitable control approximation with minimal effort once xˉ0\bar{x}_0 is known. Advanced-step methods compute in the preparation phase an (approximate) solution of the MPC problem at a predicted state x~0\tilde{x}_0 [19, 20, 21].

In this paper, we adapt these ideas to mixed-integer MPC by reordering and reducing the computations of decomposition algorithms. In the preparation phase, we solve the continuous relaxation of the MINLP, and optionally an MIQP at a predicted advanced state x~0\tilde{x}_0. In the feedback phase, we update the prepared MIQP with the measured state xˉ0\bar{x}_0 and solve it using the available warm start. To reduce the MIQP’s combinatorial complexity, we either fix the integer controls or relax their integrality over the prediction horizon tail. This

The author thanks Nathalie Janes and Moritz Diehl for interesting discussions on mixed-integer optimal control. OpenAI’s Code was used to assist with drafting and language editing, as well as implementing the accompanying code. The author reviewed and verified all AI-assisted content and takes full responsibility for the final manuscript and results. reduces the feedback delay while providing bounds on the resulting performance losses.

Contributions. The main contributions of this paper are: (i) a real-time mixed-integer nonlinear MPC method that separates preparation and feedback computations, combining integer reconstruction and one SQP step in a single MIQP; (ii) two horizon-tail approximations that fix integer controls or relax their integrality beyond a selected horizon, reducing the combinatorial search while retaining an integer-feasible first control input; (iii) bounds relating the nonlinear objective values obtained with these approximations to the globally optimal value of the original MINLP; (iv) a numerical comparison with a state-of-the-art MINLP method and a rule-based controller on a data center cooling example; and (v) an open-source implementation supporting several algorithmic variants and several MPC examples from the literature.2

Decomposition methods for MIOCP

In this section, we state the MIOCP of interest, and recall a standard decomposition method for solving such problems.

Problem formulation

We consider a discrete-time nonlinear system with states xk∈Rnxx_k \in\mathbb{R}^{n_x}, continuous controls uk∈Rnuu_k \in\mathbb{R}^{n_u}, and binary controls vk∈{0,1}nvv_k \in\{0,1\}^{n_v}. General bounded integer controls can be encoded by binary variables, so this restriction is without loss of generality. For an initial state xˉ0\bar{x}_0 and a horizon of NN intervals, define x=(x0,…,xN)x = (x_0,\ldots,x_N), u=(u0,…,uN−1)u = (u_0,\ldots,u_{N-1}), and v=(v0,…,vN−1)v = (v_0,\ldots,v_{N-1}), to be the discrete-time states and controls. The MIOCP is stated as follows:

min⁡x,u,v∑k=0N−1ℓk(xk,uk,vk)+ℓN(xN)s.t.x0=xˉ0,xk+1=fk(xk,uk,vk),k=0,…,N−1,hk(xk,uk,vk)≤0,k=0,…,N−1,vk∈{0,1}nv,k=0,…,N−1,v∈P.(1)\begin{aligned} \min_{x,u,v}\quad& \sum_{k=0}^{N-1} \ell_k(x_k,u_k,v_k) + \ell_N(x_N) \\ \text{s.t.}\quad& x_0 = \bar{x}_0, \\ & x_{k+1} = f_k(x_k,u_k,v_k), \quad k=0,\ldots,N-1, \\ & h_k(x_k,u_k,v_k) \le0, \quad k=0,\ldots,N-1, \\ & v_k \in\{0,1\}^{n_v}, \quad k=0,\ldots,N-1, \\ & v \in\mathcal{P}. \tag*{(1)} \end{aligned}

Here, ℓk:Rnx×Rnu×{0,1}nv→R\ell_k : \mathbb{R}^{n_x} \times\mathbb{R}^{n_u} \times\{0,1\}^{n_v} \to\mathbb{R} is the stage cost and ℓN:Rnx→R\ell_N : \mathbb{R}^{n_x} \to\mathbb{R} is the terminal cost. The map fk:Rnx×Rnu×{0,1}nv→Rnxf_k : \mathbb{R}^{n_x} \times\mathbb{R}^{n_u} \times\{0,1\}^{n_v} \to\mathbb{R}^{n_x} denotes the discrete-time state-transition map. The functions hk:Rnx×Rnu×{0,1}nv→Rnhkh_k : \mathbb{R}^{n_x} \times\mathbb{R}^{n_u} \times\{0,1\}^{n_v} \to\mathbb{R}^{n_{h_k}} collect the path inequality constraints. The polyhedron P⊆[0,1]Nnv\mathcal{P} \subseteq[0,1]^{Nn_v} contains additional combinatorial constraints coupling several control intervals, e.g., dwell-time constraints [12].

Next, we define a few shorthands. We aggregate the binary controls as y:=v∈{0,1}nyy := v \in\{0,1\}^{n_y}, where ny=Nnvn_y = Nn_v, and collect the continuous primal variables into w:=(x,u)∈Rnww := (x,u) \in\mathbb{R}^{n_w}. Including the bounds in its linear representation, we write P={y∈Rny∣Ay≤b}\mathcal{P} = \{y \in\mathbb{R}^{n_y} \mid Ay \le b\}. The feasible binary set is Y:=P∩{0,1}ny\mathcal{Y} := \mathcal{P} \cap\{0,1\}^{n_y}. The vector p∈Rnpp \in\mathbb{R}^{n_p} denotes the parameter, in our case, without loss of generality, this is the initial state p=xˉ0p = \bar{x}_0. Let GG collect the equality constraints in (1b) and (1c), and let HH collect the inequality constraints in (1d). A function FF is a generic nonlinear function collecting the stage and terminal costs in (1). In the remainder of this and the next section, we assume that the parameter pp is fixed. Using this notation, problem (1) can be written compactly as

min⁡y,wF(y,w)s.t.G(y,w;p)=0,H(y,w)≤0,y∈Y.(2)\begin{aligned} \min_{y,w}\quad& F(y,w) \\ \text{s.t.}\quad& G(y,w;p) = 0, \\ & H(y,w) \le0, \\ & y \in\mathcal{Y}. \tag*{(2)} \end{aligned}

It will be later useful to define a standard NLP where y∈Py \in\mathcal{P} is a parameter and not a decision variable:

JNLP(y):=min⁡wF(y,w)s.t.G(y,w;p)=0,H(y,w)≤0.(3)\begin{aligned} J_{\mathrm{NLP}}(y) := \min_w\quad& F(y,w) \\ \text{s.t.}\quad& G(y,w;p) = 0, \\ & H(y,w) \le0. \tag*{(3)} \end{aligned}

Here, JNLP(y)J_{\mathrm{NLP}}(y) denotes the optimal value function of this NLP. Note that we can compactly express the integer part of the MINLP (2) solution as [16]:

y∘=arg⁡min⁡yJNLP(y)s.t. y∈Y.(4)y^\circ= \arg\min_y J_{\mathrm{NLP}}(y) \quad\text{s.t. } y \in\mathcal{Y}. \tag*{(4)}

A relaxed integer solution y∗y^*, and thus a lower bound for JNLP(y∗)≤JNLP(y∘)J_{\mathrm{NLP}}(y^*) \le J_{\mathrm{NLP}}(y^\circ) is obtained by solving the relaxed MINLP (2), compactly written as: y∗=arg⁡min⁡yJNLP(y)y^* = \arg\min_y J_{\mathrm{NLP}}(y) s.t. y∈Py \in\mathcal{P}.

A three-phase decomposition method

For optimal control and MPC applications, decomposition methods typically compute high-quality approximate solutions of (2) more efficiently than generic MINLP methods [5, 6, 10]. The decomposition method introduced by Sager [10] consists of three steps: solve a relaxation of the MINLP, integer reconstruction, and nonlinear polishing. Following the exposition in [16], these steps are:

(S1) The integrality condition in (2) is relaxed by replacing Y\mathcal{Y} with P⊆Rny\mathcal{P} \subseteq\mathbb{R}^{n_y}, yielding a nonlinear program (NLP). A local minimizer of this NLP is denoted by (y∗,w∗)(y^*,w^*), where y∗∈Py^* \in\mathcal{P} but not necessarily y∗∈Yy^* \in\mathcal{Y}. If y∗∈Yy^* \in\mathcal{Y}, then steps two and three are omitted.

(S2) An integer solution y^∈Y\hat{y} \in\mathcal{Y} is reconstructed by minimizing a distance function:

y^∈arg⁡min⁡y∈Yd(y,y∗).(5)\hat{y} \in\arg\min_{y \in\mathcal{Y}} d(y,y^*). \tag*{(5)}

(S3) The integer variables are fixed to y=y^y = \hat{y}, and the resulting NLP (3), referred to as the polishing NLP, is solved. Whenever this NLP admits a solution w∗(y^)w^*(\hat{y}), the pair (y^,w∗(y^))(\hat{y},w^*(\hat{y})) is feasible for (2).

This procedure typically yields a pair (y^,w∗(y^))(\hat{y},w^*(\hat{y})) that is locally optimal for the fixed-integer NLP (3) and feasible, but generally suboptimal, for the MINLP (2). Let (y∘,w∘)(y^\circ,w^\circ) denote a global minimizer of (2). If the continuous relaxation is solved globally, the optimal values satisfy JNLP(y∗)≤JNLP(y∘)≤JNLP(y^)J_{\mathrm{NLP}}(y^*) \le J_{\mathrm{NLP}}(y^\circ) \le J_{\mathrm{NLP}}(\hat{y}) [16]. Any local minimizer (y∗,w∗)(y^*,w^*) of the relaxed NLP can also be used for integer reconstruction in (S2), although the first inequality does not necessarily hold anymore. The practical performance and computational complexity of decomposition methods depend strongly on the choice of the distance function d(y;y∗)d(y;y^*). In the remainder of the section, we review existing choices for dd. In Sec. III we propose new ones tailored to MPC, and establish their relations to JNLP(y∘)J_{\mathrm{NLP}}(y^\circ).

Ideal distance function

The ideal choice for the distance function is dNLP(y;y∗):=JNLP(y)−JNLP(y∗)d_{\mathrm{NLP}}(y;y^*) := J_{\mathrm{NLP}}(y)-J_{\mathrm{NLP}}(y^*). If y∗y^* is a global solution of the continuous relaxation, this function is nonnegative for all y∈Yy \in\mathcal{Y}, since JNLP(y∗)≤JNLP(y)J_{\mathrm{NLP}}(y^*) \le J_{\mathrm{NLP}}(y). Because JNLP(y∗)J_{\mathrm{NLP}}(y^*) is constant, solving (5) with this choice is equivalent to solving (4), and hence the original MINLP (2). This choice is therefore usually intractable and we look for more tractable approximations of dNLP(y;y∗)d_{\mathrm{NLP}}(y;y^*).

Combinatorial integral approximation (CIA) distance

A simpler choice is d(y;y∗):=∥y−y∗∥qd(y;y^*) := \lVert y-y^*\rVert_q, which yields a mixed-integer linear programming (MILP) formulation of (5) for q=1q=1 or q=∞q=\infty. The frequently used CIA norm dCIA(y;y∗):=∥U(y−y∗)∥∞d_{\mathrm{CIA}}(y;y^*) := \lVert U(y-y^*)\rVert_\infty, with an invertible matrix UU defined in [5], also admits an MILP formulation. If P=Rny\mathcal{P}=\mathbb{R}^{n_y}, sum-up rounding provides a polynomial-time solution to the CIA problem under suitable assumptions [5 Theorem 3]. Norm-based distance functions are attractive for their computational efficiency, as they admit tailored solution methods, such as those implemented in pycombina [13], which we use in this work. On the downside, such approximations reconstruct y^\hat{y} based solely on y∗y^*, disregarding w∗w^* or the nonlinear dynamics and constraints, which can lead to performance losses [15].

Quadratic-model distance

Since minimizing d(y;y∗):=JNLP(y)−JNLP(y∗)d(y;y^*) := J_{\mathrm{NLP}}(y)-J_{\mathrm{NLP}}(y^*) over Y\mathcal{Y} is computationally intractable, [16] proposes a quadratic approximation of JNLP(y)J_{\mathrm{NLP}}(y), turning (5) into an MIQP. We recall this approximation here and further adapt it in Sec. III.

Define the Lagrangian of the fixed-yy NLP (3) as

L(y,w,λ,μ;p):=F(y,w)+λ⊤G(y,w;p)+μ⊤H(y,w).\mathcal{L}(y,w,\lambda,\mu;p):=F(y,w)+\lambda^{\top}G(y,w;p)+\mu^{\top}H(y,w).

The Lagrangian of the continuous relaxation of (2) is Lrel(y,w,λ,μ,ρ;p):=L(y,w,λ,μ;p)+ρ⊤(Ay−b)\mathcal{L}_{\mathrm{rel}}(y,w,\lambda,\mu,\rho;p):=\mathcal{L}(y,w,\lambda,\mu;p)+\rho^{\top}(Ay-b). Since the additional term is affine in yy, both Lagrangians have the same Hessian with respect to (y,w)(y,w). At a Karush–Kuhn–Tucker (KKT) point (y∗,w∗,λ∗,μ∗,ρ∗)(y^*,w^*,\lambda^*,\mu^*,\rho^*) of the relaxed NLP in (S1), we approximate this Hessian by a symmetric positive definite matrix B:=B(y∗,w∗,λ∗,μ∗)≻0B:=B(y^*,w^*,\lambda^*,\mu^*)\succ0. With Δy:=y−y∗\Delta y:=y-y^* and Δw:=w−w∗\Delta w:=w-w^*, define the linearization of FF compactly as

FL(y,w;y∗,w∗):=F(y∗,w∗)+∇(y,w)F(y∗,w∗)⊤[ΔyΔw].F_{\mathrm{L}}(y,w;y^*,w^*):=F(y^*,w^*)+\nabla_{(y,w)}F(y^*,w^*)^{\top}\begin{bmatrix}\Delta y\\ \Delta w\end{bmatrix}.

The linearizations GL(y,w;p,y∗,w∗)G_{\mathrm{L}}(y,w;p,y^*,w^*) and HL(y,w;y∗,w∗)H_{\mathrm{L}}(y,w;y^*,w^*) are defined analogously. Furthermore, a quadratic approximation of the objective of (2) using B≻0B\succ0 is defined as

FQP(y,w;y∗,w∗,B):=FL(y,w;y∗,w∗)+12[ΔyΔw]⊤B[ΔyΔw].F_{\mathrm{QP}}(y,w;y^*,w^*,B):=F_{\mathrm{L}}(y,w;y^*,w^*)+\frac{1}{2}\begin{bmatrix}\Delta y\\ \Delta w\end{bmatrix}^{\top}B\begin{bmatrix}\Delta y\\ \Delta w\end{bmatrix}.

For the linearization point (y∗,w∗)(y^*,w^*), the MIQP approximation of (2) reads

min⁡y,wFQP(y,w;y∗,w∗,B)s.t.GL(y,w;p,y∗,w∗)=0,HL(y,w;y∗,w∗)≤0,y∈Y.(6)\begin{aligned} \min_{y,w}\quad&F_{\mathrm{QP}}(y,w;y^*,w^*,B)\\ \text{s.t.}\quad&G_{\mathrm{L}}(y,w;p,y^*,w^*)=0,\\ &H_{\mathrm{L}}(y,w;y^*,w^*)\le0,\\ &y\in\mathcal{Y}. \tag*{(6)} \end{aligned}

In analogy to (3), for fixed yy, the quadratic value function is defined as

JQP(y;y∗,w∗,B):=min⁡wFQP(y,w;y∗,w∗,B)s.t.GL(y,w;p,y∗,w∗)=0,HL(y,w;y∗,w∗)≤0.(7)\begin{aligned} J_{\mathrm{QP}}(y;y^*,w^*,B)&:=\min_w\quad F_{\mathrm{QP}}(y,w;y^*,w^*,B)\\ \text{s.t.}\quad&G_{\mathrm{L}}(y,w;p,y^*,w^*)=0,\\ &H_{\mathrm{L}}(y,w;y^*,w^*)\le0. \tag*{(7)} \end{aligned}

For B≻0B\succ0, JQPJ_{\mathrm{QP}} is convex, continuous, and piecewise quadratic in yy on its feasible domain [16]. Moreover, JQP(y;y∗,w∗,B)J_{\mathrm{QP}}(y;y^*,w^*,B) approximates JNLP(y)J_{\mathrm{NLP}}(y), with an error bound given in Lemma 1 below. For fixed pp, the quadratic-model distance is defined as

dQP(y;y∗,w∗,B):=JQP(y;y∗,w∗,B)−JNLP(y∗).(8)d_{\mathrm{QP}}(y;y^*,w^*,B):=J_{\mathrm{QP}}(y;y^*,w^*,B)-J_{\mathrm{NLP}}(y^*). \tag*{(8)}

The relaxed NLP’s KKT point (y∗,w∗)(y^*,w^*) also satisfies the KKT conditions of the MIQP’s (6) continuous relaxation, which is convex because B≻0B\succ0 and its constraints are affine. Hence, (y∗,w∗)(y^*,w^*) globally minimizes this QP, and fixing any feasible y∈Py\in\mathcal{P} cannot decrease its optimal value, so JQP(y)≥F(y∗,w∗)≥JNLP(y∗)J_{\mathrm{QP}}(y)\ge F(y^*,w^*)\ge J_{\mathrm{NLP}}(y^*), hence dQP(y;y∗,w∗,B)≥0d_{\mathrm{QP}}(y;y^*,w^*,B)\ge0. Minimizing this distance over Y\mathcal{Y} is equivalent to solving (6) constructed at (y∗,w∗,p)(y^*,w^*,p). Note that we could use also B=0B=0, then (6) reduces to an MILP.

Relaxations in the integer reconstruction

Solving the MIQP (6) is usually the most expensive step of the decomposition approach with a quadratic-model distance. Since MPC applies only the first control input, only v0v_0 must be integer feasible. This motivates reducing the combinatorial complexity through two horizon-tail approximations inspired by [22]. While [22] uses these approximations in a tailored solver for fixed-matrix MIQPs, we study them within the decomposition approach and apply them to real-time MPC in Sec. IV.

For either approximation, partition y=(y1,y2)y=(y_1,y_2) at a horizon 0≤M≤N0\le M\le N, where

y1=(v0,…,vM−1),y2=(vM,…,vN−1).(9)y_1=(v_0,\ldots,v_{M-1}),\qquad y_2=(v_M,\ldots,v_{N-1}). \tag*{(9)}

The corresponding block is empty when M=0M=0 or M=NM=N. The objective and linearized constraints retain the full horizon.

Relaxation of optimality

Suppose we have an integer-feasible vector y∗∗∈Yy^{**}\in\mathcal{Y}. In practice, it may be obtained via sum-up rounding or by solving the CIA-MILP with pycombina [13]. For 0<Mo≤N0<M_o\le N, the first block remains a binary decision and the second block is fixed to the corresponding part of y∗∗y^{**}. Thus, in (S2) we solve an MIQP with fewer free binary variables:

min⁡y1,y2,wFQP(y,w;y∗,w∗,B)s.t.GL(y,w;p,y∗,w∗)=0,HL(y,w;y∗,w∗)≤0,y∈P,y1∈{0,1}Monv,y2=y2∗∗.(10)\begin{aligned} \min_{y_1,y_2,w}\quad&F_{\mathrm{QP}}(y,w;y^*,w^*,B)\\ \text{s.t.}\quad&G_{\mathrm{L}}(y,w;p,y^*,w^*)=0,\\ &H_{\mathrm{L}}(y,w;y^*,w^*)\le0,\\ &y\in\mathcal{P},\\ &y_1\in\{0,1\}^{M_o n_v},\\ &y_2=y_2^{**}. \tag*{(10)} \end{aligned}

Every entry of yy is binary, so (10) supplies an integer-feasible first input. For Mo=0M_o = 0, the complete integer sequence is fixed to y∗∗y^{**} and only one continuous QP is solved. For Mo=NM_o = N, problem (10) is the full MIQP (6). For any MoM_o, subsequent nonlinear polishing yields a feasible, potentially suboptimal solution of the full MINLP (2), provided the polishing NLP in (S3) is feasible.

Relaxation of feasibility

For 1≤Mf≤N1 \le M_f \le N, only the first block is required to be binary, while integrality is relaxed in the remaining block. We solve the following MIQP:

min⁡y1,y2,wFQP(y,w;y∗,w∗,B)s.t.GL(y,w;p,y∗,w∗)=0,HL(y,w;y∗,w∗)≤0,y∈P,y1∈{0,1}Mfnv,y2∈[0,1](N−Mf)nv.(11)\begin{aligned} \min_{y_1,y_2,w}\quad&F_{\mathrm{QP}}(y,w;y^*,w^*,B)\\ \text{s.t.}\quad&G_{\mathrm{L}}(y,w;p,y^*,w^*)=0,\\ &H_{\mathrm{L}}(y,w;y^*,w^*)\le0,\\ &y\in\mathcal{P},\\ &y_1\in\{0,1\}^{M_f n_v},\\ &y_2\in[0,1]^{(N-M_f)n_v}. \tag*{(11)} \end{aligned}

Since Mf≥1M_f \ge1, the first control input is integer feasible, while the second block can be fractional. For Mf=NM_f = N, this problem is the full MIQP (6). With this relaxation, the decomposition no longer necessarily provides a feasible solution of the full MINLP (2). Nevertheless, the relaxed problem provides a lower bound on the full MIQP value, as discussed below, and retains an integer-feasible first input for MPC. From a dynamic programming perspective, both approximations replace the full MIQP’s tail value function by one obtained with either prescribed binary controls or relaxed integrality. Figure 1 illustrates both approximations and compares them with the full MIQP.

Figure 1. Horizon-tail approximations for a binary control in the parallel-chiller example of Sec. V. The full MIQP optimizes all binary decisions. The feasibility relaxation (Mf=8M_f = 8) allows a continuous tail, whereas the optimality relaxation (Mo=3M_o = 3) fixes the tail to prescribed binary values. Shading indicates the respective horizon tails.

Relation to the nonlinear value function

Throughout this section, pp is fixed and we abbreviate JQP(y):=JQP(y;y∗,w∗,B)J_{\mathrm{QP}}(y) := J_{\mathrm{QP}}(y;y^*,w^*,B). We now relate the optimal value functions of the relaxed MIQPs (10) and (11) to JNLP(y)J_{\mathrm{NLP}}(y), the optimal value function of (3). We begin by relating the optimal value functions of the three MIQP variants: the full MIQP and its optimality and feasibility relaxations.

Theorem 1 (Horizon-tail gap bound). Suppose that the continuous relaxation of (6) has a compact feasible set and fix (p,y∗,w∗,B)(p,y^*,w^*,B) with B≻0B \succ0. Fix a binary sequence y∗∗y^{**} feasible for (6) and assume that, for every partition (9), replacing the tail of any feasible sequence with a binary prefix by y∗∗y^{**} preserves feasibility after reoptimizing ww. Let JQP∗J_{\mathrm{QP}}^*, UMU_M, and LML_M denote the globally optimal values of (6), (10), and (11), respectively, with Mo=Mf=MM_o = M_f = M and 1≤M≤N1 \le M \le N. Then there exists K>0K > 0, independent of MM, such that

LM≤JQP∗≤UM,(12)L_M \le J_{\mathrm{QP}}^* \le U_M, \tag*{(12)}
0≤UM−LM≤K(N−M)nv.(13)0 \le U_M-L_M \le K\sqrt{(N-M)n_v}. \tag*{(13)}

Moreover, LML_M is nondecreasing, UMU_M is nonincreasing, and LN=UN=JQP∗L_N = U_N = J_{\mathrm{QP}}^*.

Proof. Every feasible point of the full MIQP (6) is feasible for the feasibility-relaxed problem (11), hence LM≤JQP∗L_M \le J_{\mathrm{QP}}^*. Conversely, every optimizer of (10) is feasible for the full MIQP (6), hence JQP∗≤UMJ_{\mathrm{QP}}^* \le U_M. Together, these inequalities establish (12a). Increasing MM shrinks the feasible set of (11) and enlarges that of (10), proving monotonicity of LML_M and UMU_M. At M=NM=N, both problems coincide with (6).

By Theorem 6.1, JQP(y)J_{\mathrm{QP}}(y) is continuous and piecewise quadratic on its feasible domain. Its finitely many quadratic pieces and compactness of the feasible set of the relaxation of (6) imply Lipschitz continuity of JQP(y)J_{\mathrm{QP}}(y) with a constant K>0K > 0. Let y^f=(y^f,1,y^f,2)\hat{y}_f = (\hat{y}_{f,1},\hat{y}_{f,2}) be the yy-component of a global optimizer of (11), so that LM=JQP(y^f)L_M = J_{\mathrm{QP}}(\hat{y}_f). Similarly, let (y^o,y^2∗∗)(\hat{y}_o,\hat{y}_2^{**}) be the corresponding component of a global optimizer of (10), so that UM=JQP(y^o,y^2∗∗)U_M = J_{\mathrm{QP}}(\hat{y}_o,\hat{y}_2^{**}). Then

UM−LM=JQP(y^o,y^2∗∗)−JQP(y^f,1,y^f,2)≤JQP(y^f,1,y^2∗∗)−JQP(y^f,1,y^f,2)≤K∥y^2∗∗−y^f,2∥≤K(N−M)nv.\begin{aligned} U_M-L_M &=J_{\mathrm{QP}}(\hat{y}_o,\hat{y}_2^{**})-J_{\mathrm{QP}}(\hat{y}_{f,1},\hat{y}_{f,2})\\ &\le J_{\mathrm{QP}}(\hat{y}_{f,1},\hat{y}_2^{**})-J_{\mathrm{QP}}(\hat{y}_{f,1},\hat{y}_{f,2})\\ &\le K\lVert\hat{y}_2^{**}-\hat{y}_{f,2}\rVert \le K\sqrt{(N-M)n_v}. \end{aligned}

In the first inequality, we used JQP(y^o,1,y^2∗∗)≤JQP(y^f,1,y^2∗∗)J_{\mathrm{QP}}(\hat{y}_{o,1},\hat{y}_2^{**}) \le J_{\mathrm{QP}}(\hat{y}_{f,1},\hat{y}_2^{**}), which follows because the tail-replacement assumption makes (y^f,1,y^2∗∗)(\hat{y}_{f,1},\hat{y}_2^{**}) feasible in (10), while y^o,1\hat{y}_{o,1} is optimal. The second inequality follows from Lipschitz continuity of JQPJ_{\mathrm{QP}}. The last uses the fact that y2y_2 has q=nv(N−M)q=n_v(N-M) components, each differing by at most one. Thus, ∥y2∗∗−y^f,2∥≤∑i=1q12=q\lVert y_2^{**}-\hat{y}_{f,2}\rVert\le\sqrt{\sum_{i=1}^{q}1^2}=\sqrt{q}, which establishes (12b). □

We proceed towards relating JNLP(y)J_{\mathrm{NLP}}(y) to JQP(y)J_{\mathrm{QP}}(y). Recall that yy is interpreted here as a fixed parameter in the NLP (3), for which we will assume some standard regularity conditions.

Assumption 1 (Local NLP regularity). Let (y∗,w∗,λ∗,μ∗)(y^*,w^*,\lambda^*,\mu^*) be a KKT point of (3) at y=y∗y=y^*, and define A∗:={i∣Hi(y∗,w∗)=0}A^*:=\{i\mid H_i(y^*,w^*)=0\} and A+∗:={i∈A∗∣μi∗>0}A^*_+:=\{i\in A^*\mid\mu_i^*>0\}. It holds that:

(a) The functions FF, GG, and HH are twice continuously differentiable near (y∗,w∗)(y^*,w^*).

(b) Linear independence constraint qualification (LICQ) holds with respect to ww, i.e., the vectors

{∇wGj(y∗,w∗;p)}j∪{∇wHi(y∗,w∗)}i∈A∗\{\nabla_w G_j(y^*,w^*;p)\}_j\cup\{\nabla_w H_i(y^*,w^*)\}_{i\in A^*}

are linearly independent.

(c) Strong second order sufficient condition (SSOSC) holds with respect to ww, i.e.,

dwT∇ww2L(y∗,w∗,λ∗,μ∗;p)dw>0d_w^{\mathsf T}\nabla^2_{ww}\mathcal{L}(y^*,w^*,\lambda^*,\mu^*;p)d_w>0

for every nonzero dwd_w in the strong critical cone

CS:={dw | ∇wG(y∗,w∗;p)Tdw=0,∇wHi(y∗,w∗)Tdw=0,i∈A+∗}.\mathcal{C}^{\mathsf S}:=\left\{d_w\ \middle|\ \begin{aligned} \nabla_wG(y^*,w^*;p)^{\mathsf T}d_w&=0,\\ \nabla_wH_i(y^*,w^*)^{\mathsf T}d_w&=0,\quad i\in A^*_+ \end{aligned}\right\}.

Next, we establish an intermediate result similar to [16 Corollary 1], but more directly using only elementary NLP perturbation theory. Throughout the following analysis, wNLP(y)w_{\mathrm{NLP}}(y) denotes the locally unique NLP solution map in the polishing step used in Lemma 1, with wNLP(y∗)=w∗w_{\mathrm{NLP}}(y^*)=w^* and JNLP(y):=F(y,wNLP(y))J_{\mathrm{NLP}}(y):=F(y,w_{\mathrm{NLP}}(y)).

Lemma 1. Suppose Assumption 1 holds for the NLP (3) at the fixed parameter y∗y^* and the corresponding solution w∗w^*, and that B≻0B\succ0 in (7). Then there exist ϵ>0\epsilon>0 and C≥0C\geq0 such that for all y∈Bϵ(y∗):={y∈Rny∣∥y−y∗∥<ϵ}y\in B_\epsilon(y^*):=\{y\in\mathbb{R}^{n_y}\mid\|y-y^*\|<\epsilon\}:

∣JNLP(y)−JQP(y)∣≤C∥y−y∗∥2.(14)\lvert J_{\mathrm{NLP}}(y)-J_{\mathrm{QP}}(y)\rvert\leq C\lVert y-y^*\rVert^2. \tag*{(14)}

Proof. Fix the parameter y=y∗y=y^* also in the QP (7). By construction, the NLP and QP have the same KKT conditions at (w∗,λ∗,μ∗)(w^*,\lambda^*,\mu^*). Since B≻0B\succ0, the unique solution of this QP is therefore w∗w^*, with Δw=0\Delta w=0. Hence, JQP(y∗)=JNLP(y∗)J_{\mathrm{QP}}(y^*)=J_{\mathrm{NLP}}(y^*), and it can be verified by direct computation that ∇yL(y∗,w∗,λ∗,μ∗;p)=∇yLQP(y∗,w∗,λ∗,μ∗;p)\nabla_y\mathcal{L}(y^*,w^*,\lambda^*,\mu^*;p)=\nabla_y\mathcal{L}_{\mathrm{QP}}(y^*,w^*,\lambda^*,\mu^*;p), where LQP\mathcal{L}_{\mathrm{QP}} is the Lagrangian of the QP (7).

By Assumption 1 and [24 Theorem 2.4.5 (iv)], the local primal–dual solution of the NLP (3) is Lipschitz continuous in yy. Because B≻0B\succ0 ensures SSOSC and Assumption 1 implies LICQ also for the QP (7) at w∗w^*, we can apply [24 Theorem 2.4.5 (iv)] to the QP’s solution map as well. Thus, let zi(y)=(wi(y),λi(y),μi(y))z_i(y)=(w_i(y),\lambda_i(y),\mu_i(y)), i∈{NLP,QP}i\in\{\mathrm{NLP},\mathrm{QP}\}, denote these primal–dual solution maps, with zi(y∗)=(w∗,λ∗,μ∗)z_i(y^*)=(w^*,\lambda^*,\mu^*).

By twice continuous differentiability of FF, GG, and HH (Ass. 1(a)) and Lipschitz continuity of the solution maps, ∇yL\nabla_y\mathcal{L} and ∇yLQP\nabla_y\mathcal{L}_{\mathrm{QP}}, evaluated along the respective solution maps, are locally Lipschitz in yy.

Furthermore, by applying [24 Theorem 2.4.5 (v)] to the NLP and QP, we have that ∇yJNLP(y∗)=∇yL(y∗,w∗,λ∗,μ∗;p)\nabla_yJ_{\mathrm{NLP}}(y^*)=\nabla_y\mathcal{L}(y^*,w^*,\lambda^*,\mu^*;p) and ∇yJQP(y∗)=∇yLQP(y∗,w∗,λ∗,μ∗;p)\nabla_yJ_{\mathrm{QP}}(y^*)=\nabla_y\mathcal{L}_{\mathrm{QP}}(y^*,w^*,\lambda^*,\mu^*;p). The same identities hold locally along the respective solution maps, so both value-function gradients are locally Lipschitz.

Finally, define E(y):=JNLP(y)−JQP(y)E(y):=J_{\mathrm{NLP}}(y)-J_{\mathrm{QP}}(y). It follows from the arguments above that there exists ϵ>0\epsilon>0 such that ∇E(y)\nabla E(y) is Lipschitz with a constant LEL_E for y∈Bϵ(y∗)y\in B_\epsilon(y^*). Let dy:=y−y∗d_y:=y-y^*. Using E(y∗)=0E(y^*)=0 and ∇E(y∗)=0\nabla E(y^*)=0 and applying the fundamental theorem of calculus for ∥dy∥<ϵ\lVert d_y\rVert<\epsilon, with ∣E(y∗+dy)+E(y∗)∣=∣E(y)∣\lvert E(y^*+d_y)+E(y^*)\rvert=\lvert E(y)\rvert we obtain

∣E(y)∣=∣E(y∗)+∫01[∇E(y∗+tdy)−∇E(y∗)]Tdy dt∣≤∫01LEt∥dy∥2 dt=12LE∥dy∥2.\begin{aligned} \lvert E(y)\rvert &=\left\lvert E(y^*)+\int_0^1[\nabla E(y^*+td_y)-\nabla E(y^*)]^{\mathsf T}d_y\,dt\right\rvert\\ &\leq\int_0^1L_Et\lVert d_y\rVert^2\,dt=\frac{1}{2}L_E\lVert d_y\rVert^2. \end{aligned}

Thus, (13) holds with C=LE/2C=L_E/2.

Finally, we relate the value JNLP(y^)J_{\mathrm{NLP}}(\hat y) obtained by the decomposition approach to the globally optimal MINLP value JNLP(y∘)J_{\mathrm{NLP}}(y^\circ) in (4). Lemma 1 requires y∈Bϵ(y∗)y\in B_\epsilon(y^*), which need not hold for arbitrary binary vectors yy and a relaxed solution y∗y^*. Hence, we make an assumption specific to mixed-integer OCPs, analogous to [16 Assumption 1], that allows us to apply the preceding result.

Assumption 2. Let ϵ>0\epsilon>0 be as in Lemma 1, and fix M∈{1,…,N}M\in\{1,\ldots,N\}. Let y^\hat y be the yy-component of a global optimizer of either (10) with Mo=MM_o=M or (11) with Mf=MM_f=M. Assume that y^∈Bϵ(y∗)\hat y\in B_\epsilon(y^*) and that there exists a global minimizer (y∘,w∘)(y^\circ,w^\circ) of (2) satisfying y∘∈Bϵ(y∗)y^\circ\in B_\epsilon(y^*), w∘=wNLP(y∘)w^\circ=w_{\mathrm{NLP}}(y^\circ).

Recall that (y∗,w∗)(y^*,w^*) is the relaxed solution obtained in (S1), while JNLP(y^)J_{\mathrm{NLP}}(\hat y) is the value of the polished solution obtained in (S3) by fixing y=y^y=\hat y in (3), with w^=wNLP(y^)\hat w=w_{\mathrm{NLP}}(\hat y). Next, our main theoretical result follows.

Theorem 2 (Nonlinear value bounds). Fix pp and let (y∗,w∗)(y^*,w^*) be a local solution of the continuous relaxation of (2). Suppose Assumption 1 holds for the fixed-y∗y^* NLP (3) at w∗w^*. Construct the MIQP (7) at (y∗,w∗)(y^*,w^*) with B≻0B\succ0, and let ϵ\epsilon and CC be given by Lemma 1. Suppose the Assumption of Theorem 1 hold for this MIQP, and let KK be its gap-bound constant.

Fix M∈{1,…,N}M\in\{1,\ldots,N\} and let y^\hat y be the yy-component of a global optimizer of either (10) with Mo=MM_o=M or (11) with Mf=MM_f=M. Let (y∘,w∘)(y^\circ,w^\circ) be a global minimizer of (2), and suppose Assumption 2 holds for y^\hat y and (y∘,w∘)(y^\circ,w^\circ) with the radius ϵ\epsilon. For the polishing solution w^=wNLP(y^)\hat w=w_{\mathrm{NLP}}(\hat y), define JNLP(y^)=F(y^,w^)J_{\mathrm{NLP}}(\hat y)=F(\hat y,\hat w); by the same assumption, JNLP(y∘)=F(y∘,w∘)J_{\mathrm{NLP}}(y^\circ)=F(y^\circ,w^\circ).

(a) If y^\hat y is obtained from the optimality-MIQP (10), then

0≤JNLP(y^)−JNLP(y∘)(15)0\leq J_{\mathrm{NLP}}(\hat y)-J_{\mathrm{NLP}}(y^\circ) \tag*{(15)}
Equation not extracted

\leq K\sqrt{(N-M)n_v}+C(\lVert\hat y-y^\rVert^2+\lVert y^\circ-y^\rVert^2).

(b) If $\hat y$ is obtained from the feasibility-MIQP (11), then

J_{\mathrm{NLP}}(\hat y)-J_{\mathrm{NLP}}(y^\circ)\leq C(\lVert\hat y-y^\rVert^2+\lVert y^\circ-y^\rVert^2)-(J^*_{\mathrm{QP}}-L_M).

{#eq:15}

Proof. By Assumption 2, Lemma 1 applies at y^\hat y and y∘y^\circ. Adding and subtracting the corresponding QP values gives

JNLP(y^)−JNLP(y∘)(16)J_{\mathrm{NLP}}(\hat y)-J_{\mathrm{NLP}}(y^\circ) \tag*{(16)}
=JNLP(y^)−JQP(y^)+JQP(y^)−JQP(y∘)+JQP(y∘)−JNLP(y∘)≤JQP(y^)−JQP(y∘)+∣JNLP(y^)−JQP(y^)∣+∣JQP(y∘)−JNLP(y∘)∣≤JQP(y^)−JQP(y∘)+C(∥y^−y∘∥2+∥y∘−y∗∥2).(17)=J_{\mathrm{NLP}}(\hat{y})-J_{\mathrm{QP}}(\hat{y})+J_{\mathrm{QP}}(\hat{y})-J_{\mathrm{QP}}(y^\circ)\\ \quad+J_{\mathrm{QP}}(y^\circ)-J_{\mathrm{NLP}}(y^\circ)\\ \le J_{\mathrm{QP}}(\hat{y})-J_{\mathrm{QP}}(y^\circ)+\lvert J_{\mathrm{NLP}}(\hat{y})-J_{\mathrm{QP}}(\hat{y})\rvert\\ \quad+\lvert J_{\mathrm{QP}}(y^\circ)-J_{\mathrm{NLP}}(y^\circ)\rvert\\ \le J_{\mathrm{QP}}(\hat{y})-J_{\mathrm{QP}}(y^\circ)+C\left(\lVert\hat{y}-y^\circ\rVert^2+\lVert y^\circ-y^*\rVert^2\right). \tag*{(17)}

Since y∘∈Bϵ(y∗)y^\circ\in\mathcal{B}_{\epsilon}(y^*), QP (7) with y=y∘y=y^\circ admits a solution. Let JQP∗J^*_{\mathrm{QP}} denote the globally optimal value of the full MIQP (6). Together with Theorem 1 and y∘∈Yy^\circ\in\mathcal{Y}, this yields

LM≤JQP∗≤JQP(y∘).(18)L_M \le J^*_{\mathrm{QP}} \le J_{\mathrm{QP}}(y^\circ). \tag*{(18)}

In case (a), optimality of the reconstruction gives JQP(y^)=UMJ_{\mathrm{QP}}(\hat{y})=U_M. Comparison with the full MIQP and Theorem 1 yields

JQP(y^)−JQP(y∘)≤UM−LM≤K(N−M)ny.J_{\mathrm{QP}}(\hat{y})-J_{\mathrm{QP}}(y^\circ)\le U_M-L_M\le K\sqrt{(N-M)n_y}.

Substitution into (16) proves the upper bound in (14). Its lower bound follows from feasibility of the polished pair (y^,w^)(\hat{y},\hat{w}) and global optimality of (y∘,w∘)(y^\circ,w^\circ), hence JNLP(y∘)≤JNLP(y^)J_{\mathrm{NLP}}(y^\circ)\le J_{\mathrm{NLP}}(\hat{y}).

In case (b), optimality of the reconstruction gives JQP(y^)=LMJ_{\mathrm{QP}}(\hat{y})=L_M. Using (17), we obtain

JQP(y^)−JQP(y∘)≤LM−JQP∗=−(JQP∗−LM)≤0.J_{\mathrm{QP}}(\hat{y})-J_{\mathrm{QP}}(y^\circ)\le L_M-J^*_{\mathrm{QP}}=-(J^*_{\mathrm{QP}}-L_M)\le0.

Substitution into (16) proves (15).

For the optimality relaxation, the nonlinear loss is bounded by the horizon-tail gap and a local quadratic modeling error. The feasibility relaxation does not enforce integrality over the full horizon, which tightens the upper bound by the relaxation gap JQP∗−LMJ^*_{\mathrm{QP}}-L_M at the expense of full integer feasibility. At M=NM=N, the upper bounds of (14) and (15) are identical and reduce to the form of [16 Theorem 2].

Advanced-step mixed-integer NMPC

In real-time MPC, the delay between receiving a state measurement and applying the control input should be as short as possible. To reduce this feedback delay, we reorder and reduce the computations of the three-step decomposition into a preparation phase, which solves the continuous relaxation with a predicted state, and a feedback phase, which solves a horizon-tail relaxed MIQP with the measured state.

Preparation and feedback

Following the advanced-step ideas [19, 20, 21], we separate computations performed before the next measurement from those needed to compute the feedback. At sampling time tkt_k, denote the true initial state by xˉ0k\bar{x}_0^k and its prediction by x~0k\tilde{x}_0^k.

During the preparation phase, while the previously computed input uk−1u^{k-1} is applied, we solve the continuous relaxation at x~0k\tilde{x}_0^k to obtain (yk∗,wk∗)(y_k^*,w_k^*) and its multipliers. This completes (S1) and provides the linearization point for the MIQP. For the optimality relaxation, we also compute the binary sequence yk∗∗y_k^{**} used to fix the tail. In principle, this can be obtained with any feasible method, e.g., heuristics, rule based controllers or learned policies [8]. In our implementation, we solve the CIA-MILP via pycombina\textit{pycombina} to obtain yk∗∗y_k^{**}. Optionally, the MIQP can be solved at x~0k\tilde{x}_0^k to provide a warm start for the feedback phase MIQP with xˉ0k\bar{x}_0^k.

Once xˉ0k\bar{x}_0^k is available, the feedback phase updates the initial state to xˉ0k\bar{x}_0^k and solves the MIQP. All other data in the MIQP remain unchanged. Algorithm 1 summarizes the procedure. All three MIQP variants enforce integrality of the first control input, including the case Mo=0M_o=0, where the entire binary sequence is prescribed, and only a QP is solved in the feedback phase.

Algorithm 1 Advanced-step mixed-integer nonlinear MPC (AS-MINMPC)

Require: Horizons NN, MM and a choice of (6), (10), or (11)

1: for each sample kk do

Preparation before tkt_k

2: &nbsp;&nbsp;&nbsp;&nbsp;Predict the next initial state x~0k\tilde{x}_0^k.

3: &nbsp;&nbsp;&nbsp;&nbsp;Solve the relaxed NLP of (S1) with x~0k\tilde{x}_0^k to obtain (yk∗,wk∗)(y_k^*,w_k^*) and its multipliers.

4: &nbsp;&nbsp;&nbsp;&nbsp;Set up the MIQP of (S2) at the lin. point (yk∗,wk∗)(y_k^*,w_k^*).

5: &nbsp;&nbsp;&nbsp;&nbsp;For (10), compute yk∗∗∈Yy_k^{**}\in\mathcal{Y} and fix its tail.

6: &nbsp;&nbsp;&nbsp;&nbsp;Optional: Solve the selected MIQP at x~0k\tilde{x}_0^k to obtain a warm start.

Feedback after measuring xˉ0k\bar{x}_0^k

7: &nbsp;&nbsp;&nbsp;&nbsp;Set the initial state in the MIQP to xˉ0k\bar{x}_0^k.

8: &nbsp;&nbsp;&nbsp;&nbsp;Solve the selected MIQP of (S2) using the available warm start, to obtain (y^k,w^k)(\hat{y}_k,\hat{w}_k).

9: &nbsp;&nbsp;&nbsp;&nbsp;Optional: Solve the polishing NLP in (S3) with y^k\hat{y}_k.

10: &nbsp;&nbsp;&nbsp;&nbsp;Apply the first continuous and integer control inputs.

11: &nbsp;&nbsp;&nbsp;&nbsp;Shift the solution for the next preparation phase.

12: end for

MIQP step as a full SQP step

To reduce feedback delay, the proposed algorithm does not in general solve the polishing NLP in (S3) to convergence. We observe that the feedback MIQP simultaneously reconstructs the integer decisions y^k\hat{y}_k and performs one SQP step toward the corresponding polishing solution, yielding w^k≈wNLP(y^k)\hat{w}_k\approx w_{\mathrm{NLP}}(\hat{y}_k).

For the full and optimality-relaxed MIQPs, fixing the reconstructed integers yields the SQP subproblem obtained by linearizing the NLP in (y,w)(y,w) at (y∗,w∗)(y^*,w^*) and imposing y=y^y=\hat{y}. For the feasibility relaxation, the same interpretation holds after fixing only the binary prefix and retaining the tail as continuous variables.

This interpretation connects the method to real-time iteration (RTI) and advanced-step RTI [1, 20, 21] for continuous NLPs. If the integer decisions are the same for the measured and predicted states, i.e., y(xˉ0k)=y(x~0k)y(\bar{x}_0^k)=y(\tilde{x}_0^k), we expect a local predictor–corrector error analysis for the proposed AS-MINMPC method to yield bounds similar to [21]. If y(xˉ0k)≠y(x~0k)y(\bar{x}_0^k)\ne y(\tilde{x}_0^k), the solution map may be discontinuous, similarly to nonsmooth MPC [25], which would need to be accounted for in the error analysis. Due to page restrictions, we leave a detailed error analysis for future work.

Numerical example

We compare several variants of the proposed method with the state-of-the-art MINLP solver CAMINO [26], and a rule-based controller (RBC) from [8] on a parallel-chiller example [8].

Implementation

We implement several variants of Algorithm 1 (including the optional steps, and solving MILPs instead of MIQPs) in the accompanying repository.3 The implementation uses IPOPT [27] for NLPs, BnB-DAQP [28] for MIQPs via CasADi 3.8.0 [29], and pycombina [13] for integer-feasible reconstruction. Thus, the proposed method uses only open-source software packages.

Benchmark example

To evaluate the proposed algorithms, we consider a data center parallel-chiller plant example from [8 Sec. 2]. The objective is to meet the cooling demand while reducing power consumption and chiller switching frequency. For nvn_v chillers, the state vector is x=(Tr,Ts(1),…,Ts(nv))x=(T_r,T_s^{(1)},\ldots,T_s^{(n_v)}), comprising the shared return and individual supply temperatures. The continuous controls are u=(Te(1),…,Te(nv),m˙(1),…,m˙(nv))u=(T_e^{(1)},\ldots,T_e^{(n_v)},\dot{m}^{(1)},\ldots,\dot{m}^{(n_v)}), comprising the evaporator temperatures and mass flows, while v=(v(1),…,v(nv))v=(v^{(1)},\ldots,v^{(n_v)}) contains the binary on/off decisions for each chiller operating in parallel. The cooling powers and thermal dynamics are:

Q(i)(t)=ηrcpm˙(i)(t)v(i)(t)(Tr(t)−Ts(i)(t)),Q^{(i)}(t)=\eta_r c_p \dot{m}^{(i)}(t)v^{(i)}(t)(T_r(t)-T_s^{(i)}(t)),
T˙r(t)=1Cr(Q˙load(t)−∑i=1nvQ(i)(t)),\dot{T}_r(t)=\frac{1}{C_r}\left(\dot{Q}_{\mathrm{load}}(t)-\sum_{i=1}^{n_v}Q^{(i)}(t)\right),
T˙s(i)(t)=−cpηsC(i)v(i)(t)m˙(i)(t)(Ts(i)(t)−Te(i)(t)).\dot{T}_s^{(i)}(t)=-\frac{c_p\eta_s}{C^{(i)}}v^{(i)}(t)\dot{m}^{(i)}(t)(T_s^{(i)}(t)-T_e^{(i)}(t)).

The chiller and pump power consumption are:

Pchiller(i)(t)=Q(i)(t)COP⁡(i)(t)+ρ(i)v(i)(t),P_{\mathrm{chiller}}^{(i)}(t)=\frac{Q^{(i)}(t)}{\operatorname{COP}^{(i)}(t)}+\rho^{(i)}v^{(i)}(t),
COP⁡(i)(t)=a0(i)+a1(i)Q(i)(t)Qmax⁡(i)+a2(i)(Q(i)(t)Qmax⁡(i))2,\operatorname{COP}^{(i)}(t)=a_0^{(i)}+a_1^{(i)}\frac{Q^{(i)}(t)}{Q_{\max}^{(i)}}+a_2^{(i)}\left(\frac{Q^{(i)}(t)}{Q_{\max}^{(i)}}\right)^2,
Ppump(i)(t)=γ(i)v(i)(t)(m˙(i)(t))3.P_{\mathrm{pump}}^{(i)}(t)=\gamma^{(i)}v^{(i)}(t)\left(\dot{m}^{(i)}(t)\right)^3.

All model parameters, bounds, and load profiles are taken from [8 Table 1]. Using the compact notation of the OCP (1), we have

min⁡x,u,v ∑k=0N−1ℓk(xk,uk,vk)+∑k=0N−1∥vk−vk−1∥R2(19)\min_{x,u,v}\ \sum_{k=0}^{N-1}\ell_k(x_k,u_k,v_k)+\sum_{k=0}^{N-1}\lVert v_k-v_{k-1}\rVert_R^2 \tag*{(19)}
s.t.x0=xˉ0,(20)\mathrm{s.t.}\quad x_0=\bar{x}_0, \tag*{(20)}
xk+1=fk(xk,uk,vk),k=0,…,N−1,(21)x_{k+1}=f_k(x_k,u_k,v_k),\quad k=0,\ldots,N-1, \tag*{(21)}
xmin⁡≤xk≤xmax⁡,k=0,…,N,(22)x_{\min}\le x_k\le x_{\max},\quad k=0,\ldots,N, \tag*{(22)}
umin⁡≤uk≤umax⁡,k=0,…,N−1,(23)u_{\min}\le u_k\le u_{\max},\quad k=0,\ldots,N-1, \tag*{(23)}
0≤Qk(i)≤Qmax⁡(i),k=0,…,N−1,(24)0\le Q_k^{(i)}\le Q_{\max}^{(i)},\quad k=0,\ldots,N-1, \tag*{(24)}
∑i=1nvvk(i)≥1,k=0,…,N−1(25)\sum_{i=1}^{n_v}v_k^{(i)}\ge1,\quad k=0,\ldots,N-1 \tag*{(25)}

Here, v−1v_{-1} denotes the previously applied binary control input. The stage costs terms ℓk\ell_k consist of

the power consumption and load demand tracking error: ℓk(xk,uk,vk):=∑i=1nv(Pchiller,k(i)+Ppump,k(i))+λW(∑i=1nvQk(i)−Qdemand,k)2\ell_k(x_k,u_k,v_k):=\sum_{i=1}^{n_v}(P_{\mathrm{chiller},k}^{(i)}+P_{\mathrm{pump},k}^{(i)})+\lambda_W\left(\sum_{i=1}^{n_v}Q_k^{(i)}-Q_{\mathrm{demand},k}\right)^2. We use the cost weights R=200IR=200I and λW=0.01\lambda_W=0.01. The discrete-time map fkf_k incorporates the prescribed effective demand and one fourth-order Runge–Kutta (RK4) step per control interval of 180 s. Closed-loop simulation uses four RK4 substeps per control interval to obtain the next measured state.

All controllers use the same load profile (Figure 3) and initial states over 240 MPC steps (12 h of sim. time). Preparation times are never the computational bottleneck, therefore, we focus on and report feedback times, which are dominated by the MIQP time. The realized closed-loop cost sums the switching and stage costs ℓk\ell_k incurred by the applied inputs over the simulation and is normalized by the lowest cost among all tested algorithms for each experiment. We compare several variants of the proposed AS-MINMPC method with different MfM_f and MoM_o values, the three-phase algorithm [16] of Sec. II, and a state-of-the-art MINLP method: SB-MIQP, implemented in CAMINO [26]. The latter two perform all computations in the feedback phase. We use the default settings of SB-MIQP, except for a time limit of 30 s per MPC step, with Gurobi as MIQP solver. A single full SB-MIQP iteration is equivalent to the three phase algorithm [26].

Figure 3. Representative MPC trajectories for delivered cooling and demand (top), and number of active chillers (bottom), for N=30N=30.

Figure 2 compares mean feedback costs for N=20,30N = 20, 30 with nv=3n_v = 3 chillers. For N=20N = 20, the variant Mf=5M_f = 5 computes feedback 16.68 times faster than CAMINO, with a slightly lower closed-loop cost. For N=30N = 30, it reduces the mean and maximum observed feedback times by factors of 15.56 and 28.30, respectively, relative to full AS-MINMPC, with only a 0.27% increase in closed-loop cost. RBC is computationally cheaper, but its cost is approximately 2.5 times that of the best optimization-based controller. Figure 3 shows that Mf=2M_f = 2 closely follows the cooling and chiller activation trajectories of the three-phase method, with better demand tracking than RBC.

Figure 2. Mean feedback time and normalized realized closed-loop cost for three chillers with N=20N=20 and N=30N=30. Horizon-tail relaxations yield greater AS-MINMPC speedups for longer prediction horizons.

In this example, feasibility-relaxed MIQPs yielded substantial speedups, often with minor losses of optimality below 1%. Optimality-relaxed MIQPs resulted in higher costs in these experiments due to the less favorable integer-sequences obtained with pycombina. Our experiments on other examples available in the public repository showed that this relative performance is problem dependent. But in general, horizon-tail approximations substantially reduced feedback delay while preserving near-reference control performance across all implemented examples.

Conclusions

We presented a real-time mixed-integer nonlinear MPC method that reorders the computations of a decomposition algorithm [10, 16] into preparation and feedback phases. The feedback MIQP reconstructs the integer controls and simultaneously performs one SQP step toward the solution of the problem with the latest state estimate. Horizon-tail approximations in the MIQP reduce the combinatorial complexity associated with the horizon length. Numerical results show reductions of more than 95% in the maximum observed feedback time, with only minor changes in closed-loop cost. The computational advantage of the proposed real-time algorithms becomes increasingly pronounced as the prediction horizon grows. The feedback phase still requires solving an MIQP, which can be expensive when many integer control variables are present. This motivates development of more efficient open-source MIQP solvers.

References

  1. [1]M. Diehl, H. J. Ferreau, and N. Haverbeke, “Efficient numerical methods for nonlinear MPC and moving horizon estimation,” in Nonlinear model predictive control, ser. Lecture Notes in Control and Information Sciences, L. Magni, M. Raimondo, and F. Allgöwer, Eds. Springer, 2009, vol. 384, pp. 391–417.DOI
  2. [2]P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, “Mixed-integer nonlinear optimization,” Acta Numerica, vol. 22, pp. 1–131, 2013.DOI
  3. [3]M. Gerdts, “A variable time transformation method for mixed-integer optimal control problems,” Optimal Control Applications and Methods, vol. 27, no. 3, pp. 169–182, 2006.DOI
  4. [4]R. Abbasi-Esfeden, A. Nurkanović, M. Diehl, P. Patrinos, and J. Sw-evers, “An efficient mixed-integer formulation and an iterative method for optimal control of switched systems under dwell time constraints,” Optimal Control Applications and Methods, 2026.
  5. [5]S. Sager, M. Jung, and C. Kirches, “Combinatorial integral approximation,” Mathematical Methods of Operations Research, vol. 73, no. 3, pp. 363–380, 2011.DOI
  6. [6]C. Kirches, F. Lenders, and P. Manns, “Approximation properties and tight bounds for constrained mixed-integer optimal control,” SIAM Journal on Control and Optimization, vol. 58, no. 3, pp. 1371–1402, 2020.DOI
  7. [7]C. A. Orrico, W. Heemels, and D. Krishnamoorthy, “Learning myopic mixed-integer nonlinear model predictive control from expert demonstrations,” arXiv preprint arXiv:2605.07401, 2026.arxiv.org/abs/2605.07401
  8. [8]J. Boldkovský, C. Faulker, E. Michael, M. Gulan, A. Tuor, and J. Drgoňa, “Data center chiller plant optimization via mixed-integer nonlinear differentiable predictive control,” Control Engineering Practice, vol. 174, p. 107063, 2026.
  9. [9]J. Adamek, L. Lüken, and S. Lucia, “Enabling robust mixed-integer nonlinear model predictive control via self-supervised learning and combinatorial integral approximation,” Journal of Process Control, vol. 159, p. 103636, 2026.DOI
  10. [10]S. Sager, “Reformulations and algorithms for the optimization of switching decisions in nonlinear optimal control,” J. Proc. Contr., vol. 19, pp. 1238–1247, 2009.DOI
  11. [11]C. Zeile, N. Robuschi, and S. Sager, “Mixed-integer optimal control under minimum dwell time constraints,” Mathematical Programming, vol. 188, no. 2, pp. 653–694, 2021.
  12. [12]Y. Chen and M. Lazar, “An efficient mpc algorithm for switched systems with minimum dwell time constraints,” Automatica, vol. 143, p. 110453, 2022.
  13. [13]A. Bürger, C. Zeile, M. Hahn, A. Altmann-Dieses, S. Sager, and M. Diehl, “pycombina: An open-source tool for solving combinatorial approximation problems arising in mixed-integer optimal control,” in Proceedings of the IFAC World Congress, vol. 53, no. 2, 2020, pp. 6502–6508.DOI
  14. [14]F. Bestehorn, C. Hansknecht, C. Kirches, and P. Manns, “Mixed-integer optimal control problems with switching costs: a shortest path approach,” Mathematical Programming, vol. 188, no. 2, pp. 621–652, 2021.DOI
  15. [15]A. Bürger, “Nonlinear mixed-integer model predictive control of renewable energy systems,” Ph.D. dissertation, University of Freiburg, 2020.DOI
  16. [16]A. Bürger, C. Zeile, A. Altmann-Dieses, S. Sager, and M. Diehl, “A Gauss–Newton-based decomposition algorithm for nonlinear mixed-integer optimal control problems,” Automatica, vol. 152, p. 110967, 2023.DOI
  17. [17]J. B. Rawlings, D. Q. Mayne, and M. M. Diehl, Model Predictive Control: Theory, Computation, and Design, 2nd ed. Nob Hill, 2017.
  18. [18]J. B. Rawlings and M. J. Risbeck, “Model predictive control with discrete actuators: Theory and application,” Automatica, vol. 78, 2017.DOI
  19. [19]V. M. Zavala and L. T. Biegler, “The advanced step NMPC controller: Optimality, stability and robustness,” Automatica, vol. 45, pp. 86–93, 2009.DOI
  20. [20]A. Nurkanović, A. Zanelli, S. Albrecht, and M. Diehl, “The Advanced Step Real Time Iteration for NMPC,” in Proceedings of the IEEE Conference on Decision and Control (CDC), 2019.DOI
  21. [21]J. Frey, A. Nurkanović, and M. Diehl, “Advanced-step real-time iterations with four levels – new error bounds and fast implementation in acados,” IEEE Control Systems Letters, 2024.DOI
  22. [22]D. Frick, A. Domahidi, and M. Morari, “Embedded optimization for mixed logical dynamical systems,” Computers & Chemical Engineering, vol. 72, no. Supplement C, pp. 21–33, 2015, a Tribute to Ignacio E. Grossmann.DOI
  23. [24]A. Fiacco, Introduction to sensitivity and stability analysis in nonlinear programming. New York: Academic Press, 1983.
  24. [25]A. Nurkanović, P. Pozharskiy, and M. Diehl, “Real-time algorithms for model predictive control of hybrid dynamical systems,” arXiv preprint arXiv:2604.18432, 2026.arxiv.org/abs/2604.18432
  25. [26]A. Ghezzi, W. V. Roy, S. Sager, and M. Diehl, “A sequential Benders-based mixed-integer quadratic programming algorithm and its implementation in the CAMINO toolbox,” Mathematical Programming Computation, vol. 1–70, 2026.arxiv.org/abs/2404.11786
  26. [27]A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming, vol. 106, no. 1, pp. 25–57, 2006.DOI
  27. [28]D. Arnström and D. Axehill, “Bnb-daqp: A mixed-integer qp solver for embedded applications,” IFAC-PapersOnLine, vol. 56, no. 2, pp. 7420–7427, 2023.arxiv.org/abs/2211.12902
  28. [29]J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “CasADi – a software framework for nonlinear optimization and optimal control,” Mathematical Programming Computation, vol. 11, no. 1, pp. 1–36, 2019.

Paper details

vlnc:W_6yyczthn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents