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

Exploi ing symme ies in ee-based combina o ial
calcula ion o explici linea MPC solu ions
1s Ru h Mi ze
Dep. o Mechanical Enginee ing
Ruh -Uni e si ¨
a Bochum
Bochum, Ge many
[email p o ec ed]
2nd Ma in M¨onnigmann
Dep. o Mechanical Enginee ing
Ruh -Uni e si ¨
a Bochum
Bochum, Ge many
[email p o ec ed]
Abs ac —Symme ies o linea MPC p oblems a e e lec ed in
symme ies o hei explici solu ions. We ecen ly showed hese
symme ies also appea in he se o he ac i e se s ha de ine
he explici solu ion. Consequen ly, symme ies can be used o
speed up algo i hms o he calcula ion o he se o ac i e se s.
In his pape , we exploi symme ies o accele a e he app oach
om [1] by imp o ing he explo a ion o he combina o ial ee
o ac i e se s. The educ ions o he compu a ional e o ha
can be achie ed a e illus a ed and analyzed wi h wo examples.
Index Te ms—Explici linea model p edic i e con ol, com-
bina o ial pa ame ic quad a ic p og amming, symme ic con-
s ained op imiza ion
I. INTRODUCTION
Explici linea model p edic i e con ol (MPC) equi es he
pa ame ic solu ion o a cons ained linea -quad a ic op imal
con ol p oblem (OCP), which is known o be con inuous
piecewise-a ine eedback law [2], [3]. Pa icula ly o high-
o de p oblems, o p oblems wi h many cons ain s, and
o p oblems wi h long p edic ion ho izons, calcula ing he
solu ion is compu a ionally demanding. Reducing he com-
pu a ional e o o calcula ing he solu ion is he ocus o
an en i e ield o esea ch. The i s app oaches p oposed o
his ask exploi geome ic ela ions o he a ine pieces in he
solu ion [2], [4], [5]. These app oaches a e compe i i e and
implemen ed in ma u e so wa e oolboxes [6], [7]. Howe e ,
hey equi e p ope uning o p e en missing ou on small
pieces o he piecewise-a ine eedback law. An al e na i e
app oach was p oposed by [1] and calcula es he se o ac i e
se s ha de ine an a ine piece in he solu ion. The app oach
p oceeds by enume a ing possible ac i e se candida es and
examining hem o being an elemen o he solu ion. Se e al
e inemen s o he app oach om [1] ha e been p oposed.
They exploi ela ions among he elemen s in he se o
ac i e se s o a mo e a ge ed selec ion and examina ion
o he ac i e se candida es, hus educing he compu a ional
complexi y [8]–[12]. App oaches ha calcula e he solu ion by
enume a ing and examining ac i e se candida es a e known as
combina o ial app oaches o implici enume a ion echniques.
Suppo by he Eu opean Commission unde g an no. 101079342 (Fos e -
ing Oppo uni ies Towa ds Slo ak Excellence in Ad anced Con ol o Sma
Indus ies) is g a e ully acknowledged.
Combina o ial app oaches o en o de he ac i e se s ha a e
candida es o he solu ion in a combina o ial ee.
Symme ies o a physical sys em and i s cons ain s o en
esul in symme ies o he associa ed cons ained linea -
quad a ic OCP. Symme ies o he OCP a e hen e lec ed
in inpu - and s a e-space ans o ma ions in he associa ed
piecewise-a ine eedback law [13]. Fo p oblems wi h con-
s ain s ha a e poin -symme ic o he o igin, symme ies
we e iden i ied in he ac i e se s [14] and used o imp o e
he combina o ial app oaches om [1] and [15] in [14] and
[16], espec i ely. Fo p oblems wi h gene al symme ies,
symme ies in he ac i e se s we e iden i ied only ecen ly and
a s a egy o imp o e combina o ial app oaches o symme ic
OCPs was p oposed [17].
In his wo k, we use he s a egy p oposed in [17] o
imp o e he combina o ial app oach om [1]. This app oach
uses a combina o ial ee o enume a e he ac i e se s ha
a e candida es o he solu ion. Also, we p opose a change
o he s a egy ha makes he examina ion mo e e icien .
This change u he educes he compu a ional e o , o
p oblems wi h many symme ies in pa icula . Reduc ions o
he compu a ional e o a e analyzed by applying he app oach
o di e en examples.
Sec ion II in oduces cons ained linea -quad a ic OCPs
and he combina o ial app oach om [1]. Sec ion III de ines
symme ies o OCPs and in oduces he explo a ion s a egy
o imp o e combina o ial app oaches p oposed by [17]. Sec-
ion IV p esen s wo app oaches simila o [1] bu imp o ed
o symme ic OCPs. The new app oaches a e applied o wo
examples in Sec . V and he compu a ional e o is analyzed.
Finally, Sec . VI concludes his pape .
No a ion: Le Ia∈Ra×adeno e he iden i y ma ix and
1a∈Raa column ec o o ones. Fu he mo e, le Pc(M) =
{m∈ P(M)| |m| ≤ c}, whe e P(M) e e s o he powe se
o se M. Fo a ma ix A∈Rm×nand o de ed se M ⊆
{1, ..., a}, we deno e by AM∈R|M|×n he subma ix o A
con aining all ows indica ed by M. Le ope a o s ⊗and ×
deno e he K onecke and Ca esian p oduc , espec i ely, and
le A◦ M ={Am |m∈ M}. Fu he mo e, le max(M)and
min(M)deno e he g ea es and smalles elemen o he se
M, espec i ely, whe e applicable. We say se s Mand N
pa i ion Ri M ∪ N =Rand M ∩ N =∅.
2023 24 h In e na ional Con e ence on P ocess Con ol (PC)
June 6–9, 2023, Š bské Pleso, Slo akia
979-8-3503-4763-0/23/$31.00 ©2023 IEEE 48
II. PROBLEM STATEMENT AND PRELIMINARIES
This pape ea s ini e-ho izon cons ained linea -quad a ic
OCPs o he o m
min
U,X kx(N)k2
P+
N−1
X
k=0 kx(k)k2
Q+ku(k)k2
R(1a)
s. . 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)
wi h s age k∈N0, p edic ion ho izon N∈N, in-
pu u(k)∈Rm, s a e x(k)∈Rn, column ec o s
U=uT(0), ..., uT(N−1)T∈RNm and X=
xT(1), ..., xT(N)T∈RNn, weigh ing ma ices o inpu s
R∈Rm×m, s a es Q∈Rn×n, and e minal s a e P∈Rn×n,
sys em ma ices A∈Rn×nand B∈Rn×mo he disc e e-
ime ime-in a ian linea sys em, and cons ain se o inpu s
U ⊂ Rm, s a es X ⊂ Rn, and he e minal s a e T ⊂ Rn.
We assume he ini ial s a e x(0) is gi en, ma ices Rand Q
a e such ha R≻0and Q0,(A, B)is s abilizable, se s U
and Xa e compac ull-dimensional poly opes ha con ain he
o igin in hei in e io s, and ma ix Pand se Ta e he op imal
cos unc ion ma ix o he uncons ained in ini e-ho izon
p oblem which implies P≻0, and he la ges possible se
such ha he op imal eedback o he uncons ained in ini e-
ho izon p oblem s abilizes he sys em wi hou iola ing he
cons ain s, espec i ely.
Subs i u ing sys em (1b) in OCP (1) enables o ew i e he
OCP as he quad a ic p og am (QP)
min
U
1
2UTHU +x(0)TFU +1
2x(0)TY x(0)
s. . GU ≤Ex(0) + w,
(2)
wi h H∈RNm×Nm,F∈Rn×Nm,Y∈Rn×n,G∈Rq×Nm,
E∈Rq×n, and w∈Rq. The assump ions on OCP (1) imply
H≻0in QP (2) [2]. Wi hou es ic ion, we assume he
inequali y cons ain s in QP (2) a e o mula ed such ha w=
1q.
Le q e e o he numbe o inequali ies in QP (2) and le
Q:= {1, ..., q}deno e he index se . Fu he mo e, le se s
A(x(0)) and I(x(0)) deno e he op imal ac i e and inac i e
se o any x(0) such ha QP (2) has a solu ion, espec i ely,
wi h
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 whe e U⋆(x(0)) deno es he op imal solu ion o he QP.
We o en d op x(0) in he no a ion o an ac i e and inac i e
se , and call an ac i e se Aop imal i i e e s o he op imal
solu ion U⋆(x(0)) o some x(0) wi h (3a).
Sol ing QP (2) as a pa ame ic p og am, whe e he pa am-
e e is he ini ial s a e x(0), esul s in he op imal con ol law
x(0) 7→ U⋆(x(0)) which is a con inuous piecewise a ine
unc ion o x(0) on a poly opic pa i ion o he easible
pa ame e space [2, Sec . 4.1]. The a ine pieces in he solu ion
a e ep esen ed by op imal ac i e se s A ha de ine ull-
dimensional s a e-space poly opes and such ha ma ix GA
has ull ow ank. We collec all ac i e se s ha sa is y hese
condi ions in he solu ion se M.
A. Combina o ial app oach om [1]
The powe se P(Q)con ains all possible cons ain com-
bina ions o , equi alen ly, all possible ac i e se s. I ollows
ha M ⊆ P(Q). By de ini ion o M, all elemen s A ∈
Ma e such ha he ma ix GAhas ull ow ank. Since
GA∈R|A|×Nm, he ank o ma ix GAis bounded om
abo e by min (|A|, Nm). I ollows ha ac i e se s Awi h
|A| > Nm esul in ow ank de icien GA. Consequen ly,
M ⊆ PNm(Q). The combina o ial app oach om [1] con-
side s he ac i e se s A ∈ PNm(Q)as candida es o he
solu ion.
Figu e 1 shows a oo ed ee ha ep esen s he candida es
in PNm(Q). The ee was i s p oposed by [18, De . 2.2] and
is used by many combina o ial app oaches [1], [10], [14]. We
e e o he ee as a combina o ial ee. The combina o ial
ee is o ganized such ha candida es o iden ical ca dinali ies
appea in he same le el and candida es con aining he lowes
cons ain indices appea le mos wi hin each le el wi hou
es ic ion. Le he se o candida es in he sub ee o a
candida e A, i.e., all descendan s o Aand Ai sel be deno ed
D(A),
D(A) := nA ∪ ˜
A | ˜
A ∈ P({max(A) + 1, ..., q})o.
Fig. 1: Combina o ial ee o a bi a y OCP wi h q= 4
cons ain s.
The solu ion Mis calcula ed by collec ing all candida es
A ∈ PNm(Q) ha sa is y he ollowing condi ions: (i) GA
has ull ow ank, (ii) Ais op imal, and (iii) Ade ines a
ull-dimensional poly ope. The app oach om [1] is s a ed in
Alg. 1. I explo es all candida es in he o de o inc easing
ca dinali y (line 2 in Alg. 1). When ans e ed o he com-
bina o ial ee in oduced be o e, he elemen s in he ee a e
explo ed om op o bo om. Fo each candida e, a ank es is
execu ed o es o condi ion (i) (line 3). Candida es Asuch
49
ha ma ix GAis ow ank de icien a e dismissed. To es o
condi ion (ii), he linea p og am (LP) (4) is sol ed (line 5),
min
U,x(0),λA,sI, − (4a)
s. . FTx(0) + HU + (GA)TλA= 0,(4b)
1|A| ≤λA,(4c)
GAU−EAx(0) −wA= 0,(4d)
GIU−EIx(0) −wI+sI= 0,(4e)
1|I| ≤sI, ≥0,(4 )
wi h Lag ange mul iplie s λAand slack a iables sI. Can-
dida es such ha LP (4) has a solu ion a e op imal, and
no op imal o he wise. I a solu ion o (4) exis s, we deno e
co esponding op imiza ion a iables U⋆,x⋆(0),λ⋆
A,s⋆
I, and
⋆. The ollowing p ocedu e enables he app oach o iden i y
many candida es a a ime ha a e no op imal: Fo all
candida es such ha LP (4) has no solu ion, we sol e LP (4)
wi hou (4b) and (4c) (lines 12–13). We call candida es such
ha his LP has a solu ion easible, and in easible o he wise.
In easible ac i e se s a e no op imal because he LP o es
o easibili y in ol es only a subse o he cons ain s o he
LP o es o op imali y. The se Scollec s candida es ha
a e de ec ed as in easible (lines 14–15). Ac i e se s A ha
a e supe se s o in easible ac i e se s a e in easible wi h [1,
Thm. 1], and hus no op imal. Dismissing candida es because
hey a e supe se s o de ec ed in easible ac i e se s (line 4) is
u he e e ed o as p uning. To es o he las condi ion
(iii), i su ices o es candida es ha esul in ⋆= 0 o
de ining a ull-dimensional poly ope (lines 9–11). Candida es
ha esul in ⋆>0de ine ull-dimensional poly opes wi h [4,
Thm. 2] since his esul implies s ic inequali y o 0< λ⋆
A
and GIU⋆−EIx⋆(0) −wI<0(lines 7–8).
Algo i hm 1: Combina o ial app oach om [1]
1Ini ializa ion: se M=∅,S=∅
2 o e e y A ∈ PNm(Q)by inc . ca dinali y do
3i ank(GA) = |A| hen
4i A 6⊇ ˜
A o all ˜
A ∈ S hen
5sol e (4)
6i solu ion exis s hen
7i solu ion ⋆>0 hen
8add A o M
9else
10 i poly ope de . by Ais ull-dim. hen
11 add A o M
12 else
13 sol e (4) wi hou (4b) and (4c)
14 i no solu ion exis s hen
15 add A o S
16 Ou pu : M
III. SYMMETRIC OCPS AND STRATEGY FOR
COMBINATORIAL TREE
We ollow [13, De . 4] and call an OCP (1) symme ic o
he pai (Θ,Ω), whe e ma ices Θ∈Rn×nand Ω∈Rm×m
a e in e ible, i he condi ions
ΘA=AΘ,ΘB=BΩ,
Θ◦ X =X,Ω◦ U =U,Θ◦ T =T,
ΘTQΘ = Q, ΩTRΩ = R, ΘTPΘ = P
(5)
hold. No e ha symme ies o he sys em ma ices and con-
s ain se s in (5) esul om symme ies o he unde lying
physical sys em and i s cons ain s, espec i ely, and he
weigh ing ma ices can o en be chosen o comply wi h some
desi ed symme y p ope ies. A me hod o he iden i ica ion
o all pai s (Θ,Ω) ha sa is y condi ions (5) o an OCP (1)
was p oposed by [19]. We collec all pai s (Θ,Ω) ha sa is y
condi ions (5) o an a bi a y bu ixed OCP (1) in he se
G. Each pai (Θ,Ω) ∈ G causes he op imal con ol law o
OCP (1) o be in a ian unde ans o ma ions o he inpu -
and s a e-space wi h Ωand Θ, espec i ely [13].
Conside an OCP (1) ha is e o mula ed as QP (2) wi h
w= 1qand a pai (Θ,Ω) ∈ G. Wi h ega d o he cons ain s
in he QP (2), e e y cons ain i∈ Q has a symme ic
cons ain j∈ Q such ha
G{i}=G{j}·IN⊗Ωand E{i}=E{j}·Θ(6)
[17, Thm. 2]. We in oduce he unc ion π(Θ,Ω) :Q → Q
o ep esen he ela ions j=π(Θ,Ω)(i) om (6). Also, we
in oduce he unc ion Π(Θ,Ω) :P(Q)→ P(Q) o map all
cons ain s in an ac i e se A ∈ P(Q) o hei co esponding
symme ic cons ain s wi h π(Θ,Ω). We call he ac i e se Aj=
Π(Θ,Ω)(Ai) he symme ic ac i e se o Aiunde pai (Θ,Ω).
Le he o bi O(A)collec he symme ic ac i e se s o an
ac i e se Aunde all pai s (Θ,Ω) ∈ G,
O(A) := nΠ(Θ,Ω)(A)|(Θ,Ω) ∈ G o.(7)
We o en d op he a gumen Ain he no a ion o an o bi .
I was shown in [17] ha he o bi s o all ac i e se s in
P(Q)pa i ion P(Q). Likewise, he o bi s o all ac i e se s
in PNm(Q)pa i ion PNm(Q)since he elemen s o an
o bi ha e iden ical ca dinali ies. I ollows ha he se o
candida es o he combina o ial app oach om [1] in oduced
in Sec . II-A pa i ions in o o bi s.
All elemen s o an o bi ha e p ope ies in common [17,
Thm. 4] ha a e ele an o combina o ial app oaches:
1) The elemen s o an o bi a e ei he all op imal o all no
op imal.
2) The poly opes de ined by he elemen s o an o bi a e
ei he all ull-dimensional o all lowe -dimensional in
s a e-space.
I is sugges ed by [17] o imp o e combina o ial app oaches
by only es ing one ac i e se and i s poly ope o each o bi o
op imali y and ull-dimensionali y, espec i ely, and applying
he esul o all ac i e se s in he o bi . Howe e , i is no i ial
o e icien ly iden i y ac i e se s ha can be dismissed om
es ing. The ollowing s a egy is sugges ed by [17]: Fo each
o bi O, we call he ac i e se con aining he lowes cons ain
indices, i.e.,
A ∈ O : min(A ˜
A)<min( ˜
A A)∀˜
A ∈ O A
50
he p ima y ac i e se . Acco dingly, all o bi elemen s excep
o he p ima y ac i e se a e non-p ima y. I is su icien
o p ocess only he p ima y ac i e se and dismiss all o he
ac i e se s o he o bi om es ing. Assuming all ac i e se s
ha a e candida es a e explo ed in he o de o inc easing
ca dinali y and inc easing cons ain indices (when ans e ed
o he combina o ial ee, his s a egy is om op o bo om
and in each le el om le o igh ), he p ima y ac i e se o
each o bi is eached i s . The esidual elemen s o he o bi s
a e non-p ima y and can he e o e be dismissed. Wi h [17,
Thm. 5], he ac i e se s o he sub ee D(A)a e non-p ima y
i he oo o he sub ee Ais non-p ima y. We e e o [17,
Example 6] o an illus a i e example.
IV. IMPROVED COMBINATORIAL APPROACHES
Based on he s a egy desc ibed in Sec . III, we imp o e
he combina o ial app oach om [1] in oduced as Alg. 1 in
Sec . II-A. The imp o emen o he app oach is achie ed by
only p ocessing p ima y and dismissing non-p ima y candi-
da es. The comple e solu ion s ill esul s because he whole
o bi is added o he solu ion Mwhene e a p ima y candida e
is de ec ed o be pa o M.
The imp o ed app oach is s a ed in Alg. 2. I p ocesses all
candida es A ∈ PNm(Q)in he o de o inc easing ca dinali y
and inc easing cons ain indices (line 2 in Alg. 2). This way,
he p ima y candida e o each o bi is p ocessed i s . The
se Ncollec s candida es ha a e de ec ed as non-p ima y.
Any candida e Asuch ha A ∈ D(¯
A) o an ¯
A ∈ N is
non-p ima y and hus dismissed (line 4). All elemen s o he
o bi o a p ima y candida e, excep he p ima y candida e
i sel , a e non-p ima y. To keep he numbe o elemen s in
Nsmall, a non-p ima y candida e is only added o Ni he
candida e is no al eady an elemen o a se D(¯
A),¯
A ∈ N
(lines 17–19). All o he lines in Alg. 2 (lines 3, 5–16, 20)
emain unchanged om Alg. 1 bu add he whole o bi o he
solu ion Mwhene e a candida e is de ec ed o be pa o M
(lines 9, 12).
Sol ing he LPs accoun s o a la ge sha e o he compu ing
ime. The numbe o sol ed LPs o Alg. 2 is almos educed
by ac o g, he numbe o symme ies, which will be explained
in mo e de ail in Sec . V. Howe e , Alg. 2 execu es addi ional
compu a ional ope a ions ha coun e ac he educ ion o
compu a ional ime, mos no ably he es s in lines 4 and 18
o es i an ac i e se is a descendan o a de ec ed non-
p ima y ac i e se . The addi ional compu a ional e o is mos
e iden o examples wi h a la ge numbe o symme ies o
wo easons: Fi s ly, he se Ncon ains mo e elemen s because
a la ge numbe o symme ies en ails a la ge numbe o non-
p ima y ac i e se s. Thus, he es in lines 4 and 18 is mo e
expensi e. Secondly, he la ge he numbe o symme ies he
la ge he numbe o elemen s o an o bi . Thus, he o loop
s a ing in line 17 uns mo e o en.
We sugges a di e en p ocedu e in Alg. 3 ha ob ia es
hese issues and need Co . 1 as a p epa a ion. I ex ends he
p ope ies ha elemen s o an o bi ha e in common by he
p ope y easibili y.
Algo i hm 2: Imp o ed combina o ial app oach 1
1Ini ializa ion: se M=∅,S=∅,N=∅
2 o e e y A ∈ PNm(Q)by inc . ca dinali y and by inc . cons ain
indices do
3i ank(GA) = |A| hen
4i A 6∈ D(¯
A) o all ¯
A∈ N hen
5i A 6⊇ ˜
A o all ˜
A ∈ S hen
6sol e (4)
7i solu ion exis s hen
8i solu ion ⋆>0 hen
9add elemen s o O(A) o M
10 else
11 i poly ope de . by Ais ull-dim hen
12 add elemen s o O(A) o M
13 else
14 sol e (4) wi hou (4b) and (4c)
15 i no solu ion exis s hen
16 add A o S
17 o e e y ˘
A ∈ O(A) A do
18 i ˘
A 6∈ D(¯
A) o all ¯
A∈ N hen
19 add ˘
A o N
20 Ou pu : M
Co olla y 1. Conside an OCP (1). The ac i e se s o an o bi
a e ei he all easible o all in easible.
P oo . Fo an a bi a y ac i e se A, le he se s Fx(0)(A)
and FU(A)con ain all ini ial s a es x(0) and inpu ec o s U,
espec i ely, such ha a solu ion o LP (4) wi hou (4b) and
(4c) exis s, i.e.,
Fx(0)(A)× FU(A) := (x(0), U)∈Rn×RNm |
GAU+EAx(0) + wA= 0, GIU+EIx(0) + wI≤0}.
An ac i e se A ha is easible esul s in Fx(0)(A)×
FU(A)6=∅, an ac i e se A ha is in easible esul s in
Fx(0)(A)× FU(A) = ∅. Conside an o bi Oand wo o i s
elemen s Ai,Aj∈ O. The p oo is done by showing ha i
Fx(0)(Ai)× FU(Ai) = ∅ hen Fx(0)(Aj)× FU(Aj) = ∅and
i Fx(0)(Ai)× FU(Ai)6=∅ hen Fx(0)(Aj)× FU(Aj)6=∅.
Ac i e se s Aiand Aja e conside ed o be elemen s o he
same o bi which implies he e exis s a pai (Θ,Ω) ∈ G such
ha Aj= Π(Θ,Ω)(Ai). I holds
Fx(0)(Aj) = Θ ◦ Fx(0)(Ai),FU(Aj) = Ω ◦ FU(Ai)(8)
since pai (Θ,Ω) causes ans o ma ions o he inpu - and
s a e-space wi h Ωand Θ, espec i ely. Equa ion (8) implies
ei he bo h se s Fx(0)(Aj)and Fx(0)(Ai)a e emp y o bo h
a e no emp y and, in he same way, ei he bo h se s FU(Aj)
and FU(Ai)a e emp y o bo h a e no emp y.
Co olla y 1 enables adding he whole o bi o se Swhen-
e e an ac i e se is de ec ed as in easible. To keep he numbe
o elemen s in se Ssmall, o bi elemen s a e only added o S
i hey a e no al eady a supe se o a de ec ed in easible ac i e
se in S(line 23–26 in Alg. 3). Due o he la ge numbe o
de ec ed in easible ac i e se s in S, he e ec i eness o p uning
inc eases. I is he e o e ad an ageous o dismiss candida es
ha a e supe se s o de ec ed in easible ac i e se s (p uning)
51
i s (line 4) and dismiss candida es which a e descendan s o
de ec ed non-p ima y ac i e se s second (line 5). I ollows
ha we need no s o e non-p ima y se s ha a e in easible in
Nbecause hese candida es a e dismissed by p uning in line 4
and ne e appea in line 5. The e o e, lines 17–19 om Alg. 2
a e implemen ed in lines 13–15 and 19–21 in Alg. 3.
Algo i hm 3: Imp o ed combina o ial app oach 2
1Ini ializa ion: se M=∅,S=∅,N=∅
2 o e e y A ∈ PNm(Q)by inc . ca dinali y and by inc . cons ain
indices do
3i ank(GA) = |A| hen
4i A 6⊇ ˜
A o all ˜
A ∈ S hen
5i A 6∈ D(¯
A) o all ¯
A∈ N hen
6sol e (4)
7i solu ion exis s hen
8i solu ion ⋆>0 hen
9add elemen s o O(A) o M
10 else
11 i poly ope de . by Ais ull-dim hen
12 add elemen s o O(A) o M
13 o e e y ˘
A ∈ O(A) A do
14 i ˘
A 6∈ D(¯
A) o all ¯
A∈ N hen
15 add ˘
A o N
16 else
17 sol e (4) wi hou (4b) and (4c)
18 i solu ion exis s hen
19 o e e y ˘
A ∈ O(A) A do
20 i ˘
A 6∈ D(¯
A) o all ¯
A∈ N hen
21 add ˘
A o N
22 else
23 o e e y ˘
A ∈ O(A)do
24 i ˘
A 6⊇ ˜
A o all ˜
A ∈ S hen
25 add ˘
A o S
26 Ou pu : M
The changes implemen ed in Alg. 3 cause wo hings
compa ed o Alg. 2: Fi s ly, he se Ncon ains ewe elemen s
because in easible ac i e se s a e no elemen s anymo e. This
makes he es in lines 5, 14, and 20 less expensi e. Secondly,
es ing i a candida e is a descendan o a de ec ed non-
p ima y ac i e se is execu ed less o en because he es ing i
a candida e is a descendan o a de ec ed in easible ac i e se
is execu ed be o e and dismisses many candida es al eady.
V. COMPUTATIONAL ANALYSIS
We analyze he compu a ional e o o Algs. 2 and 3 wi h
wo examples and compa e hem o he o iginal app oach om
[1] (Alg. 1).
Example 1. Conside he sys em [20, Example 1]
x(k+ 1) = 2 1
−1 2x(k) + I2u(k),
wi h inpu and s a e cons ain s |ui(k)| ≤ 1,i= 1,2, and
|xi(k)| ≤ 1,i= 1,2, espec i ely, weigh ing ma ices Q=I2,
R= 5,000 ·I2, and p edic ion ho izon N= 3. The e minal
weigh ing ma ix Pand se Ta e as desc ibed in Sec . II.
TABLE I: Compu a ional da a o Example 1
Algo i hm 1 Algo i hm 2 Algo i hm 3
# sol ed LPs 11,969 3,059 3,043
# es p uning 47,545 11,887 47,647
# es descendan 0 83,202 13,755
compu ing ime 77.8s26.0s23.6s
TABLE II: Compu a ional da a o Example 2
Algo i hm 1 Algo i hm 2 Algo i hm 3
# sol ed LPs 111,681 14,197 14,149
# es p uning 3,264,401 408,051 3,265,129
# es descendan 0 6,120,750 266,252
compu ing ime 1,001 s706 s478 s
Example 1 has ou pai s (Θi,Ωi)∈ G,i= 1, ..., 4, ha
sa is y (5). The pai s co espond o o a ions o he inpu - and
s a e-space by ϕ1= 0◦,ϕ2= 90◦,ϕ3= 180◦, and ϕ4= 270◦
wi h
(Θi,Ωi) = cos(ϕi)−sin(ϕi)
sin(ϕi) cos(ϕi),
cos(ϕi)−sin(ϕi)
sin(ϕi) cos(ϕi).
(9)
All algo i hms p ocess |PNm(Q)|= 499,178 candida es and
de e mine he solu ion wi h |M| = 73 elemen s. Rank es s
a e execu ed o each o he candida es by all algo i hms.
The emaining compu ing ope a ions o he algo i hms can
be summa ized o be he numbe o sol ed LPs o es o
op imali y wi h (4) and easibili y wi h (4) wi hou (4b) and
(4c), he numbe o es s o es i a candida e is a supe se o
a de ec ed in easible ac i e se ( es p uning) and he numbe
o es s o es i a candida e is a descendan o a de ec ed
non-p ima y ac i e se ( es descendan ). These numbe s di e
wi h he di e en p ocedu es o he algo i hms and a e lis ed
in Tab. I oge he wi h he compu ing imes.
We in oduce a second example wi h mo e symme ies.
Example 2. Conside he sys em
x(k+ 1) = 1 1
−1 1x(k) + I2u(k),
wi h weigh ing ma ices Q, R =I2and p edic ion ho izon
N= 3, and whe e he cons ain se s o inpu s and s a es a e
oc agons wi h spans 20 and 2, espec i ely, ha a e cen e ed
a he o igin. The e minal weigh ing ma ix Pand se Ta e
as desc ibed in Sec . II.
Example 2 has eigh pai s (Θi,Ωi)∈ G,i= 1, ..., 8, ha
sa is y (5). The pai s co espond o o a ions o he inpu - and
s a e-space by ϕ1= 0◦,ϕ2= 45◦,ϕ3= 90◦,ϕ4= 135◦,
ϕ5= 180◦,ϕ6= 225◦,ϕ7= 270◦, and ϕ8= 315◦wi h (9).
All algo i hms p ocess |PNm(Q)|= 36,684,859 candida es
o Example 2 and de e mine he solu ion wi h |M| = 97
elemen s. O he compu a ional da a is lis ed in Tab. II.
I is e iden om he da a in Tabs. I and II ha Algs. 2
and 3 equi e less compu ing ime han Alg. 1. The educ ion
52

mainly esul s because ewe LPs a e sol ed o Algs. 2
and 3 han o Alg. 1 and sol ing he LPs occupies a la ge
sha e o he compu ing ime. All algo i hms gene ally dismiss
candida es Asuch ha ma ix GAis ow ank de icien
and ha a e supe se s o de ec ed in easible ac i e se s om
sol ing an LP. Algo i hms 2 and 3 addi ionally do no sol e
LPs o non-p ima y candida es such ha all bu one ac i e
se ou o each o bi a e dismissed om sol ing an LP.
The numbe o elemen s o an o bi depends on he numbe
o symme ies o he p oblem. Conside ing an OCP wi h g
symme ies, each o bi con ains up o gelemen s, see (7),
so he numbe o sol ed LPs o Algs. 2 and 3 dec eases o
abou 1/g compa ed o Alg. 1. Howe e , Algs. 2 and 3 equi e
addi ional compu a ional e o o execu ing es s descendan .
This e o diminishes he educ ion o compu a ional ime, so
he educ ion in he compu ing imes o Algs. 2 and 3 when
compa ed o Alg. 1 is smalle han he educ ion in he numbe
o sol ed LPs. We will ocus on ha in he nex pa ag aph.
Fu he mo e, he da a in Tabs. I and II e eal ha Alg. 3
equi es less compu ing ime han Alg. 2, o he highly
symme ic Example 2 in pa icula . The di e ences esul
om he di e en numbe s o execu ed es s p uning and es s
descendan . In Alg. 2, es s descendan a e execu ed o all
candida es Asuch ha ma ix GAhas ull ow ank (line 4)
and o all elemen s o he o bi s o ac i e se s ha sa is y
he ank c i e ion and ha a e p ima y (line 17). In Alg. 3,
in con as , es s descendan a e execu ed o all candida es
ha sa is y he ank c i e ion and ha a e no supe se s o
de ec ed in easible ac i e se s (line 5) and o all elemen s
o he o bi s o ac i e se s ha sa is y he ank c i e ion and
ha a e p ima y and easible (lines 14, 20). I ollows ha
Alg. 3 execu es ewe es s descendan han Alg. 2 since he
c i e ia o he candida es being es ed a e mo e es ic i e.
Fu he mo e, execu ing a es descendan in Alg. 3 equi es
less compu a ional e o han in Alg. 2 because Ncon ains
only easible ac i e se s and he e o e ewe elemen s. In
Alg. 2 es s p uning a e execu ed o all candida es Asuch ha
ma ix GAhas ull ow ank and ha a e non-p ima y (line 5)
while Alg. 3 execu es es p uning o all candida es ha sa is y
he ank c i e ion (line 4) and o all elemen s o he o bi s o
ac i e se s ha sa is y he ank c i e ion, ha a e no dismissed
by es p uning, and ha a e p ima y and in easible (line 24).
As a esul , he numbe s o es s p uning o Alg. 2 a e almos
dec eased by ac o gcompa ed o Alg. 3. In summa y, Alg. 3
esul s in ewe es s descendan han Alg. 2 bu mo e es s
p uning. The mo e symme ies a p oblem has, he mo e he
a io be ween compu a ional sa ings and expendi u es shi s
owa ds sa ings o Alg. 3 making Alg. 3 he mo e e ec i e
app oach.
VI. CONCLUSION
We applied he me hods om [17] o imp o ing com-
bina o ial app oaches o symme ic OCPs o he app oach
om [1]. The imp o ed app oach equi es ewe LPs o be
sol ed esul ing in a lowe compu a ional e o . The numbe
o sol ed LPs d ops by a ac o o g, he numbe o symme-
ies o he OCP. Howe e , he app oach equi es addi ional
compu ing ope a ions which coun e ac he educ ion o he
compu a ional e o . These ope a ions occu equen ly o
OCPs wi h many symme ies. Fo his eason, we p esen ed a
second app oach ha makes p uning mo e e ec i e by aking
symme ic easibili y p ope ies in o accoun . This esul s in
ewe equi ed addi ional compu ing ope a ions. Fo OCPs
wi h many symme ies, he second app oach showed o be
he app oach ha equi es less compu a ional e o .
REFERENCES
[1] A. Gup a, S. Bha iya, and P. Na a aj, “A no el app oach o mul ipa a-
me ic quad a ic p og amming,” Au oma ica, ol. 47, pp. 2112–2117,
2011.
[2] A. Bempo ad, M. Mo a i, V. Dua, and E. N. Pis ikopoulos, “The explici
linea quad a ic egula o o cons ained sys ems,” Au oma ica, ol. 38,
pp. 3–20, 2002.
[3] M. M. Se on, G. C. Goodwin, and J. A. De Don´a, “Cha ac e isa ion o
eceding ho izon con ol o cons ained linea sys ems,” Asian Jou nal
o Con ol, ol. 5, pp. 271–286, 2003.
[4] P. Tøndel, T. A. Johanson, and A. Bempo ad, “An algo i hm o
mul i-pa ame ic quad a ic p og amming and explici MPC solu ions,”
Au oma ica, ol. 39, pp. 489–497, 2003.
[5] M. Bao i´c, “An e icien algo i hm o mul i-pa ame ic quad a ic p o-
g amming,” ETH Z¨u ich, Tech. Rep., 2002, AUT02-05.
[6] M. He ceg, M. K asnica, C. N. Jones, and M. Mo a i, “Mul i-
Pa ame ic Toolbox 3.0,” in P oc. o he Eu opean Con ol Con-
e ence, Z¨u ich, Swi ze land, July 17–19 2013, pp. 502–510,
h p://con ol.ee.e hz.ch/∼mp .
[7] A. Bempo ad, “Hyb id Toolbox - Use ’s Guide,” 2004,
h p://cse.lab.im lucca.i /∼bempo ad/hyb id/ oolbox.
[8] M. He ceg, C. N. Jones, M. K asnica, and M. Mo a i, “Enume a ion-
based app oach o sol ing pa ame ic linea complemen a i y p oblems,”
Au oma ica, ol. 62, pp. 243–248, 2015.
[9] R. Obe dieck, N. A. Diangelakis, and E. N. Pis ikopoulos, “Explici
model p edic i e con ol: A connec ed-g aph app oach,” Au oma ica,
ol. 76, pp. 103–112, 2017.
[10] P. Ahmadi-Moshkenani, T. A. Johansen, and S. Ola u, “Combina o ial
app oach owa d mul ipa ame ic quad a ic p og amming based on cha -
ac e izing adjacen c i ical egions,” IEEE T ansac ions on Au oma ic
Con ol, ol. 63, no. 10, pp. 3221–3231, Oc 2018.
[11] M. M¨onnigmann, “On he s uc u e o he se o ac i e se s in cons ained
linea quad a ic egula ion,” Au oma ica, ol. 106, pp. 61–69, 2019.
[12] R. Mi ze and M. M¨onnigmann, “Imp o ed ac i e se dynamic p og am-
ming o sol ing linea -quad a ic op imal con ol p oblems,” in 2022
IEEE 61s Con e ence on Decision and Con ol (CDC), 2022, pp. 1764–
1769.
[13] C. R. Danielson and F. Bo elli, “Symme ic Linea Model P edic i e
Con ol,” IEEE T ansac ions on Au oma ic Con ol, ol. 60, no. 5, pp.
1244–1259, 2015.
[14] C. Felle , T. A. Johanson, and S. Ola u, “An imp o ed algo i hm o
combina o ial mul i-pa ame ic quad a ic p og amming,” Au oma ica,
ol. 49, pp. 1370–1376, 2013.
[15] R. Mi ze and M. M¨onnigmann, “A dynamic p og amming app oach o
sol ing cons ained linea -quad a ic op imal con ol p oblems,” Au o-
ma ica, ol. 120, p. 109132, 2020b.
[16] R. Mi ze and M. M¨onnigmann, “Dynamic p og amming o explici
linea MPC wi h poin -symme ic cons ain s,” in 21s IFAC Wo ld
Cong ess, Be lin, 2020a, pp. 6999–7004.
[17] R. Mi ze, M. K asnica, and M. M¨onnigmann, “Exploi ing symme ies in
ac i e se enume a ion o cons ained linea -quad a ic op imal con ol,”
Au oma ica, ol. 151, p. 110900, 2023.
[18] R. Rymon, “Sea ch h ough sys ema ic se enume a ion,” in P inciples
o Knowledge Rep esen a ion and Reasoning: P oceedings o he Thi d
In e na ional Con e ence (KR’92), 1992, pp. 539–550.
[19] C. R. Danielson and F. Bo elli, “Iden i ica ion o he symme ies o
linea sys ems wi h poly opic cons ain s,” in P oc. o he Ame ican
Con ol Con e ence, 2014, pp. 4218–4223.
[20] C. R. Danielson and F. Bo elli, “Symme ic explici model p edic i e
con ol,” IFAC P oceedings Volumes, ol. 45, no. 17, pp. 132–137, 2012.
53