Exploiting symmetries in tree-based combinatorial calculation of explicit linear MPC solutions

Exploiting symmetries in tree-based combinatorial calculation of explicit linear MPC solutions 1st Ruth Mitze Dep. of Mechanical Engineering Ruhr-Universit¨ at Bochum Bochum, Germany [email protected] 2nd Martin M¨onnigmann Dep. of Mechanical Engineering Ruhr-Universit¨ at Bochum Bochum, Germany [email protected] Abstract—Symmetries of linear MPC problems are reflected in symmetries of their explicit solutions. We recently showed these symmetries also appear in the set of the active sets that define the explicit solution. Consequently, symmetries can be used to speed up algorithms for the calculation of the set of active sets. In this paper, we exploit symmetries to accelerate the approach from [1] by improving the exploration of the combinatorial tree of active sets. The reductions of the computational effort that can be achieved are illustrated and analyzed with two examples. Index Terms—Explicit linear model predictive control, combinatorial parametric quadratic programming, symmetric constrained optimization I. INTRODUCTION Explicit linear model predictive control (MPC) requires the parametric solution to a constrained linear-quadratic optimal control problem (OCP), which is known to be continuous piecewise-affine feedback law [2], [3]. Particularly for highorder problems, for problems with many constraints, and for problems with long prediction horizons, calculating the solution is computationally demanding. Reducing the computational effort of calculating the solution is the focus of an entire field of research. The first approaches proposed for this task exploit geometric relations of the affine pieces in the solution [2], [4], [5]. These approaches are competitive and implemented in mature software toolboxes [6], [7]. However, they require proper tuning to prevent missing out on small pieces of the piecewise-affine feedback law. An alternative approach was proposed by [1] and calculates the set of active sets that define an affine piece in the solution. The approach proceeds by enumerating possible active set candidates and examining them for being an element of the solution. Several refinements to the approach from [1] have been proposed. They exploit relations among the elements in the set of active sets for a more targeted selection and examination of the active set candidates, thus reducing the computational complexity [8]–[12]. Approaches that calculate the solution by enumerating and examining active set candidates are known as combinatorial approaches or implicit enumeration techniques. Support by the European Commission under grant no. 101079342 (Fostering Opportunities Towards Slovak Excellence in Advanced Control for Smart Industries) is gratefully acknowledged. Combinatorial approaches often order the active sets that are candidates for the solution in a combinatorial tree. Symmetries of a physical system and its constraints often result in symmetries of the associated constrained linearquadratic OCP. Symmetries of the OCP are then reflected in inputand state-space transformations in the associated piecewise-affine feedback law [13]. For problems with constraints that are point-symmetric to the origin, symmetries were identified in the active sets [14] and used to improve the combinatorial approaches from [1] and [15] in [14] and [16], respectively. For problems with general symmetries, symmetries in the active sets were identified only recently and a strategy to improve combinatorial approaches for symmetric OCPs was proposed [17]. In this work, we use the strategy proposed in [17] to improve the combinatorial approach from [1]. This approach uses a combinatorial tree to enumerate the active sets that are candidates for the solution. Also, we propose a change to the strategy that makes the examination more efficient. This change further reduces the computational effort, for problems with many symmetries in particular. Reductions of the computational effort are analyzed by applying the approach to different examples. Section II introduces constrained linear-quadratic OCPs and the combinatorial approach from [1]. Section III defines symmetries for OCPs and introduces the exploration strategy to improve combinatorial approaches proposed by [17]. Section IV presents two approaches similar to [1] but improved for symmetric OCPs. The new approaches are applied to two examples in Sect. V and the computational effort is analyzed. Finally, Sect. VI concludes this paper. Notation: Let Ia∈Ra×adenote the identity matrix and 1a∈Raa column vector of ones. Furthermore, let Pc(M) = {m∈ P(M)| |m| ≤ c}, where P(M)refers to the power set of set M. For a matrix A∈Rm×nand ordered set M ⊆ {1, ..., a}, we denote by AM∈R|M|×nthe submatrix of A containing all rows indicated by M. Let operators ⊗and × denote the Kronecker and Cartesian product, respectively, and let A◦ M ={Am |m∈ M}. Furthermore, let max(M)and min(M)denote the greatest and smallest element of the set M, respectively, where applicable. We say sets Mand N partition Rif M ∪ N =Rand M ∩ N =∅. 2023 24th International Conference on Process Control (PC) June 6–9, 2023, Štrbské Pleso, Slovakia 979-8-3503-4763-0/23/$31.00 ©2023 IEEE 48 II. PROBLEM STATEMENT AND PRELIMINARIES This paper treats finite-horizon constrained linear-quadratic OCPs of the form min U,X kx(N)k2 P+ N−1 X k=0 kx(k)k2 Q+ku(k)k2 R(1a) s.t. x(k+ 1) = Ax(k) + Bu(k), k = 0, ..., N −1(1b) u(k)∈ U, k = 0, ..., N −1(1c) x(k)∈ X, k = 0, ..., N −1(1d) x(N)∈ T ,(1e) with stage k∈N0, prediction horizon N∈N, input u(k)∈Rm, state x(k)∈Rn, column vectors U=uT(0), ..., uT(N−1)T∈RNm and X= xT(1), ..., xT(N)T∈RNn, weighting matrices for inputs R∈Rm×m, states Q∈Rn×n, and terminal state P∈Rn×n, system matrices A∈Rn×nand B∈Rn×mof the discretetime time-invariant linear system, and constraint set for inputs U ⊂ Rm, states X ⊂ Rn, and the terminal state T ⊂ Rn. We assume the initial state x(0) is given, matrices Rand Q are such that R≻0and Q0,(A, B)is stabilizable, sets U and Xare compact full-dimensional polytopes that contain the origin in their interiors, and matrix Pand set Tare the optimal cost function matrix of the unconstrained infinite-horizon problem which implies P≻0, and the largest possible set such that the optimal feedback for the unconstrained infinitehorizon problem stabilizes the system without violating the constraints, respectively. Substituting system (1b) in OCP (1) enables to rewrite the OCP as the quadratic program (QP) min U 1 2UTHU +x(0)TFU +1 2x(0)TY x(0) s.t. GU ≤Ex(0) + w, (2) with H∈RNm×Nm,F∈Rn×Nm,Y∈Rn×n,G∈Rq×Nm, E∈Rq×n, and w∈Rq. The assumptions on OCP (1) imply H≻0in QP (2) [2]. Without restriction, we assume the inequality constraints in QP (2) are formulated such that w= 1q. Let qrefer to the number of inequalities in QP (2) and let Q:= {1, ..., q}denote the index set. Furthermore, let sets A(x(0)) and I(x(0)) denote the optimal active and inactive set for any x(0) such that QP (2) has a solution, respectively, with A(x(0)) := i∈ Q | G{i}U⋆(x(0)) = E{i}x(0) + w{i}, (3a) I(x(0)) := Q\A(x(0)),(3b) and where U⋆(x(0)) denotes the optimal solution to the QP. We often drop x(0) in the notation of an active and inactive set, and call an active set Aoptimal if it refers to the optimal solution U⋆(x(0)) for some x(0) with (3a). Solving QP (2) as a parametric program, where the parameter is the initial state x(0), results in the optimal control law x(0) 7→ U⋆(x(0)) which is a continuous piecewise affine function of x(0) on a polytopic partition of the feasible parameter space [2, Sect. 4.1]. The affine pieces in the solution are represented by optimal active sets Athat define fulldimensional state-space polytopes and such that matrix GA has full row rank. We collect all active sets that satisfy these conditions in the solution set M. A. Combinatorial approach from [1] The power set P(Q)contains all possible constraint combinations or, equivalently, all possible active sets. It follows that M ⊆ P(Q). By definition of M, all elements A ∈ Mare such that the matrix GAhas full row rank. Since GA∈R|A|×Nm, the rank of matrix GAis bounded from above by min (|A|, Nm). It follows that active sets Awith |A| > Nm result in row rank deficient GA. Consequently, M ⊆ PNm(Q). The combinatorial approach from [1] considers the active sets A ∈ PNm(Q)as candidates for the solution. Figure 1 shows a rooted tree that represents the candidates in PNm(Q). The tree was first proposed by [18, Def. 2.2] and is used by many combinatorial approaches [1], [10], [14]. We refer to the tree as a combinatorial tree. The combinatorial tree is organized such that candidates of identical cardinalities appear in the same level and candidates containing the lowest constraint indices appear leftmost within each level without restriction. Let the set of candidates in the subtree of a candidate A, i.e., all descendants of Aand Aitself be denoted D(A), D(A) := nA ∪ ˜ A | ˜ A ∈ P({max(A) + 1, ..., q})o. Fig. 1: Combinatorial tree for arbitrary OCP with q= 4 constraints. The solution Mis calculated by collecting all candidates A ∈ PNm(Q)that satisfy the following conditions: (i) GA has full row rank, (ii) Ais optimal, and (iii) Adefines a full-dimensional polytope. The approach from [1] is stated in Alg. 1. It explores all candidates in the order of increasing cardinality (line 2 in Alg. 1). When transferred to the combinatorial tree introduced before, the elements in the tree are explored from top to bottom. For each candidate, a rank test is executed to test for condition (i) (line 3). Candidates Asuch 49 that matrix GAis row rank deficient are dismissed. To test for condition (ii), the linear program (LP) (4) is solved (line 5), min U,x(0),λA,sI,t −t(4a) s.t. FTx(0) + HU + (GA)TλA= 0,(4b) 1|A|t≤λA,(4c) GAU−EAx(0) −wA= 0,(4d) GIU−EIx(0) −wI+sI= 0,(4e) 1|I|t≤sI, t ≥0,(4f) with Lagrange multipliers λAand slack variables sI. Candidates such that LP (4) has a solution are optimal, and not optimal otherwise. If a solution to (4) exists, we denote corresponding optimization variables U⋆,x⋆(0),λ⋆ A,s⋆ I, and t⋆. The following procedure enables the approach to identify many candidates at a time that are not optimal: For all candidates such that LP (4) has no solution, we solve LP (4) without (4b) and (4c) (lines 12–13). We call candidates such that this LP has a solution feasible, and infeasible otherwise. Infeasible active sets are not optimal because the LP to test for feasibility involves only a subset of the constraints of the LP to test for optimality. The set Scollects candidates that are detected as infeasible (lines 14–15). Active sets Athat are supersets of infeasible active sets are infeasible with [1, Thm. 1], and thus not optimal. Dismissing candidates because they are supersets of detected infeasible active sets (line 4) is further referred to as pruning. To test for the last condition (iii), it suffices to test candidates that result in t⋆= 0 for defining a full-dimensional polytope (lines 9–11). Candidates that result in t⋆>0define full-dimensional polytopes with [4, Thm. 2] since this result implies strict inequality for 0< λ⋆ A and GIU⋆−EIx⋆(0) −wI<0(lines 7–8). Algorithm 1: Combinatorial approach from [1] 1Initialization: set M=∅,S=∅ 2for every A ∈ PNm(Q)by incr. cardinality do 3if rank(GA) = |A| then 4if A 6⊇ ˜ Afor all ˜ A ∈ S then 5solve (4) 6if solution exists then 7if solution t⋆>0then 8add Ato M 9else 10 if polytope def. by Ais full-dim. then 11 add Ato M 12 else 13 solve (4) without (4b) and (4c) 14 if no solution exists then 15 add Ato S 16 Output: M III. SYMMETRIC OCPS AND STRATEGY FOR COMBINATORIAL TREE We follow [13, Def. 4] and call an OCP (1) symmetric to the pair (Θ,Ω), where matrices Θ∈Rn×nand Ω∈Rm×m are invertible, if the conditions ΘA=AΘ,ΘB=BΩ, Θ◦ X =X,Ω◦ U =U,Θ◦ T =T, ΘTQΘ = Q, ΩTRΩ = R, ΘTPΘ = P (5) hold. Note that symmetries of the system matrices and constraint sets in (5) result from symmetries of the underlying physical system and its constraints, respectively, and the weighting matrices can often be chosen to comply with some desired symmetry properties. A method for the identification of all pairs (Θ,Ω) that satisfy conditions (5) for an OCP (1) was proposed by [19]. We collect all pairs (Θ,Ω) that satisfy conditions (5) for an arbitrary but fixed OCP (1) in the set G. Each pair (Θ,Ω) ∈ G causes the optimal control law of OCP (1) to be invariant under transformations of the inputand state-space with Ωand Θ, respectively [13]. Consider an OCP (1) that is reformulated as QP (2) with w= 1qand a pair (Θ,Ω) ∈ G. With regard to the constraints in the QP (2), every constraint i∈ Q has a symmetric constraint j∈ Q such that G{i}=G{j}·IN⊗Ωand E{i}=E{j}·Θ(6) [17, Thm. 2]. We introduce the function π(Θ,Ω) :Q → Q to represent the relations j=π(Θ,Ω)(i)from (6). Also, we introduce the function Π(Θ,Ω) :P(Q)→ P(Q)to map all constraints in an active set A ∈ P(Q)to their corresponding symmetric constraints with π(Θ,Ω). We call the active set Aj= Π(Θ,Ω)(Ai)the symmetric active set to Aiunder pair (Θ,Ω). Let the orbit O(A)collect the symmetric active sets to an active set Aunder all pairs (Θ,Ω) ∈ G, O(A) := nΠ(Θ,Ω)(A)|(Θ,Ω) ∈ G o.(7) We often drop the argument Ain the notation of an orbit. It was shown in [17] that the orbits of all active sets in P(Q)partition P(Q). Likewise, the orbits of all active sets in PNm(Q)partition PNm(Q)since the elements of an orbit have identical cardinalities. It follows that the set of candidates for the combinatorial approach from [1] introduced in Sect. II-A partitions into orbits. All elements of an orbit have properties in common [17, Thm. 4] that are relevant for combinatorial approaches: 1) The elements of an orbit are either all optimal or all not optimal. 2) The polytopes defined by the elements of an orbit are either all full-dimensional or all lower-dimensional in state-space. It is suggested by [17] to improve combinatorial approaches by only testing one active set and its polytope of each orbit for optimality and full-dimensionality, respectively, and applying the result to all active sets in the orbit. However, it is not trivial to efficiently identify active sets that can be dismissed from testing. The following strategy is suggested by [17]: For each orbit O, we call the active set containing the lowest constraint indices, i.e., A ∈ O : min(A\ ˜ A)<min( ˜ A\A)∀˜ A ∈ O\A 50 the primary active set. Accordingly, all orbit elements except for the primary active set are non-primary. It is sufficient to process only the primary active set and dismiss all other active sets of the orbit from testing. Assuming all active sets that are candidates are explored in the order of increasing cardinality and increasing constraint indices (when transferred to the combinatorial tree, this strategy is from top to bottom and in each level from left to right), the primary active set of each orbit is reached first. The residual elements of the orbits are non-primary and can therefore be dismissed. With [17, Thm. 5], the active sets of the subtree D(A)are non-primary if the root of the subtree Ais non-primary. We refer to [17, Example 6] for an illustrative example. IV. IMPROVED COMBINATORIAL APPROACHES Based on the strategy described in Sect. III, we improve the combinatorial approach from [1] introduced as Alg. 1 in Sect. II-A. The improvement of the approach is achieved by only processing primary and dismissing non-primary candidates. The complete solution still results because the whole orbit is added to the solution Mwhenever a primary candidate is detected to be part of M. The improved approach is stated in Alg. 2. It processes all candidates A ∈ PNm(Q)in the order of increasing cardinality and increasing constraint indices (line 2 in Alg. 2). This way, the primary candidate of each orbit is processed first. The set Ncollects candidates that are detected as non-primary. Any candidate Asuch that A ∈ D(¯ A)for an ¯ A ∈ N is non-primary and thus dismissed (line 4). All elements of the orbit of a primary candidate, except the primary candidate itself, are non-primary. To keep the number of elements in Nsmall, a non-primary candidate is only added to Nif the candidate is not already an element of a set D(¯ A),¯ A ∈ N (lines 17–19). All other lines in Alg. 2 (lines 3, 5–16, 20) remain unchanged from Alg. 1 but add the whole orbit to the solution Mwhenever a candidate is detected to be part of M (lines 9, 12). Solving the LPs accounts for a large share of the computing time. The number of solved LPs for Alg. 2 is almost reduced by factor g, the number of symmetries, which will be explained in more detail in Sect. V. However, Alg. 2 executes additional computational operations that counteract the reduction of computational time, most notably the tests in lines 4 and 18 to test if an active set is a descendant of a detected nonprimary active set. The additional computational effort is most evident for examples with a large number of symmetries for two reasons: Firstly, the set Ncontains more elements because a large number of symmetries entails a large number of nonprimary active sets. Thus, the test in lines 4 and 18 is more expensive. Secondly, the larger the number of symmetries the larger the number of elements of an orbit. Thus, the for loop starting in line 17 runs more often. We suggest a different procedure in Alg. 3 that obviates these issues and need Cor. 1 as a preparation. It extends the properties that elements of an orbit have in common by the property feasibility. Algorithm 2: Improved combinatorial approach 1 1Initialization: set M=∅,S=∅,N=∅ 2for every A ∈ PNm(Q)by incr. cardinality and by incr. constraint indices do 3if rank(GA) = |A| then 4if A 6∈ D(¯ A)for all ¯ A∈ N then 5if A 6⊇ ˜ Afor all ˜ A ∈ S then 6solve (4) 7if solution exists then 8if solution t⋆>0then 9add elements of O(A)to M 10 else 11 if polytope def. by Ais full-dim then 12 add elements of O(A)to M 13 else 14 solve (4) without (4b) and (4c) 15 if no solution exists then 16 add Ato S 17 for every ˘ A ∈ O(A)\A do 18 if ˘ A 6∈ D(¯ A)for all ¯ A∈ N then 19 add ˘ Ato N 20 Output: M Corollary 1. Consider an OCP (1). The active sets of an orbit are either all feasible or all infeasible. Proof. For an arbitrary active set A, let the sets Fx(0)(A) and FU(A)contain all initial states x(0) and input vectors U, respectively, such that a solution to LP (4) without (4b) and (4c) exists, i.e., Fx(0)(A)× FU(A) := (x(0), U)∈Rn×RNm | GAU+EAx(0) + wA= 0, GIU+EIx(0) + wI≤0}. An active set Athat is feasible results in Fx(0)(A)× FU(A)6=∅, an active set Athat is infeasible results in Fx(0)(A)× FU(A) = ∅. Consider an orbit Oand two of its elements Ai,Aj∈ O. The proof is done by showing that if Fx(0)(Ai)× FU(Ai) = ∅then Fx(0)(Aj)× FU(Aj) = ∅and if Fx(0)(Ai)× FU(Ai)6=∅then Fx(0)(Aj)× FU(Aj)6=∅. Active sets Aiand Ajare considered to be elements of the same orbit which implies there exists a pair (Θ,Ω) ∈ G such that Aj= Π(Θ,Ω)(Ai). It holds Fx(0)(Aj) = Θ ◦ Fx(0)(Ai),FU(Aj) = Ω ◦ FU(Ai)(8) since pair (Θ,Ω) causes transformations of the inputand state-space with Ωand Θ, respectively. Equation (8) implies either both sets Fx(0)(Aj)and Fx(0)(Ai)are empty or both are not empty and, in the same way, either both sets FU(Aj) and FU(Ai)are empty or both are not empty. Corollary 1 enables adding the whole orbit to set Swhenever an active set is detected as infeasible. To keep the number of elements in set Ssmall, orbit elements are only added to S if they are not already a superset of a detected infeasible active set in S(line 23–26 in Alg. 3). Due to the larger number of detected infeasible active sets in S, the effectiveness of pruning increases. It is therefore advantageous to dismiss candidates that are supersets of detected infeasible active sets (pruning) 51 first (line 4) and dismiss candidates which are descendants of detected non-primary active sets second (line 5). It follows that we need not store non-primary sets that are infeasible in Nbecause these candidates are dismissed by pruning in line 4 and never appear in line 5. Therefore, lines 17–19 from Alg. 2 are implemented in lines 13–15 and 19–21 in Alg. 3. Algorithm 3: Improved combinatorial approach 2 1Initialization: set M=∅,S=∅,N=∅ 2for every A ∈ PNm(Q)by incr. cardinality and by incr. constraint indices do 3if rank(GA) = |A| then 4if A 6⊇ ˜ Afor all ˜ A ∈ S then 5if A 6∈ D(¯ A)for all ¯ A∈ N then 6solve (4) 7if solution exists then 8if solution t⋆>0then 9add elements of O(A)to M 10 else 11 if polytope def. by Ais full-dim then 12 add elements of O(A)to M 13 for every ˘ A ∈ O(A)\A do 14 if ˘ A 6∈ D(¯ A)for all ¯ A∈ N then 15 add ˘ Ato N 16 else 17 solve (4) without (4b) and (4c) 18 if solution exists then 19 for every ˘ A ∈ O(A)\A do 20 if ˘ A 6∈ D(¯ A)for all ¯ A∈ N then 21 add ˘ Ato N 22 else 23 for every ˘ A ∈ O(A)do 24 if ˘ A 6⊇ ˜ Afor all ˜ A ∈ S then 25 add ˘ Ato S 26 Output: M The changes implemented in Alg. 3 cause two things compared to Alg. 2: Firstly, the set Ncontains fewer elements because infeasible active sets are not elements anymore. This makes the test in lines 5, 14, and 20 less expensive. Secondly, testing if a candidate is a descendant of a detected nonprimary active set is executed less often because the testing if a candidate is a descendant of a detected infeasible active set is executed before and dismisses many candidates already. V. COMPUTATIONAL ANALYSIS We analyze the computational effort of Algs. 2 and 3 with two examples and compare them to the original approach from [1] (Alg. 1). Example 1. Consider the system [20, Example 1] x(k+ 1) = 2 1 −1 2x(k) + I2u(k), with input and state constraints |ui(k)| ≤ 1,i= 1,2, and |xi(k)| ≤ 1,i= 1,2, respectively, weighting matrices Q=I2, R= 5,000 ·I2, and prediction horizon N= 3. The terminal weighting matrix Pand set Tare as described in Sect. II. TABLE I: Computational data for Example 1 Algorithm 1 Algorithm 2 Algorithm 3 # solved LPs 11,969 3,059 3,043 # test pruning 47,545 11,887 47,647 # test descendant 0 83,202 13,755 computing time 77.8s26.0s23.6s TABLE II: Computational data for Example 2 Algorithm 1 Algorithm 2 Algorithm 3 # solved LPs 111,681 14,197 14,149 # test pruning 3,264,401 408,051 3,265,129 # test descendant 0 6,120,750 266,252 computing time 1,001 s706 s478 s Example 1 has four pairs (Θi,Ωi)∈ G,i= 1, ..., 4, that satisfy (5). The pairs correspond to rotations of the inputand state-space by ϕ1= 0◦,ϕ2= 90◦,ϕ3= 180◦, and ϕ4= 270◦ with (Θi,Ωi) = cos(ϕi)−sin(ϕi) sin(ϕi) cos(ϕi), cos(ϕi)−sin(ϕi) sin(ϕi) cos(ϕi). (9) All algorithms process |PNm(Q)|= 499,178 candidates and determine the solution with |M| = 73 elements. Rank tests are executed for each of the candidates by all algorithms. The remaining computing operations of the algorithms can be summarized to be the number of solved LPs to test for optimality with (4) and feasibility with (4) without (4b) and (4c), the number of tests to test if a candidate is a superset of a detected infeasible active set (test pruning) and the number of tests to test if a candidate is a descendant of a detected non-primary active set (test descendant). These numbers differ with the different procedures of the algorithms and are listed in Tab. I together with the computing times. We introduce a second example with more symmetries. Example 2. Consider the system x(k+ 1) = 1 1 −1 1x(k) + I2u(k), with weighting matrices Q, R =I2and prediction horizon N= 3, and where the constraint sets for inputs and states are octagons with spans 20 and 2, respectively, that are centered at the origin. The terminal weighting matrix Pand set Tare as described in Sect. II. Example 2 has eight pairs (Θi,Ωi)∈ G,i= 1, ..., 8, that satisfy (5). The pairs correspond to rotations of the inputand state-space by ϕ1= 0◦,ϕ2= 45◦,ϕ3= 90◦,ϕ4= 135◦, ϕ5= 180◦,ϕ6= 225◦,ϕ7= 270◦, and ϕ8= 315◦with (9). All algorithms process |PNm(Q)|= 36,684,859 candidates for Example 2 and determine the solution with |M| = 97 elements. Other computational data is listed in Tab. II. It is evident from the data in Tabs. I and II that Algs. 2 and 3 require less computing time than Alg. 1. The reduction 52 mainly results because fewer LPs are solved for Algs. 2 and 3 than for Alg. 1 and solving the LPs occupies a large share of the computing time. All algorithms generally dismiss candidates Asuch that matrix GAis row rank deficient and that are supersets of detected infeasible active sets from solving an LP. Algorithms 2 and 3 additionally do not solve LPs for non-primary candidates such that all but one active set out of each orbit are dismissed from solving an LP. The number of elements of an orbit depends on the number of symmetries of the problem. Considering an OCP with g symmetries, each orbit contains up to gelements, see (7), so the number of solved LPs for Algs. 2 and 3 decreases to about 1/g compared to Alg. 1. However, Algs. 2 and 3 require additional computational effort for executing tests descendant. This effort diminishes the reduction of computational time, so the reduction in the computing times of Algs. 2 and 3 when compared to Alg. 1 is smaller than the reduction in the number of solved LPs. We will focus on that in the next paragraph. Furthermore, the data in Tabs. I and II reveal that Alg. 3 requires less computing time than Alg. 2, for the highly symmetric Example 2 in particular. The differences result from the different numbers of executed tests pruning and tests descendant. In Alg. 2, tests descendant are executed for all candidates Asuch that matrix GAhas full row rank (line 4) and for all elements of the orbits of active sets that satisfy the rank criterion and that are primary (line 17). In Alg. 3, in contrast, tests descendant are executed for all candidates that satisfy the rank criterion and that are not supersets of detected infeasible active sets (line 5) and for all elements of the orbits of active sets that satisfy the rank criterion and that are primary and feasible (lines 14, 20). It follows that Alg. 3 executes fewer tests descendant than Alg. 2 since the criteria for the candidates being tested are more restrictive. Furthermore, executing a test descendant in Alg. 3 requires less computational effort than in Alg. 2 because Ncontains only feasible active sets and therefore fewer elements. In Alg. 2 tests pruning are executed for all candidates Asuch that matrix GAhas full row rank and that are non-primary (line 5) while Alg. 3 executes test pruning for all candidates that satisfy the rank criterion (line 4) and for all elements of the orbits of active sets that satisfy the rank criterion, that are not dismissed by test pruning, and that are primary and infeasible (line 24). As a result, the numbers of tests pruning for Alg. 2 are almost decreased by factor gcompared to Alg. 3. In summary, Alg. 3 results in fewer tests descendant than Alg. 2 but more tests pruning. The more symmetries a problem has, the more the ratio between computational savings and expenditures shifts towards savings for Alg. 3 making Alg. 3 the more effective approach. VI. CONCLUSION We applied the methods from [17] for improving combinatorial approaches for symmetric OCPs to the approach from [1]. The improved approach requires fewer LPs to be solved resulting in a lower computational effort. The number of solved LPs drops by a factor of g, the number of symmetries of the OCP. However, the approach requires additional computing operations which counteract the reduction of the computational effort. These operations occur frequently for OCPs with many symmetries. For this reason, we presented a second approach that makes pruning more effective by taking symmetric feasibility properties into account. This results in fewer required additional computing operations. For OCPs with many symmetries, the second approach showed to be the approach that requires less computational effort. REFERENCES [1] A. Gupta, S. Bhartiya, and P. Nataraj, “A novel approach to multiparametric quadratic programming,” Automatica, vol. 47, pp. 2112–2117, 2011. [2] A. Bemporad, M. Morari, V. Dua, and E. N. Pistikopoulos, “The explicit linear quadratic regulator for constrained systems,” Automatica, vol. 38, pp. 3–20, 2002. [3] M. M. Seron, G. C. Goodwin, and J. A. De Don´a, “Characterisation of receding horizon control for constrained linear systems,” Asian Journal of Control, vol. 5, pp. 271–286, 2003. [4] P. Tøndel, T. A. Johanson, and A. Bemporad, “An algorithm for multi-parametric quadratic programming and explicit MPC solutions,” Automatica, vol. 39, pp. 489–497, 2003. [5] M. Baoti´c, “An efficient algorithm for multi-parametric quadratic programming,” ETH Z¨urich, Tech. Rep., 2002, AUT02-05. [6] M. Herceg, M. Kvasnica, C. N. Jones, and M. Morari, “MultiParametric Toolbox 3.0,” in Proc. of the European Control Conference, Z¨urich, Switzerland, July 17–19 2013, pp. 502–510, http://control.ee.ethz.ch/∼mpt. [7] A. Bemporad, “Hybrid Toolbox - User’s Guide,” 2004, http://cse.lab.imtlucca.it/∼bemporad/hybrid/toolbox. [8] M. Herceg, C. N. Jones, M. Kvasnica, and M. Morari, “Enumerationbased approach to solving parametric linear complementarity problems,” Automatica, vol. 62, pp. 243–248, 2015. [9] R. Oberdieck, N. A. Diangelakis, and E. N. Pistikopoulos, “Explicit model predictive control: A connected-graph approach,” Automatica, vol. 76, pp. 103–112, 2017. [10] P. Ahmadi-Moshkenani, T. A. Johansen, and S. Olaru, “Combinatorial approach toward multiparametric quadratic programming based on characterizing adjacent critical regions,” IEEE Transactions on Automatic Control, vol. 63, no. 10, pp. 3221–3231, Oct 2018. [11] M. M¨onnigmann, “On the structure of the set of active sets in constrained linear quadratic regulation,” Automatica, vol. 106, pp. 61–69, 2019. [12] R. Mitze and M. M¨onnigmann, “Improved active set dynamic programming for solving linear-quadratic optimal control problems,” in 2022 IEEE 61st Conference on Decision and Control (CDC), 2022, pp. 1764– 1769. [13] C. R. Danielson and F. Borrelli, “Symmetric Linear Model Predictive Control,” IEEE Transactions on Automatic Control, vol. 60, no. 5, pp. 1244–1259, 2015. [14] C. Feller, T. A. Johanson, and S. Olaru, “An improved algorithm for combinatorial multi-parametric quadratic programming,” Automatica, vol. 49, pp. 1370–1376, 2013. [15] R. Mitze and M. M¨onnigmann, “A dynamic programming approach to solving constrained linear-quadratic optimal control problems,” Automatica, vol. 120, p. 109132, 2020b. [16] R. Mitze and M. M¨onnigmann, “Dynamic programming for explicit linear MPC with point-symmetric constraints,” in 21st IFAC World Congress, Berlin, 2020a, pp. 6999–7004. [17] R. Mitze, M. Kvasnica, and M. M¨onnigmann, “Exploiting symmetries in active set enumeration for constrained linear-quadratic optimal control,” Automatica, vol. 151, p. 110900, 2023. [18] R. Rymon, “Search through systematic set enumeration,” in Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR’92), 1992, pp. 539–550. [19] C. R. Danielson and F. Borrelli, “Identification of the symmetries of linear systems with polytopic constraints,” in Proc. of the American Control Conference, 2014, pp. 4218–4223. [20] C. R. Danielson and F. Borrelli, “Symmetric explicit model predictive control,” IFAC Proceedings Volumes, vol. 45, no. 17, pp. 132–137, 2012. 53