Teiche , Ka in; Seidel, Tobias; Süss, Philipp
A icle — Published Ve sion
Combining disc e e and con inuous in o ma ion o mul i-
c i e ia op imiza ion p oblems
Ma hema ical Me hods o Ope a ions Resea ch
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Teiche , Ka in; Seidel, Tobias; Süss, Philipp (2024) : Combining disc e e and
con inuous in o ma ion o mul i-c i e ia op imiza ion p oblems, Ma hema ical Me hods o
Ope a ions Resea ch, ISSN 1432-5217, Sp inge , Be lin, Heidelbe g, Vol. 100, Iss. 1, pp. 153-173,
h ps://doi.o g/10.1007/s00186-024-00849-0
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/314961
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Ma hema ical Me hods o Ope a ions Resea ch (2024) 100:153–173
h ps://doi.o g/10.1007/s00186-024-00849-0
ORIGINAL ARTICLE
Combining disc e e and con inuous in o ma ion o
mul i-c i e ia op imiza ion p oblems
Ka in Teiche 1·Tobias Seidel1·Philipp Süss1
Recei ed: 11 Ap il 2023 / Re ised: 4 Janua y 2024 / Accep ed: 4 Janua y 2024 /
Published online: 23 Feb ua y 2024
© The Au ho (s) 2024
Abs ac
In mul i-c i e ia op imiza ion p oblems ha o igina e om eal-wo ld decision mak-
ing asks, we o en ind he ollowing s uc u e: The e is an unde lying con inuous,
possibly e en con ex model o he mul iple ou come measu es depending on he
design a iables, bu hese ou comes a e addi ionally assigned o disc e e ca ego ies
acco ding o hei desi abili y o he decision make . Mul i-c i e ia delibe a ions may
hen ake place a he le el o hese disc e e labels, while he calcula ion o a speci ic
design emains a con inuous p oblem. In his wo k, we analyze his ype o p oblem
and p o ide heo e ical esul s abou i s solu ion se . We p o e ha he disc e e deci-
sion p oblem can be ackled by sol ing scala iza ions o he unde lying con inuous
model. Based on ou analysis we p opose mul iple algo i hmic app oaches ha a e
speci ically sui ed o handle hese p oblems. We compa e he algo i hms based on a
se o es p oblems. Fu he mo e, we apply ou me hods o a eal-wo ld adio he apy
planning example.
Keywo ds Mul i-c i e ia op imiza ion ·Decision making ·Non-linea op imiza ion ·
Pa e o on app oxima ion
1 In oduc ion
In many p ac ical applica ions, he decision make ’s u ili y unc ion is o a s ep-wise
na u e e en hough he unde lying measu e and i s dependence on he eal- alued
op imiza ion a iables is con inuous. Fo example, in adio he apy one ies o ha e a
su icien ly high dose in he a ge and hen, p o ided his is he case, as li le dose in
su ounding o gans a isk as possible. While he dose alues in hose nea by o gans
a e con inuously dependen on adminis e ed adia ion, om a physician’s poin o
BKa in Teiche
[email p o ec ed].de
1F aunho e Ins i u e o Indus ial Ma hema ics (ITWM), F aunho e pla z 1, 67663 Kaise slau e n,
Ge many
123
154 K. Teiche e al.
iew hey a e judged on whe he hey exceed ce ain h eshold alues associa ed wi h
pa icula side e ec s. The eby, a dose in an o gan migh be labeled as ei he “dange -
ously high”, “accep able”, o “ideal”. The mul i-c i e ia decision making would hen
delibe a e on he ade-o s be ween di e en o gans based on hese b oad ca ego iza-
ions.
We o malize his obse a ion by de ining he ollowing ype o mul i-c i e ia op i-
miza ion p oblem:
P:min
x∈Md1( 1(x)),...,dk( k(x)) (1)
whe e we assume M⊆Rn o be compac and non-emp y, 1,..., k:M→R
o be con inuous unc ions, and d1,...,dk:R→R o be mono one inc easing.
We le := ( 1,..., k)and d:= (d1◦π1,...,dk◦πk), whe e πideno es he
p ojec ion om a ec o in Rk o he i- h componen . We assume ha he e is no a
p io i p e e ence be ween he objec i es.
To es ablish he disc e e na u e o ou p oblem, we equi e he ollowing assump ion
o he mono one inc easing u ili y unc ions di:
Assump ion 1.1 (Disc e e u ili y) Fo i∈{1,...,k} he e is a ini e se i⊂Rsuch
ha di:R→i.
In he li e a u e, he e is a as amoun o gene al-pu pose app oaches ha can be
applied o mul i-c i e ia p oblems wi h disc e e and con inuous decision a iables and
objec i es alike (S eue and Choo 1983; Benson and Sayin 1997; Das and Dennis
1998; Schandl e al. 2002). While hese a e applicable o P, hey do no ake in o
accoun i s special s uc u e. An e icien algo i hm o Pshould ideally combine
ce ain cha ac e is ics o algo i hms in ended speci ically o con inuous p oblems
wi h hose speci ic o disc e e p oblems.
When acing a p oblem wi h he s uc u e o P, he aim is o ind he non-domina ed
solu ions wi h espec o he disc e e u ili y unc ion e alua ions di. Howe e , we also
ha e an unde lying con inuous p oblem ha we can po en ially capi alize on:
Pc:min
x∈M 1(x),..., k(x). (2)
Simila o how non-domina ed solu ions a e ob ained in he pu ely con inuous
se ing, e icien solu ions o (2) can be calcula ed wi h po en ially e y e icien
gene al-pu pose con inuous sol e s, such as IPOPT (Wäch e and Biegle 2006)o kni-
o (By d e al. 2006). Sui able scala iza ion me hods a e weigh ed sum i he p oblem
is con ex, and -cons ain (see e.g. Eh go 2005), o Pascole i–Se a ini scala iza ion
(Pascole i and Se a ini 1984) in he case o non-con ex p oblems. Pa icula ly sui ed
app oaches o app oxima ing he Pa e o on o a con inuous p oblem a e sandwich-
ing (Se na 2012; Bok an z and Fo sg en 2012) in case he p oblem is con ex, and
hype olume o hype boxing algo i hms (B ingmann and F ied ich 2010; Teiche
2014) i he p oblem is non-con ex.
Howe e , algo i hms o con inuous p oblems a e app oxima ion algo i hms: hey
aim a calcula ing a disc e e se o non-domina ed solu ions ha ep esen he Pa e o
123
Combining disc e e and con inuous in o ma ion o … 155
on up o some app oxima ion e o measu e, o en by es ablishing lowe and/o
uppe bounds on he on (Sayın 2000; Klam o h e al. 2002; Eich elde 2009). In
con as , o ou se ing we do no aim a an app oxima ion o he Pa e o on , bu
a ull ep esen a ion. Tha is, we wan o ind a leas one e icien solu ion o each
non-domina ed poin in he image space o he disc e e u ili y unc ions. In his ega d,
ou app oach is in line wi h many algo i hmic app oaches o calcula ing he Pa e o
on o a pu ely disc e e p oblem (Ulungu and Teghem 1994; Holzmann and Smi h
2018).
While i is in ac possible o sol e he mul i-c i e ia p oblem Panalogously o
a pu ely disc e e p oblem wi h hose echniques, such an app oach is unnecessa ily
compu a ionally expensi e, as he mo e di icul disc e e p oblem is sol ed epea edly
and no he po en ially simple con inuous p oblem. On he o he hand, one could
sol e he con inuous p oblem Pcin he app oxima i e sense and, in a second s ep,
in e he disc e e on . Bu hen many poin s on he con inuous Pa e o on may be
calcula ed ha a e edundan o he disc e e Pa e o on o P. This is why in his
pape we aim o combine bo h wo lds. We will p esen algo i hms ha a oid sol ing he
disc e e p oblem and a he sol e he simple con inuous p oblem Pc. Simul aneously,
he algo i hms will inco po a e he disc e e aspec s o P o a oid sol ing edundan
con inuous p oblems.
The ou line o his pape is as ollows. We i s in es iga e he ela ionship be ween
he solu ions o Pand Pc(Sec .2). Based on his heo e ical insigh , we hen p o-
pose di e en algo i hms o ind all non-domina ed poin s o P(Sec .3). Finally, we
demons a e and e alua e hese algo i hms using a se o es p oblems and an example
om adio he apy (Sec .4). We conclude wi h a discussion o ou esul s (Sec .5).
2 Theo e ical esul s
In his sec ion, we in es iga e he heo e ical p ope ies o P(1). In pa icula , we
desc ibe he ela ionship be ween peculia solu ions o Pand hei co esponding
coun e pa s wi h espec o he unde lying con inuous p oblem Pc(2). This is c ucial
o he de elopmen and he analysis o he algo i hms desc ibed la e in his pape .
No e ha o all obse a ions wi hin his sec ion, Assump ion 1.1 is no equi ed; hey
hold o a bi a y mono one unc ions.
Be o e we p esen he heo e ical esul s, we summa ize some no a ion used
h oughou his pape . Fo wo ec o s y1,y2∈Rkwe w i e y1y2i he inequali y
y1
i≤y2
iholds o e e y componen i=1,...k(analogously o ,<,>). We say
ha a poin y∈Rkdomina es a poin y∈Rki :
yi≤y
i o all i∈{1,...,k}
yi<y
i o a leas one i∈{1,...,k}.
We say ha a poin y∈Rks ic ly domina es a poin y∈Rki o all i∈{1,...,k}
he inequali y yi<y
iholds. The image o he combined MCO p oblem Pis deno ed
by
123
156 K. Teiche e al.
Y:= (d◦ )(M). (3)
Fo he he unde lying con inuous p oblem Pc he image is deno ed by
Yc:= (M). (4)
A poin x∈Mis called e icien solu ion o P( o Pc)i he eisnoy∈Y(y∈Yc)
such ha ydomina es (d◦ )(x)(domina es (x)). The co esponding image poin
is called non-domina ed. A poin x∈Mis called weakly e icien solu ion o P( o
Pc)i he eisnoy∈Y(y∈Yc)such ha ys ic ly domina es (d◦ )(x)(s ic ly
domina es (x)). The co esponding image poin is called weakly non-domina ed.
We can now begin o in oduce s a emen s abou he ela ionship be ween pa icula
solu ions o Pand Pc. We i s obse e he connec ion be ween weakly non-domina ed
poin s o he wo p oblems.
Lemma 2.1 I yc,∗∈Ycis a weakly non-domina ed poin o Pc hen y∗:= d(yc,∗)∈
Yis weakly non-domina ed o P.
P oo Fo an a bi a y poin yin he image Yo P he e is a leas one poin yc∈Yc
such ha y=d(yc). Now conside he weakly non-domina ed poin yc,∗∈Yc. The e
mus be a leas one index i∈{1,...,k}such ha
yc,∗
i≤yc
i,
as o he wise ycwould s ic ly domina e yc,∗and yc,∗could no be a weakly non-
domina ed poin . Fo he same index ii ollows by mono onici y o di ha
y∗
i=di(yc,∗
i)≤di(yc
i)=yi.
This shows ha ydoes no s ic ly domina e y∗.As ywas chosen a bi a y in Y, his
shows ha also y∗is a weakly non-domina ed poin .
Lemma 2.1 also implies ha a non-domina ed poin is mapped o a weakly non-
domina ed poin . Un o una ely his poin is no necessa ily non-domina ed anymo e,
as he ollowing example shows:
Example 2.2 Conside he ollowing example (illus a ed in Fig.1):
•M={x∈R2|x2≤1}
•k=2, 1(x)=x1, 2(x)=x2
• o ∈R:d1( )=d2( )and
d1( )=1i ≤−0.5,
2i >−0.5.
The poin (−1,0)is a non-domina ed poin o p oblem Pc. Howe e , by di is
mapped o he poin (1,2). This poin is domina ed by (1,1), which is he image o
he easible solu ion (−0.5,−0.5)unde d◦ .
123
Combining disc e e and con inuous in o ma ion o … 157
Fig. 1 Illus a ion o Example
2.2. The image se Yco he
inne p oblem Pcis depic ed in
g ay and i s Pa e o on in blue.
The non-domina ed poin
(−1,0), depic ed in ed, is
mapped by d o he weakly
non-domina ed poin (1,2).This
poin is domina ed by (1,1)
The example also shows ha he e e se ela ionship does no hold. I d(yc)
is a weakly non-domina ed poin , hen he p eimage can be s ic ly domina ed.
The poin (−0.5,−0.5)is domina ed in Pcby he poin (−√2
2,−√2
2). Howe e ,
d((−0.5,−0.5)) is a non-domina ed poin . This means ha no all p eimages o a
non-domina ed poin a e again (weakly) non-domina ed. The ollowing can be shown
abou he exis ence o non-domina ed poin s in he p eimage:
Lemma 2.3 Le y∗∈Ybe a non-domina ed poin o P. Then he e exis s a non-
domina ed poin yc,∗∈Yco Pcsuch ha
y∗=d(yc,∗).
P oo Le
Z=d−1(y∗)∩Yc
deno e he p eimage o he non-domina ed poin y∗∈Ygi en in he s a emen . By
assump ion his se is nonemp y. We wan o show ha we can ind a poin in Z ha is
non-domina ed o Pc. Fi s conside any poin z∈Zand a poin z∈Ycsuch ha :
z
i≤zi o all i∈{1,...,k}.(5)
Then by mono onici y o diwe ha e:
di(z
i)≤di(zi)=y∗
i o all i∈{1,...,k}
As y∗is non-domina ed, we mus ha e:
d(z)=y∗.
123
158 K. Teiche e al.
This means ha e e y poin z∈Ycsa is ying he inequali ies in Eq. (5) is al eady
con ained in Z.
As we did no assume any con inui y p ope ies o d, hese Zis no necessa ily
closed. This is why we conside he closu e o his se deno ed by Z. As we assumed
ha is con inuous and Mis compac , he se Zis as a subse o Yc= (M)compac .
Now ix an a bi a y poin z∗∈Zand conside he ollowing op imiza ion p oblem:
min
z∈Z
k
i=1
zi
s. . zi≤z∗
i o all i∈{1,...,k}
The easible se is compac and non-emp y by cons uc ion. Mo eo e e e y easible
poin o his p oblem is by he a gumen s gi en abo e in Z. This means ha also an
op imal solu ion yc,∗∈Yc o his p oblem is again in Z, which hen means ha
d(yc,∗)=d(y∗).
I emains o a gue ha yc,∗is ins ead a non-domina ed poin o Pc. Because o
op imali y, yc,∗canno be domina ed by any poin in Z. Mo eo e , e e y poin in
Yc ha would domina e zalso sa is ies (5) and is again in Z. Toge he his means
ha he cons uc ed poin canno be domina ed by any poin in Ycand is indeed a
non-domina ed poin o p oblem Pc.
This Lemma is c ucial o an algo i hmic app oach. I shows ha we can ind he Pa e o
on o he pe haps mo e complex p oblem Pby calcula ing poin s o he Pa e o on
o he con inuous p oblem Pc. Fo comple eness we show in he nex example ha he
s a emen o Lemma 2.3 does no hold ue, i one eplaces non-domina ed by weakly
non-domina ed.
Example 2.4 Conside he same easible se and he same objec i es as in Example 2.2
bu conside he ollowing u ili y unc ion:
• o ∈R:d1( )=d2( )and
d1( )=1i ≤0.5,
2i >0.5.
Fo an illus a ion, see Fig.2. In his example, he poin (2,1)is a weakly non-
domina ed poin o P. Howe e , all poin s in Yc ha a e mapped o his poin a e
s ic ly domina ed in Pc,e.g.by(−1,0).
3 Algo i hms
In his sec ion, we discuss di e en algo i hms ailo ed a calcula ing he Pa e o on
o a p oblem Pwi h disc e e u ili y mappings. Tha is, o he algo i hms p esen ed
123
Combining disc e e and con inuous in o ma ion o … 159
Fig. 2 Illus a ion o Example
2.4. The image se Yco he
inne p oblem Pcis depic ed in
g ay and i s Pa e o on in blue.
E e y poin in he da k a ea is
s ic ly domina ed in he inne
p oblem Pc, bu i is he
p eimage o a weakly
non-domina ed poin (1,2) o P
Fig. 3 Illus a ion o exhaus i ely sol ing he mul i-c i e ia p oblem P. The p eimages o he poin s y∈
k
i=1idi ide he image space o he con inuous p oblem Pcin o boxes. By inding speci ic solu ions o
he inne p oblem—which map o poin s on he con inuous Pa e o on depic ed in blue—we can de e mine
whe he each box, and hus each y∈k
i=1i, is non-domina ed, domina ed, o una ainable
in his sec ion o be applicable, we om now on explici ly equi e ha Assump ion
1.1 is sa is ied. This means ha o he image o Pwe ha e:
Y⊆
k
i=1
i.
The p oposed algo i hms u ilize he special s uc u e o P. On he one hand, all
p oposed me hods employ a g adien -based sol e o ind ei he easible o weakly
e icien solu ions xo Pby i e a i ely sol ing pa icula single-c i e ia op imiza ion
p oblems—so-called scala iza ions—de i ed om he con inuous inne p oblem Pc.
On he o he hand, he algo i hms also ake he disc e e u ili y mappings in o accoun ,
namely when choosing which scala iza ion o sol e nex and when e alua ing hei
p og ess.
123
160 K. Teiche e al.
The p oposed algo i hms aim o exhaus i ely sol e he mul i-c i e ia p oblem P
(see Fig.3). This means ha :
•Fo all y∈k
i=1i, he algo i hm de e mines whe he yis non-domina ed,
domina ed o una ainable.
•Fo any y∈k
i=1i ha is non-domina ed, he algo i hm calcula es a solu ion
x∈Msuch ha y=(d◦ )(x).
In he applica ions we will in oduce in Sec .4 he ca dinali y o each indi idual i
will no only be ini e bu also small (3–5). Addi ionally we will no ha e a bi a y
many objec i es in mind (in he examples 2–4). This means ha i is possible o i e a e
o e all elemen s in k
i=1iand o sa e in o ma ion o each elemen . Howe e , ou
goal is o keep he compu a ional e o – in he sense o op imiza ion p oblems o
sol e o e all elemen s – small.
Du ing applica ion o he ollowing algo i hms a poin y∈k
i=1ican ha e ou
di e en cu en s a es encoded by σ(y):
•σ(y)=a ainable: The algo i hm ound an xwi h
(d◦ )(x)y.
In his case we sa e xin X∗(y).
•σ(y)=domina ed: The algo i hm de e mined a poin ˜
y∈Y ha is a ainable and
ha domina es y.
•σ(y)=una ainable: The algo i hm checked ha he e is no poin x ha is mapped
o yo any poin ha domina es y.
•σ(y)=unknown: The algo i hm did no make any s a emen abou his poin , ye .
No e ha we do no need o explici ly encode all poin s ha a e a ainable bu non-
domina ed. I we ound co ec ly all poin s ha a e a ainable and o hese poin s all ha
a e domina ed, hen he complemen o he domina ed poin s a e he non-domina ed
ones. We can also be su e o ha e calcula ed a p eimage x o each non-domina ed y.
As o each a ainable poin ywe ound an xwi h:
(d◦ )(x)y.
Fo a non-domina ed poin none o hese inequali ies can be s ic and we mus ha e:
(d◦ )(x)=y.
In he ollowing, we call a poin ya suppo ed poin o Pcwi h weigh s w(see e.g.
Eh go 2005) i i sol es he ollowing op imiza ion p oblem:
min
y∈Yc
k
i=1
wi·yi.
123
Combining disc e e and con inuous in o ma ion o … 167
Fig. 6 The box checking algo i hm, using he Pascole i-Se a ini scala iza ion, o a p oblem ins ance o 8
wi h k=2andK=4. In o al, six i e a ions a e necessa y o exhaus i ely sol e he p oblem
d4
i(xi)=⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
0.4i 0≤xi≤0.4,
0.6i 0.4<xi≤0.6,
0.8i 0.6<xi≤0.8,
1.0i xi>0.8
∀i=1, .., k
d5
i(xi)=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎩
0.4i 0≤xi≤0.4,
0.5i 0.4<xi≤0.5,
0.6i 0.5<xi≤0.6,
0.8i 0.6<xi≤0.8,
1.0i xi>0.8
∀i=1, .., k.
The unde lying con inuous p oblem Pco he andomized p oblems (8) is con ex,
allowing he applica ion o all algo i hms (A), (B) and (C). Fo a speci ic p oblem
ins ance wi h k=2 and K=4, Fig.6illus a es he cou se o he box checking
algo i hm (A), and Fig.7depic s he cou se when using he combined algo i hm o
con ex p oblems (C) ins ead. We see ha o his ins ance, he combined algo i hm
o con ex p oblems ou pe o ms he box checking algo i hm, inishing in 3 a he
han 6 i e a ions.
We can compa e he pe o mance o algo i hms (A)–(C) by measu ing he p og ess
po e he i e a ions, wi h pbeing de ined as:
123
168 K. Teiche e al.
Fig. 7 The con ex algo i hm applied o a p oblem ins ance o Eq.8wi h k=2andK=4. Only h ee
i e a ions a e necessa y o de e mine all non-domina ed poin s. No e ha he solu ion o one o he non-
domina ed ou comes is ob ained by con ex combina ion o p e iously calcula ed poin s acco ding o Lemma
3.3 (o ange)
p=1−|{y∈k
i=1i|σ(y)unknown}|
|k
i=1i|.(9)
Figu e8shows he a e aged p og ess o he a i icial p oblem 8o e a ying
numbe o objec i es k∈{2,3,4}and image se ca dinali ies K∈{3,4,5}. To c ea e
each o he a e aged plo s, 10 andomly c ea ed p oblem ins ances we e sol ed and
he mean o ob ained p og ess alues pa e each i e a ion was calcula ed.
The combined con ex algo i hm (C) pe o ms bes by exploi ing he con exi y o
he p oblem. The nex bes choice is he combined algo i hm ha uses he suppo ed
solu ions algo i hm as a i s phase. The box checking algo i hm on i s own does no
pe o m as well. Wi h highe dimension kand highe image se ca dinali y K, he
di e ences in algo i hm pe o mance become mo e p onounced.
4.2 Radio he apy planning example
In adio he apy planning, he aim is o deli e he p esc ibed dose o he a ge olumes
while spa ing nea by o gans a isk. In in ensi y-modula ed adia ion he apy (IMRT),
he i adia ion— he so-called luence—is deli e ed om di e en angles a ound he
pa ien and can addi ionally be modula ed o e he c oss sec ion o each beam by
mo ing collima o lea es in and ou o he beam ield.
The luence is ep esen ed by a ec o x0 and cons i u es he op imiza ion
a iable o he mul i-c i e ia adio he apy planning p oblem (Kü e e al. 2002; Kü e
e al. 2003; C a e al. 2012). The dose in luence ma ix D depends on he pa ien
ana omy as es ablished by a CT scan and p omo es he mapping om he luence o
he dose, such ha he en ies o Dx ep esen he dose o each oxel in he oxelized
pa ien ana omy.
The op imiza ion objec i es hen e alua e he dose ec o en ies o e he a ge
olumes and o gans a isk. These e alua ion unc ions a e con inuous and o en con-
ex. Possible choices a e minimum, maximum, mean, p-no ms o one-sided p-no ms.
123
Combining disc e e and con inuous in o ma ion o … 169
Fig. 8 A e aged p og ess o algo i hms (A)–(C): box checking algo i hm (da k blue), combined algo i hm
wi h suppo ed solu ions algo i hm as i s phase (pu ple do ed) and combined algo i hm wi h con ex
algo i hm as i s phase ( ed). The a e ages we e aken o e 10 andomized p oblem ins ances o 8.The
numbe o objec i es kwas a ied om 2 o 4 and he image se ca dinali y Kwas a ied om 3 o 5
Thus, he (con inuous) mul i-c i e ia adio he apy planning p oblem has he p ope ies
equi ed o he inne p oblem Pcin ou se ing.
In clinical p ac ice, ce ain h eshold alues o he objec i es play a c ucial ole.
In he case o o gans a isk, iola ing a h eshold is linked o speci ic side e ec s.
Fo he a ge s, ailing o mee a speci ic alue may inc ease he p obabili y o he
umo ecu ing. O en, hese clinical goals a e u he ca ego ized in o hose which
ep esen he absolu e minimum equi emen , and o he s ha co espond o an a e age
o an ideal dose dis ibu ion in he olume. Taking hese disc e iza ions (“minimum”,
“a e age”, “ideal”) in o accoun , we ob ain he s uc u e o he con inuous p oblem
wi h disc e ized u ili y P.
As an example, we conside he TG119 case. The ana omy o he case has a U-
shaped a ge olume, an o gan a isk (OAR) in he cen e o he a ge , and he
su ounding no mal issue egion. We de ine he beam geome y as 7 equidis an ly
spaces beams, see Fig. 9.
To se up he op imiza ion p oblem, we o mula e one objec i e o each s uc u e
as de ailed in Table 1. Addi ionally, o each objec i e we de ine he disc e iza ion
mappings in o he ca ego ies 3 (“minimum”), 2 (“a e age”), and 1 (“ideal”) by ce ain
uppe bounds, also gi en in Table 1, such ha he disc e ized u ili y unc ions di
123
170 K. Teiche e al.
Fig. 9 Geome y o he TG119
case. I has a U-shaped a ge
olume (whi e), an o gan a isk
(magen a) in he cen e o he
a ge , and su ounding no mal
issue. Se en beams a e spaced
equidis an ly (whi e lines)
Table 1 Op imiza ion model o he TG119 case: op imiza ion objec i es o a ge , OAR and issue, and
h eshold alues o he disc e iza ion in o ca ego ies 1–3
Volume Objec i e Ca ego ies: 3 2 1
OAR 1
|OAR| ∈OAR(Dx) 25.0 23.0 20.0
Tissue 1
| issue| ∈OAR(Dx) 8.0 6.0 5.0
Ta ge ∈ a ge max {0,60 −(Dx) }22.0 1.5 1.0
(i=1,2,3)map o he smalles ca ego y o which i(Dx) alls below he ca ego y’s
uppe bound.
Again, we compa ed he algo i hms (A)–(C). Figu e10 shows he esul ob ained
wi h all h ee algo i hms. The e a e wo Pa e o-op imal solu ions o he disc e ized
p oblem: one whe e he a ge and he issue dose quali y a e ideal while he OAR
dose quali y is a e age, and one whe e he OAR and issue dose quali y a e ideal and
he a ge dose quali y is a e age. This is e lec ed in he dose olume his og ams o
he wo solu ions, whe e he i s solu ion shows a be e slope a he p esc ip ion dose
le el o 60 Gy, while he o he solu ion exhibi s a lowe OAR cu e.
Figu e11 shows he p og ess—as de ined in (9)— o he di e en algo i hms o e
he i e a ions. Fo his pa icula example, he algo i hms do no di e much in hei
e iciency. The combined algo i hm ha uses he con ex algo i hm as a i s phase
pe o ms he bes , ollowed by he box checking algo i hm and he o he combined
algo i hm.
5 Conclusion
In his pape we conside ed mul i-c i e ia op imiza ion p oblems which a e based on a
con inuous p oblem. The ou pu s o he objec i es a e mapped using a disc e e u ili y
unc ion making he o e all mul i-c i e ia op imiza ion a disc e e one. Fo example,
such ca ego ies can be used o quickly ind candida e solu ions o a decision make ,
especially when he Pa e o on is no longe easily isualized. In a i s s ep a decision
make migh wan o ge a ough o e iew o he di e en al e na i es ins ead o
na iga ing locally.
123
Combining disc e e and con inuous in o ma ion o … 171
Fig. 10 The esul o he TG119 example. On he le side, he OAR mean objec i e and i s disc e iza ion
in o ca ego ies is plo ed agains he issue mean objec i e and i s disc e iza ion o each o he 3 ca ego ies
o he a ge unde dose objec i e. The e a e wo Pa e o op imal ou comes in he disc e ized space. These
a e achie ed by wo e icien solu ions xmapping o he ma ked poin s unde he con inuous objec i es
de ined in Table 1( he a ge objec i e alue being shown in pu ple.) The dose dis ibu ions o he wo
solu ions—displayed as dose- olume his og ams a he igh — ep esen wo dis inc comp omises, wi h
he uppe solu ion achie ing a be e a ge co e age and he lowe solu ion a be e spa ing o he OAR
Fig. 11 P og ess o algo i hms
(A)–(C) o he TG119
adio he apy planning example:
box checking algo i hm (da k
blue), combined algo i hm wi h
suppo ed solu ions algo i hm as
i s phase (pu ple), and
combined algo i hm wi h con ex
algo i hm as i s phase ( ed)
123
172 K. Teiche e al.
In his pape , we i s s udied he connec ion be ween solu ions o he unde lying
con inuous p oblem and he combined mul i-c i e ia p oblem. The esul s we e used
o in oduce se e al algo i hms ha combine he disc e e and con inuous s uc u e.
In nume ical examples, we we e able o show ha ou app oaches can sa e a lo o
compu a ion compa ed o a nai e app oach. Fo la ge p oblems wi h mo e objec i es
and mo e ca ego ies, he expe imen s showed ha i is bene icial o use as much
in o ma ion as possible and also o exploi con exi y.
Se e al aspec s we e beyond he scope o his pape , bu may be o in e es o u u e
in es iga ions. We ocused on ully disc e e u ili ies. In Sec . 2we al eady poin ed
ou ha his is no necessa ily equi ed om a heo e ical poin o iew. All esul s
hold o mono one unc ions in gene al. I would be in e es ing o look a combined
con inuous and disc e e u ili ies. We also ocused on p oblems wi h a mode a e numbe
o ca ego ies and objec i es. This way i was no a p oblem o i e a e o e all possible
ca ego y combina ions. I would be in e es ing o s udy how he de eloped s a egies
ans e o his la ge se ing.
Funding Open Access unding enabled and o ganized by P ojek DEAL.
Decla a ions
Con lic o in e es The au ho s ha e no compe ing in e es s o decla e ha a e ele an o he con en o
his a icle. No unding was ecei ed o assis wi h he p epa a ion o his manusc ip .
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included
in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I
ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed
by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he
copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
Benson HP, Sayin S (1997) Towa ds inding global ep esen a ions o he e icien se in mul iple objec i e
ma hema ical p og amming. Na Res Logis 44:47–67
Bok an z R, Fo sg en A (2012) An algo i hm o app oxima ing con ex pa e o su aces based on dual
echniques. In o ms J Compu 25(2)
B ingmann K, F ied ich T (2010) Tigh bounds o he app oxima ion a io o he hype olume indica o .
In: Schae e R, Co a C, Kołodziej J, Rudolph G (eds) Pa allel p oblem sol ing om na u e. PPSN
XI, olume 6238 o Lec u e No es in Compu e Science. Sp inge , Be lin, pp 607–616
By d RH, Nocedal J, Wal z RA (2006) Kni o: an in eg a ed package o nonlinea op imiza ion. Sp inge ,
Be lin, pp 35–59
C a DL, Hong TS, Shih HA, Bo eld TR (2012) Imp o ed planning ime and plan quali y h ough
mul ic i e ia op imiza ion o in ensi y-modula ed adio he apy. In J Rad Onc Biol Phys 82(1):e83–
e90
Das I, Dennis J (1998) No mal-bounda y in e sec ion: a new me hod o gene a ing he pa e o su ace in
nonlinea mul ic i e ia op imiza ion p oblems. SIAM J Op im 8:631–657
Eh go M (2005) Mul ic i e ia op imiza ion: wi h 88 igu es and 12 ables, 2nd edn. Sp inge , Be lin
Eich elde Gab iele (2009) Scala iza ions o adap i ely sol ing mul i-objec i e op imiza ion p oblems.
Compu Op im Appl 44:249–273
123
Combining disc e e and con inuous in o ma ion o … 173
Holzmann T, Smi h JC (2018) Sol ing disc e e mul i-objec i e op imiza ion p oblems using modi ied
augmen ed weigh ed chebyche scala iza ions. Eu J Ope Res 271:436–449
Klam o h K, Tind J, Wiecek MM (2002) Unbiased app oxima ion in mul ic i e ia op imiza ion. Ma h
Me hods Ope Res 56(3):413–437
Kü e KH, Hamache H, Hans W (2002) In e se adia ion he apy planning—a mul iple objec i e op i-
miza ion app oach. Disc e e Appl Ma h 118
Kü e K-H, Sche e A, Monz M, Alonso F, T inkaus H, Bo eld T, Thieke C (2003) In ensi y-modula ed
adio he apy—a la ge scale mul i-c i e ia p og amming p oblem. OR Spec um 25:223–249
Pascole i A, Se a ini P (1984) Scala izing ec o op imiza ion p oblems. J Op im Theo y Appl 42(4):499–
524
Sayın Se pil (2000) Measu ing he quali y o disc e e ep esen a ions o e icien se s in mul iple objec i e
ma hema ical p og amming. Ma h P og am 87:543–560
Schandl B, Klam o h K, Wiecek MM (2002) No m-based app oxima ion in mul ic i e ia p og amming.
Compu Ma h Appl 44:925–942
Se na JI (2012) Mul i-objec i e op imiza ion in mixed in ege p oblems wi h applica ion o he beam angle
op imiza ion p oblem in IMRT. Ph.D. hesis, Technical Uni e si y o Kaise slau e n, Depa men o
Ma hema ics
S eue RE, Choo EU (1983) An in e ac i e weigh ed chebyche p ocedu e o mul iple objec i e p og am-
ming. Ma h P og am 26:326–344
Teiche IK (2014) A hype boxing Pa e o app oxima ion me hod applied o adio equency abla ion ea -
men planning. Ph.D. hesis, Technical Uni e si y o Kaise slau e n, Depa men o Ma hema ics
Ulungu EL, Teghem J (1994) Mul i-objec i e combina o ial op imiza ion p oblems: a su ey. Mul i-c i e ia
Decis Anal 3:83–104
Wäch e A, Biegle LT (2006) On he implemen a ion o a p imal-dual in e io poin il e line sea ch
algo i hm o la ge-scale nonlinea p og amming. Ma h P og am 106:25–57
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps
and ins i u ional a ilia ions.
123
