Sass, Susanne; Mi sos, Alexande ; Nikolo , Nikolay I.; Tsoukalas, Angelos
A icle — Published Ve sion
Ou -o -sample es ima ion o a b anch-and-bound
algo i hm wi h g owing da ase s
Jou nal o Global Op imiza ion
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Sass, Susanne; Mi sos, Alexande ; Nikolo , Nikolay I.; Tsoukalas, Angelos (2025) :
Ou -o -sample es ima ion o a b anch-and-bound algo i hm wi h g owing da ase s, Jou nal o
Global Op imiza ion, ISSN 1573-2916, Sp inge US, New Yo k, NY, Vol. 92, Iss. 3, pp. 615-642,
h ps://doi.o g/10.1007/s10898-025-01514-4
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323681
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/
Jou nal o Global Op imiza ion (2025) 92:615–642
h ps://doi.o g/10.1007/s10898-025-01514-4
Ou -o -sample es ima ion o a b anch-and-bound algo i hm
wi h g owing da ase s
Susanne Sass1·Alexande Mi sos1,2,3 ·Nikolay I. Nikolo 4,5 ·
Angelos Tsoukalas6
Recei ed: 10 May 2024 / Accep ed: 12 June 2025 / Published online: 23 June 2025
© The Au ho (s) 2025
Abs ac
In [Sass e al., Eu . J. Ope . Res., 316 (1): 36 – 45, 2024], we p oposed a b anch-and-bound
(B&B) algo i hm wi h g owing da ase s o he de e minis ic global op imiza ion o pa ame e
es ima ion p oblems based on la ge da ase s. The ein, we s a he B&B algo i hm wi h a
educed da ase and augmen i un il eaching he ull da ase upon con e gence. Howe e ,
con e gence may be slowed down by a gap be ween he lowe bounds o he educed and he
o iginal p oblem, in pa icula o noisy measu emen da a. Thus, we p opose he use o ou -
o -sample es ima ion o imp o ing he lowe bounds calcula ed wi h educed da ase s. Based
on his, we ex end he de e minis ic app oach and p opose wo heu is ic app oaches. The
compu a ional pe o mance o all app oaches is compa ed wi h he s anda d B&B algo i hm
as a benchma k based on eal-wo ld es ima ion p oblems om p ocess sys ems enginee ing,
biochemis y, and machine lea ning co e ing da ase s wi h and wi hou measu emen noise.
Ou esul s indica e ha he heu is ic app oaches can imp o e he inal lowe bounds on he
op imal objec i e alue wi hou cu ing o he global solu ion. Aside om his, we p o e ha
esampling can dec ease he a iance o he lowe bounds calcula ed based on andom ini ial
da ase s. In ou case s udy, esampling ha dly a ec s he pe o mance o he app oaches
which indica es ha he B&B algo i hm wi h g owing da ase s does no su e om la ge
a iances.
Keywo ds Nonlinea p og amming ·Spa ial b anch and bound ·Pa ame e es ima ion ·
O e i ing ·Resampling
BAngelos Tsoukalas
[email p o ec ed]
1P ocess Sys ems Enginee ing (AVT.SVT), RWTH Aachen Uni e si y, 52074 Aachen, Ge many
2JARA-CSD, 52056 Aachen, Ge many
3Ins i u e o Clima e and Ene gy Sys ems: Ene gy Sys ems Enginee ing (ICE-1),
Fo schungszen um Jülich GmbH, 52425 Jülich, Ge many
4Ins i u e o S a is ics, RWTH Aachen Uni e si y, 52056 Aachen, Ge many
5Ins i u e o Ma hema ics and In o ma ics, Bulga ian Academy o Sciences, 1113 So ia, Bulga ia
6Depa men o Technology and Ope a ions Managemen , RSM E asmus Uni e si y Ro e dam, 3062 PA
Ro e dam, Ne he lands
123
616 Jou nal o Global Op imiza ion (2025) 92:615–642
1 In oduc ion
The alidi y o pa ame e es ima ion esul s inc eases signi ican ly when a oiding bo h
subop imal solu ions and o e i ing. Subop imal solu ions can be excluded when using de e -
minis ic global op imiza ion (DGO) me hods [1,2]. Common DGO me hods [3,4] like he
b anch-and-bound (B&B) algo i hm [5,6] each hei limi a ions when sol ing la ge-scale
noncon ex op imiza ion p oblems a ising om many pa ame e es ima ion p oblems [7–9].
To o e come hese limi a ions, we [10] ex ended he s anda d B&B algo i hm by using
g owing da ase s. B ie ly speaking, we s a he B&B algo i hm wi h a educed model
ob ained by picking only a small subse o he ull da ase and augmen he da ase un il
con e ging o he ull da ase p o ided. Fo his, we in oduced augmen a ion ules which
decide o each p ocessed node whe he o augmen he da ase o o b anch he pa ame e
domain. We ha e p o en ha he B&B algo i hm wi h g owing da ase s emains a DGO
me hod, see Theo em 2 o [10]. A key poin o he p oo is ha he lowe bounding p ob-
lem based on educed da ase s yields a alid lowe bound o he o iginal p oblem, i.e., he
pa ame e es ima ion p oblem based on he ull da ase . Ano he key poin is he choice o
an augmen a ion ule which gua an ees eaching he ull da ase e en ually. Howe e , when
da a educ ion allows o a much loose lowe bound and objec i e alue, con e gence may
be slowed down o e en p e en ed depending on he augmen a ion ule, see Example 1 in
[10]. This b ings us back o he opic o o e i ing.
In he con ex o machine lea ning, o e i ing e e s o he phenomenon o models pe -
o ming well on he da a used o aining bu ail o gene alize o new da a [11,12]. In
p ac ice, he ac ual pe o mance o he ained model is he e o e commonly es ima ed
based on independen da ase s, he so-called alida ion se s. We ans e hese indings o
he B&B algo i hm wi h g owing da ase s by using ou -o -sample e alua ions o imp o ing
he lowe bounds calcula ed based on he educed da ase ( educed lowe bound). In de ail,
we use an app oxima ed lowe bound gi en by a combina ion o he educed lowe bound and
he ou -o -sample e alua ion o (i)a no el augmen a ion ule and (ii) o p uning. While
(i)yields a heu is ic ule aiming o imp o e he pe o mance o he de e minis ic app oach,
wi h (ii)we loose he heo e ical gua an ee o con e ging owa ds he global solu ion and
he e o e ob ain me e heu is ic app oaches. To es ima e whe he he heu is ic p uning indeed
cu s o he global solu ion, we p opose a pos -p ocessing check o he inal lowe bound
a e he e mina ion o he B&B algo i hm.
In [10], we p oposed o pick he da a poin s o he educed da ase s andomly om he
ull da ase . In his a icle, we exploi his andomness o imp o ing he educed lowe bound
o bo h he heu is ic augmen a ion ule and he heu is ic p uning. In ac , esampling is a
common ool in s a is ics o educe he bias and a iance o es ima o s, c . [13,14]and[15,
Chap e 5]. In ou app oach, esampling a educed da ase comes wi h he calcula ion and
op imiza ion o a lowe bounding p oblem, making i compu a ionally cos ly. We he e o e
p opose o use wo subsamples o upda ing he educed lowe bound based on he ini ial
da ase .
All p oposed ex ensions o he B&B algo i hm wi h g owing da ase s a e implemen ed
in ou open-sou ce sol e MAiNGO1[16] which is a DGO sol e o ac o able mixed-
in ege nonlinea p og ams. We pe o m an ex ensi e case s udy compa ing he de e minis ic
and heu is ic app oaches o he B&B algo i hm wi h g owing da ase s wi h he s anda d
B&B algo i hm as a benchma k. Fo his, we e isi eal-wo ld applica ions om ou p e-
ious wo k and collec ed u he models om li e a u e esul ing in 13 di e en pa ame e
1A ailable a h ps://gi . w h-aachen.de/a -s /public/maingo.
123
Jou nal o Global Op imiza ion (2025) 92:615–642 617
es ima ion p oblems co e ing he ields o p ocess sys ems enginee ing, biochemis y, and
machine lea ning. Ready- o-use implemen a ions o he p oblem o mula ions a e published
in ou open-sou ce eposi o y GloPSE2.
The emainde o his a icle is s uc u ed as ollows. Sec ion 2comp ises he ma hema ical
backg ound, whe e we s a wi h an o e iew on ou no a ion in Sec ion 2.1. Subsequen ly,
he main algo i hmic and heo e ical ad ances o he B&B algo i hm wi h g owing da ase s
om [10] a e ecalled in Sec ion 2.2. In Sec ion 3, we ob ain an app oxima e lowe bound o
he o iginal p oblem based on he educed lowe bound and ou -o -sample e alua ion. This
app oxima ion is used o a no el augmen a ion ule in Sec ion 3.1, and o in oducing a
heu is ic app oach including a pos -p ocessing s ep in Sec ion 3.2. In Sec ion 3.3, we ans e
he indings o es ima ion p oblems minimizing he mean squa ed e o yielding a second
heu is ic app oach. In Sec ion 4, we p opose a heu is ic lowe bound based on esampling.
In Sec ion 5, we pe o m an ex ensi e case s udy e alua ing he p oposed pos -p ocessing
p ocedu e and compa ing all app oaches o he B&B algo i hm wi h g owing da ase s wi h
he s anda d B&B algo i hm, be o e we conclude in Sec ion 6.
2 P elimina ies
2.1 P oblem o mula ion and no a ion
As in ou p e ious wo k [10], we ocus on inding globally op imum pa ame e alues p∈P
minimizing
min
p∈P
(xd,yd)∈D
g(p;xd,yd)(SSE)
s. . h(xd,yd;p)≤0∀(xd,yd)∈D
h(p)≤0,(PE)
whe e g(·; xd,yd)=( (xd;·)−yd)2is he squa ed p edic ion e o o a pa ame e ized
model unc ion (·; p):Rm→R o da a poin (xd,yd)∈DR
m×R,andh(xd,yd;·)
and
ha e he esidual unc ions o he da a-dependen and da a-independen inequali y con-
s ain s on pa ame e s p∈P, espec i ely. Le he pa ame e domain PR
nbe a closed,
bounded box. In case o in ege pa ame e s, le he pa ame e domain consis o subse-
quen disc e e alues. No e ha g(·; xd,yd)is nonnega i e, and s ic ly posi i e in case o
model-da a misma ch caused by measu emen e o s, subop imal pa ame e alues, o model
misspeci ica ion.
In he ollowing, we call D he ull da ase and pa ame e es ima ion p oblem (PE) he
o iginal p oblem.Le gc (·; xd,yd):P→Rbe a non-nega i e con ex unde es ima o o
g(·; xd,yd)as well as hc (xd,yd;·)and
hc be con ex unde es ima o s o h(xd,yd;·)and
h,
espec i ely. Then, he op imal solu ion o he con ex op imiza ion p oblem
min
p∈P
(xd,yd)∈D
gc (p;xd,yd)(LBP)
s. . hc (xd,yd;p)≤0∀(xd,yd)∈D
hc (p)≤0,
2A ailable a h ps://gi . w h-aachen.de/a -s /public/glopse.
123
618 Jou nal o Global Op imiza ion (2025) 92:615–642
gi es a lowe bound on he op imal solu ion o he o iginal p oblem, which we will call ull
lowe bound.We e e o educed p oblem and educed lowe bound when eplacing he
da ase wi h a educed da ase Dk⊆Dwi hin (PE)and(LBP), espec i ely. No e ha , in
common DGO so wa e, he lowe bounding p oblem (LBP) is u he elaxed o a linea
p og am wi hou losing i s alidi y o he o iginal p oblem by linea izing alid con ex
unde es ima o s.
In he B&B node Nk=(Pk,Dk)p ocessed in B&B i e a ion k∈N, op imiza ion p ob-
lems (PE)and(LBP) a e sol ed o pa ame e domain Pk⊆Pand da ase Dk⊆D.Le uk
be he bes uppe bound ound un il i e a ion k.Le l ull
kand l ed
kbe he ull and educed lowe
bound calcula ed in node Nkwi h op imal pa ame e alues plb, ull
kand plb, ed
k, espec i ely.
I a lowe bound calcula ed based on a educed da ase canno be gua an eed o be alid o
he o iginal p oblem, we will call i heu is ic lowe bound
lkcompa ed o alid lowe bounds
lk.
2.2 The B&B algo i hm wi h g owing da ase s
As p oposed in [10], he B&B algo i hm wi h g owing da ase s ex ends he s anda d algo i hm
by a da a educ ion s ep be o e en e ing he B&B loop and a sub ou ine o deciding whe he o
b anch o augmen a node, see Figu e 1. Fo his, we associa e all nodes Nk=(Pk,Dk)∈N
o he B&B ee wi h bo h a pa ame e domain PkPand a da ase Dk⊆D.In he
sub ou ine, c . Sub ou ine 1 o [10], we call an augmen a ion ule A:N→{T ue,False}.
I A(Nk)=T ue, he da ase is augmen ed, i.e., we add one child node Nnew =(Pk,Dnew)
wi h Dnew Dk. O he wise, we b anch he pa ame e domain while e aining he da ase ,
i.e., we add wo child nodes Nnew,1 =(Pk,1,Dk)and Nnew,2 =(Pk,2,Dk)wi h pa i ion
Pk,1∪Pk,2=Pk. Wi h his, we ob ain an algo i hm which is gua an eed o con e ge owa ds
he global op imum o (PE) i we use a ini ely con e gen augmen a ion ule [10].
De ini ion 1 (De ini ion 1 o [10]) Le Dk⊆Dbe he da ase used in node Nk,whichis
p ocessed in i e a ion ko he B&B algo i hm wi h g owing da ase s depic ed in Figu e 1.
The augmen a ion ule A:N→{T ue,False}comple es ini ely, i o any in ini e nes ed
sequence o nodes {Nkj}j→∞ wi h Nkj=(Pkj,Dkj)i holds ∃J<∞:Dkj=D∀j≥J.
Fo comple eness o con en s, we epea he main heo e ical esul s o [10]. The in e -
es ed eade may e e o he o iginal publica ion [10] o mo e de ails and he p o es. The
heo e ical esul s a e based on he ollowing assump ions.
Assump ion 1 (Assump ions 1 and 2 o [10])
(i) Le (xd;·):P→Rand h(xd,yd;·):P→R o any ixed (xd,yd)∈Das well
as
h:P→Rbe con inuous.
(ii) Le gc (·; xd,yd)be any nonnega i e con ex unde es ima o o g(·; xd,yd)o e P
o any ixed (xd,yd)∈D.
(iii) Le hc (xd,yd;·)and
hc be any con ex unde es ima o o h(xd,yd;·) o any ixed
(xd,yd)∈Dand
h, espec i ely, o e P.
Wi h he help o he nonnega i e con ex unde es ima o s, c . Assump ion 1(ii), we can
cons uc alid lowe bounds based on a educed da ase .
Lemma 1 (Lemma 1 (i) o [10] (adap ed)) Le Assump ion 1hold.
Then, (xd,yd)∈D ed gc (p;xd,yd)is a con ex unde es ima o o bo h (xd,yd)∈D ed
g(p;xd,yd)and (xd,yd)∈Dg(p;xd,yd)o e P o any D ed ⊆D.
123
Jou nal o Global Op imiza ion (2025) 92:615–642 619
Fig. 1 Flow cha o he B&B algo i hm wi h g owing da ase s [10] whe e he ex ensions o he s anda d
B&B algo i hm a e highligh ed wi h dashed boxes.
Finally, we ex ended he p oo o con e gence o a s anda d B&B algo i hm gi en in Theo em
5.26 o Loca elli and Schoen [17]. In pa icula , we build upon hei de ini ions o exac ness
in he limi , heiso onic p ope y o unde es ima o s, and exhaus i eness o b anching gi en
in De ini ion 5.4, Equa ion (5.34), and De ini ion 5.5, espec i ely, o [17].
Theo em 1 (Theo em 2 o [10] (adap ed)) Le Assump ion 1hold. We apply a spa ial
B&B algo i hm wi h op imali y ole ance ε>0 o (PE). Le he con ex unde es ima o s
gc
D,h
c (xd,yd;·)∀(xd,yd)∈D, and
hc be exac in he limi . Le gc (·; xd,yd)and
123
620 Jou nal o Global Op imiza ion (2025) 92:615–642
Table 1 Da ase s, co esponding op imal objec i e and scaled op imal objec i e as gi en o Example 1 o
[10]
Da a poin s Op . obj. Op . obj. scaled wi h |D|
|D ed|
D0={(0,0.6)}0.0 3 ·0=0
D1={(0,0.6), (0,1)}0.08 3
2·0.08 =0.12
D={(0,0), (0,0.6), (0,1)}0.5067 0.5067
hc (xd,yd;·)sa is y he iso onic p ope y ∀(xd,yd)∈D. Le he subdi ision p ocess o he
B&B algo i hm be exhaus i e.
I we use an augmen a ion ule Awhich comple es ini ely, hen he B&B algo i hm wi h
g owing da ase s depic ed in Figu e 1 e mina es a e a ini e numbe o i e a ions and
•ei he es ablishes ha he p oblem is in easible i he inal uppe bound equals in ini y
•o e u ns an ε-op imal solu ion i he inal lowe bound is ini e.
No e ha i is essen ial o he p oo o ini e con e gence ha he augmen a ion ule
comple es ini ely. O he wise he e may be a gap be ween educed and ull lowe bound
p e en ing augmen ing o e en p uning based on he educed da ase , see he ollowing
example.
Example 1 (Example 1 o [10] (adap ed)) We wan o sol e
min
a∈[0,25](a−1)2+(a−0.6)2+(a−0)2,
whe e we ind a linea unc ion (x;a)=a·x h ough he o igin and h ee da a poin s
D={(1,0), (1,0.6), (1,1)}a he same inpu x=1, wi h a nai e implemen a ion o he
B&B algo i hm wi h g owing da ase s using augmen a ion ule Ascaling wi h ρ=1. Assume
ha he ( educed) da ase s a e chosen as in Table 1. E en i he lowe bound calcula ed based
on educed da ase s D0and D1is exac , i.e., equals he espec i e op imal objec i e a he
op imum poin p∗, gaps would emain
(xd,yd)∈D0
gc (p∗;xd,yd)
(xd,yd)∈D1
gc (p∗;xd,yd)
(xd,yd)∈D
gc (p∗;xd,yd)≤
(xd,yd)∈D
g(p∗;xd,yd)
B anching does no help ei he since we al eady assume exac lowe bounds. Wi h ha ,
nei he augmen ing no con e gence is possible.
3 Ou -o -sample es ima ion wi h g owing da ase s
The educed lowe bound is alid o he o iginal p oblem bu may be oo loose o augmen ing
o p uning, c . Sec ion 2.2 and [10]. In his case, he ime sa ings due o he da a educ ion may
be canceled ou by he unnecessa y la ge B&B ee. Thus, we p opose o apply ou -o -sample
e alua ion o a be e app oxima ion o he ull lowe bound. We expec ha he solu ion o
he educed bounding p oblem plus his addi ional e alua ion emains compu a ionally as e
123
Jou nal o Global Op imiza ion (2025) 92:615–642 621
han calcula ing he ull lowe bound. In de ail, we e alua e (LBP) o e all emaining da a
poin s D Dka he op imal solu ion poin plb, ed
kyielding he heu is ic ou -o -sample lowe
bound
loos
k:=
(xd,yd)∈D Dk
gc (plb, ed
k;xd,yd).
No e ha we de ine he ou -o -sample lowe bound only o p ope subse s DkD. Based
on empi ical e idence, we expec he ou -o -sample lowe bound o be alid o he o iginal
p oblem. In ac , he ou -o -sample lowe bound sums up less nonnega i e e ms han he
ull lowe bound, whe e each e m is a unc ion e alua ion a poin plb, ed
kwhich is ypically
close o equal o he op imal solu ion poin plb, ull
k.
Pos ula e 1 Fo B&B nodes wi h educed da ase s DkD, ou -o -sample lowe bound
loos
k
is smalle han o equal he ull lowe bound l ull
kand he e o e alid o he o iginal p oblem.
Pos ula e 1may be iola ed o pa hological cases as shown in he ollowing example.
Example 2 (Non- alid
loos
k) Assume ha we a e looking o he bes slope o a linea unc ion
h ough da a poin s D={(1,1), (2,5.5), (3,3)}R
2yielding he uncons ained con ex
pa ame e es ima ion p oblem
min
p∈[0,10]
(xd,yd)∈D
(p·xd−yd)2.(1)
Assume u he ha he educed da ase a B&B i e a ion kis gi en by Dk={(1,1), (3,3)}.
Due o he con exi y o (1), we can sol e i also as he lowe bounding p oblem. We obse e
l ed
k=0 a op imal solu ion poin plb, ed
k=1, meaning ha we can i da a poin s Dkexac ly
by he iden i y. We ob ain
loos
k=(1·2−5.5)2=12.25, and l ull
k=8.75 a op imal solu ion
poin plb, ed
k=1.5. Hence, ou -o -sample lowe bound
loos
kis la ge han he ull lowe bound
l ull
k.
Wi h he help o bo h educed and ou -o -sample lowe bound, we can enclose he ull
lowe bound.
Lemma 2 Le gc (·; xd,yd)be Lipschi z con inuous in domain Pwi h Lipschi z cons an s
Ld>0 o any d =1,...,|D|.I plb, ed
kis easible o (LBP), hen
l ed
k+
loos
k−L·||plb, ull
k−plb, ed
k|| ≤ l ull
k≤l ed
k+
loos
k
wi h L := |D|
d=1Ld.
P oo Fo he i s inequali y, we obse e
(xd,yd)∈D
gc (plb, ull
k;xd,yd)
=
(xd,yd)∈Dgc (plb, ed
k;xd,yd)+gc (plb, ull
k;xd,yd)−gc (plb, ed
k;xd,yd)
=
(xd,yd)∈Dk
gc (plb, ed
k;xd,yd)+
(xd,yd)∈D Dk
gc (plb, ed
k;xd,yd)
+
(xd,yd)∈Dgc (plb, ull
k;xd,yd)−gc (plb, ed
k;xd,yd).(2)
123
622 Jou nal o Global Op imiza ion (2025) 92:615–642
Since plb, ed
kis easible o (LBP)and plb, ull
kminimizes (LBP), we ha e
(xd,yd)∈D
gc (plb, ull
k;xd,yd)≤
(xd,yd)∈D
gc (plb, ed
k;xd,yd)
and, oge he wi h Lipschi z con inui y,
−
(xd,yd)∈Dgc (plb, ull
k;xd,yd)−gc (plb, ed
k;xd,yd)
=|
(xd,yd)∈Dgc (plb, ull
k;xd,yd)−gc (plb, ed
k;xd,yd)|
addi i i y
≤
(xd,yd)∈D
|gc (plb, ull
k;xd,yd)−gc (plb, ed
k;xd,yd)|
Lipschi z
≤
(xd,yd)∈D
Ld·||plb, ull
k−plb, ed
k||.(3)
Inse ing (3)in(2)gi es
(xd,yd)∈D
gc (plb, ull
k;xd,yd)≥
(xd,yd)∈Dk
gc (plb, ed
k;xd,yd)+
(xd,yd)∈D Dk
gc (plb, ed
k;xd,yd)
−L·||plb, ull
k−plb, ed
k||
which is he same as he i s inequali y o Lemma 2.
Fo he second inequali y, we obse e
l ull
k=
(xd,yd)∈D
gc (plb, ull
k;xd,yd)≤
(xd,yd)∈D
gc (plb, ed
k;xd,yd)
due o he op imali y o plb, ull
kand he easibili y o plb, ed
k o he ull lowe bounding
p oblem (LBP). Mo eo e , we ha e
(xd,yd)∈D
gc (plb, ed
k;xd,yd)=
(xd,yd)∈Dk
gc (plb, ed
k;xd,yd)
+
(xd,yd)∈D Dk
gc (plb, ed
k;xd,yd)
which concludes he p oo .
Rega ding he easibili y o poin plb, ed
k o (LBP), we no e ha he da a-independen con-
s ain s
hc a e in a ian o he da ase used. Thus, he easibili y is na u ally gi en o any
model wi hou da a-dependen cons ain s hc (xd,yd;·).
Based on Lemma 2,wede ine heheu is iccombined lowe bound
lcombi
k:= l ed
k+
loos
k.
No e ha he posi i i y o he cumula ed Lipschi z cons an Lis c ucial o bounding he
ull lowe bound below based on he combined lowe bound. Due o he exhaus i eness
o b anching, we ha e diam(Pk)→0 o B&B i e a ion k→∞and, hus, || plb, ull
k−
plb, ed
k||→0(k→∞). E en a he beginning o he B&B algo i hm, i.e., o small k, he
op imal poin s plb, ull
kand plb, ed
ko en coincided in nume ical expe imen s pe o med wi h
he models in es iga ed in Sec ion 5. Consequen ly, we expec nume ical ad an ages when
123
Jou nal o Global Op imiza ion (2025) 92:615–642 629
Then,
Va ⎡
⎣gc
Dk,1(plb, ed,1
k)+gc
Dk,2(plb, ed,2
k)
2⎤
⎦
=
1+Co gc
Dk,1(plb, ed,1
k), gc
Dk,2(plb, ed,2
k)
2·Va gc
Dk,1(plb, ed,1
k).
The s a emen o Lemma 5 ollows om Dk,1and Dk,2ha ing he same dis ibu ion as well
as he scaling and addi i e p ope ies o a iances.
As Co [·,·]∈[−1,1]by he Cauchy-Schwa z inequali y, Lemma 5implies ha bagging
can only imp o e he a iance
Va ⎡
⎣gc
Dk,1(plb, ed,1
k)+gc
Dk,2(plb, ed,2
k)
2⎤
⎦≤Va gc
Dk,1(plb, ed,1
k).
Equali y can only be a ained o pe ec ly co ela ed da ase s gi ing
Co gc
Dk,1(plb, ed,1
k), gc
Dk,2(plb, ed,2
k)=1. Con a ily, o unco ela ed da ase s, i.e., a co -
ela ion o 0, we can hal he a iance by picking a second subsample
Va ⎡
⎣gc
Dk,1(plb, ed,1
k)+gc
Dk,2(plb, ed,2
k)
2⎤
⎦=1
2Va gc
Dk,1(plb, ed,1
k).
The co ela ion equals ze o o independen andom a iables. Howe e , we canno expec
di e en educed da ase s o be independen , since (i) he e may be sys ema ic e o a ec ing
a subse o da a poin s simila ly and (ii) he da ase s a e d awn om he same sample Dand
may he e o e con ain common da a poin s. The ex en o (i)highly depends on he model
and he ac ual da ase Dwhich a e bo h pa o he ixed p oblem o mula ion in ou se up. Fo
(ii), we ha e highe chances ha di e en subsamples Dk,1and Dk,2a e no in e sec ing,
i he size o he educed da ase s Dkis small compa ed o he ull da ase D. By de aul
se ings, we pick 10% o he da a poin s om he ull da ase o he ini ial da ase and add
ano he 25% o he da a poin s when augmen ing. This means he second smalles da ase
con ains al eady a compa a i ely la ge pa o he ull da ase , namely 35% o all da a poin s.
Fo example, assume a ull da ase wi h |D|=100. The p obabili y ha wo subsamples
wi h |Dk,∗|=10 do no in e sec is abou 0.33, while i is abou 2.75 ×10−9 o subsamples
wi h |Dk,∗|=35. Thus, we use he p oposed esampling heu is ic only o upda e he educed
lowe bound calcula ed based on he ini ial da ase .
5 Nume ical esul s
In his sec ion, we s udy he compu a ional pe o mance o he B&B algo i hm wi h g ow-
ing da ase s using he s anda d B&B algo i hm as a benchma k. In de ail, we in es iga e
he de e minis ic app oach om [10] as well as he heu is ic app oaches om Sec ions 3.2
and 3.3 using di e en augmen a ion ules. We un each o he app oaches wi h and wi hou
esampling he ini ial da ase , c . Sec ion 4. Bo h he s anda d B&B algo i hm and all dis-
cussed algo i hmic app oaches o he B&B algo i hm wi h g owing da ase s a e a ailable in
ou open-sou ce sol e MAiNGO 0.8.2.
123
630 Jou nal o Global Op imiza ion (2025) 92:615–642
Table 2 O e iew on gene al p ope ies and e e ences o he models and da a used in he case s udy
Name n|D|dim(x)Da a Op . class O iginal e e ences
Model Da a
P ocess sys ems enginee ing
EOS262 9 262 2 syn he ic, exac MINLP [21,22][10]
EOS2262 9 2262 2 syn he ic, exac MINLP — ”——
”—
EOS262noisy 9 262 2 syn he ic, noisy MINLP — ”——
”—
EOS2262noisy 9 2262 2 syn he ic, noisy MINLP — ”——
”—
IHMcon 20 284 1 measu ed NLP [23][24,25]
IHMunc 10 284 1 measu ed NLP — ”——
”—
kine ics 5 446 1 measu ed DO [1,2,26][2]
EIS 7 26 1ameasu ed NLP [27][28,29]
Biochemis y
TSP 12 20 8 syn he ic, exac DO [30,31][10]
TSPnoisy 12 20 8 syn he ic, noisy DO — ”——
”—
Machine lea ning
GMMcon 6 272 1 measu ed NLP [32][33,34]
GMMineq 5 272 1 measu ed NLP — ”——
”—
ainANN 21 220 3 measu ed NLP [35,36][37,38]
aThe model ou pu is a complex numbe , i.e., dim(y)=2
Benchma k lib a ies om ma hema ical p og amming, e.g., MINLPlib [39], P ince onLib
[40], and he COCONUT benchma k [41], only accoun o pa ame e es ima ion p oblems
(PE) conside ing small da ase s which do no equi e ou ex ension. Besides, ou ocus is
he solu ion o eal-wo ld applica ions ex ending he nume ical p oo -o -concep ob ained
in [10]. Hence, we collec ed di e en models om bo h li e a u e and ou p e ious wo k
s emming om p ocess sys ems enginee ing, machine lea ning, and biochemis y. These
models co e di e en classes o op imiza ion p oblems including mixed-in ege nonlinea
p og ams (MINLPs), nonlinea p og ams (NLPs), and dynamic op imiza ion p oblems (DOs)
wi h up o n=21 unknown pa ame e s and a di e en numbe and dimension o da a poin s
in ull da ase D,seeTable2. The exac ma hema ical exp essions a e p o ided in Online
Resou ce 1. Fo eady- o-use implemen a ions o he model as well as he exac da a poin s
used e e o he a o emen ioned eposi o y GloPSE2.
All compu a ions a e pe o med on In el Xeon Pla inum 8160 p ocesso s “SkyLake” ( e-
quency 2.1GHz, RAM =3.75GB o a single node). E en small de ia ions in compu a ional
imes o p ocessing one node may signi ican ly change he numbe o nodes p ocessed wi hin
ou CPU ime limi o 23h when adding up. Consequen ially, he inal lowe and uppe bound
may change as well. Thus, we epea each un 5 imes and epo he median o he inal
bounds and, in case o con e gence, CPU imes. No e ha we choose a CPU ime limi o
23h such ha we can gua an ee a o al un ime o 24h including he ini ializa ion o he model
and p epa a ions o he ou pu da a.
We se he ela i e op imali y ole ance o εR=0.1. The absolu e ole ance is ixed o
εA=0.01 o all app oaches using (SSE). When using (MSE), he objec i e is scaled by he
numbe o da a poin s. In analogy, we scale he absolu e op imali y ole ance o model speci ic
alues εA=0.01/|D|when using (MSE). In each op imiza ion un, we use Ipop e sion
3.12.12 [42] o unning 3 local sea ches as a p e-p ocessing s ep in he oo node. Mo eo e ,
123
Jou nal o Global Op imiza ion (2025) 92:615–642 631
Fig. 5 Lowe bounds o nodes in Nchanged be o e (◦) and a e (×) pos -p ocessing and change o inal lowe
bound
ldue o pos -p ocessing compa ed o inal uppe bound uand ela i e op imali y ole ance εR
we use McCo mick elaxa ions [43,44] calcula ed wi h MC++ [45] and a linea iza ion in he
midpoin o he pa ame e in e als o ob ain a linea p og am (LP) o lowe bounding. Fo
models IHMcon, IHMunc, EIS, TSP, TSPnoisy, GMMcon, GMMineq, and ainANN, we
sol e he LP wi h linea op imize CLP 1.17.0 [46]. As he esul ing LP o he EOS models
wi h noisy measu emen da a as well as model kine ics seems o be nume ically di icul o
CLP and al e na i e LP sol e CPLEX [47], we use in e al ex ensions [48] calcula ed wi h
FILIB++ [49] o models EOS262, EOS2262, EOS262noisy, EOS2262noisy, and kine ics.
When using pu e in e al ex ensions, we disable he op imali y-based bound igh ening [50].
The uppe bounding p oblem is sol ed wi h local op imize LBFGS [51,52] implemen ed
in he NLOPT oolbox 2.5.0 [53] o all models. To minimize de ia ions caused by small
di e ences in he CPU ime equi ed o p ocessing a node, we limi he numbe o s eps
pe o med by local sol e s Ipop and LBFGS a he han he CPU ime used o each local
sea ch. The comple e lis ing o se ings is p o ided in Online Resou ce 2.
5.1 E alua ion o pos -p ocessing
A i s , we s udy he pos -p ocessing s ep o check whe he we can expec he heu is ic
app oaches o con e ge o he global solu ions. Table 3summa izes he numbe o nodes
acked o pos -p ocessing, he implica ions o he lowe bounds epo ed, and he maximum
CPU ime used o pos -p ocessing. No e ha hese a e he s a is ics o un 1 ou o he 5
epe i i e uns only. The numbe o nodes acked as well as which speci ic nodes a e acked
may a y i he numbe o p ocessed nodes di e s. Howe e , we expec o make he la ges
mis akes ea ly, namely wi h small da ase s, which is co e ed by all 5 epe i i e uns. Mo e
impo an ly, no e ha he s a is ics o models IHMcon, IHMunc, EIS, and ainANN a e no
lis ed, jus as he s a is ics o he MSE heu is ic o models TSP and TSPnoisy, since no nodes
a e acked o pos -p ocessing in hese cases. In hese cases, we do no p une based on a
educed da ase . This means we ha e a de e minis ic p ocedu e so a a he cos o a la ge
B&B ee. Simila ly, in uns wi h |Npos p o|<100 i seems o be ha d o p une based on he
educed da ase s. As an excep ion, |Npos p o|<100 comp ises also he case whe e we need
o p ocess less han 100 nodes o con e gence, c . TSP model in Table 3.
We obse e ha o only 4 ou o 13 models he e a e nodes whe e he lowe bound l ull
k
calcula ed in pos -p ocessing alls below he inal uppe bound, i.e., whe e we may ha e
made a w ong p uning decision due o da a educ ion. Ou o hese, he inal lowe bound is
upda ed solely o 3 models, namely when using he SSE heu is ic applying augmen a ion
ules scaling and ol o model EOS262 and augmen a ion ule ol o models GMMcon
and GMMineq.
We pick wo exempla y cases o depic he changes due o pos -p ocessing in Figu e 5.In
bo h cases, he nodes which a ec he inal lowe bound
lha e been only jus p uned wi h
lcombi
k(1−εR)·u. In model EOS262, he changes due o pos -p ocessing a e essen ially
nonexis en : we ind nume ically insigni ican di e ences o 10−14 o 10−18. In con as o
ha , he inal lowe bound o models GMMcon and GMMineq change signi ican ly, e.g.,
123
632 Jou nal o Global Op imiza ion (2025) 92:615–642
Table 3 Pos -p ocessing s a is ics o he models wi h acked nodes, i.e., wi h Npos p o =∅, including he numbe o nodes acked, he numbe o nodes whe e he lowe bound
changed signi ican ly wi hin pos -p ocessing, a lag indica ing whe he he inal lowe bound was changed as well, and he maximum CPU ime o e all augmen a ion ules
Model Re- |Npos p o|No. o nodes w ongly p unedaFinal lowe bound changed?bMaximum
sampling? CPU ime [s]
SSE heu is ic using augmen a ion ules CONST /SCALING /TOL
EOS262 No 100/ 100 / 100 0 / 2/2 0/ 1 / 1 0.7
Yes 100/ 100 /100 0/ 3 / 3 0/ 1/1 0.9
EOS2262 no 100/ 100 / 100 0 / 0/0 0/ 0 / 0 8.2
Yes 100/ 100 /100 0/ 0 / 0 0/ 0/0 9.9
EOS262noisy no 22/ 72 / 72 0/ 0 / 0 0/ 0 /0 0.6
Yes 22/72/72 0/0/0 0/0/0 1.0
EOS2262noisy no 52/ 100 / 100 0/ 0 / 0 0/ 0/0 7.1
Yes 66/ 100 /100 0/ 0 / 0 0/ 0/0 7.9
kine ics no 100/ 100 / 100 0 / 0/0 0/ 0 / 0 1.6
Yes 100/ 100 /100 0/ 0 / 0 0/ 0/0 1.6
TSP no 100/ 100 / 4 0 / 0/0 0/ 0 / 0 1.3
Yes 100/ 100 /4 0/ 0 / 0 0/ 0/0 0.3
TSPnoisy no 16/ 100 / 0 0 / 0/0 0/ 0 / 0 0.2
Yes 0/100/0 0/0/0 0/0/0 0.2
GMMcon no 44/ 100 / 100 0 / 6/74 0/ 0 / 1 0.1
yes 44/ 100 / 100 0 / 2/70 0/ 0 / 1 0.1
123
Jou nal o Global Op imiza ion (2025) 92:615–642 633
Table 3 con inued
Model Re- |Npos p o|No. o nodes w ongly p unedaFinal lowe bound changed?bMaximum
sampling? CPU ime [s]
GMMineq no 100/ 100 / 100 0 / 0/96 0/ 0 / 1 0.2
yes 100/ 100 / 100 0 / 0/99 0/ 0 / 1 0.2
MSE heu is ic using augmen a ion ules CONST /OOS /TOL
EOS262 no 100/ 100 / 100 0 / 1/0 0/ 0 / 0 0.5
yes 100/ 100 / 100 0 / 0/0 0/ 0 / 0 1.0
EOS2262 no 100/ 100 / 100 3 / 1/1 0/ 0 / 0 6.4
yes 100/ 100 / 100 2 / 4/1 0/ 0 / 0 7.1
EOS262noisy no 12/100 / 100 0 / 0 /0 0/0 / 0 0.6
yes 30/12/92 0/0/0 0/0/0 0.8
EOS2262noisy no 4/ 76 / 76 0/ 0 / 0 0/ 0 /0 5.2
yes 12/76/76 0/0/0 0/0/0 5.8
kine ics no 100/ 100 / 100 0 / 0/0 0/ 0 / 0 1.4
yes 100/ 100 / 100 0 / 0/0 0/ 0 / 0 1.7
GMMcon no 100/ 100 / 100 9 / 17/17 0/ 0 / 0 0.1
yes 100/ 76 / 100 9 / 12/8 0/ 0 / 0 0.1
GMMineq no 100/ 100 / 100 1 / 4/4 0/ 0 / 0 0.1
yes 100/ 100 / 100 1 / 4/4 0/ 0 / 0 0.0
aNodes wi h l ull
k<u, see Sec ion 3.2
b0 = no, 1 = yes
123
634 Jou nal o Global Op imiza ion (2025) 92:615–642
om 723.7 o 406.7 o GMMineq when using esampling, ex ending he ela i e op imali y
gap om 15% o 86%.
Fo 95% o 156 cases, including he 2 heu is ic app oaches wi h 3 di e en augmen a ion
ules each o 13 models wi h and wi hou esampling, he inal lowe bound was no changed
and only in 4 cases he change was signi ican . In pa icula , he inal lowe bound was changed
only when using he SSE heu is ic. No e ha he pos -p ocessing is e y cheap: o e all 5
epe i ions o he case s udy we measu ed a maximum un ime o 11.3s.
In conclusion, e en he heu is ic app oaches con e ge owa ds he global solu ion in mos
o he cases. The pos -p ocessing p ocedu e de ec s he emaining cases wi h small compu-
a ional e o and p o ides means o deciding whe he he heu is ic p uning signi ican ly
dis o s he solu ion ob ained.
5.2 Compa ison o compu a ional pe o mance
Finally, we s udy he pe o mance o he B&B algo i hm wi h g owing da ase s wi h he s an-
da d B&B algo i hm as a benchma k. Only 4 models con e ge wi hin he CPU ime limi o
23h o a leas one o he app oaches including all 3 models wi h exac da a, namely EOS262,
EOS2262, and TSP, compa e Table 4. Fo models EOS262 and EOS2262, he de e minis ic
app oach is he as es wi h dec easing he un ime o he s anda d B&B algo i hm by a ac o
o 3 and up o 4, espec i ely. Fo he TSP model, he MSE heu is ics inds he global solu-
ion in he oo node, esul ing in a un ime o 2s, while he s anda d B&B algo i hm akes
abou 2h o con e gence wi h (SSE) and hi s he CPU ime limi wi h (MSE). No e ha o
exac da a, he inal lowe bound equals he na u al lowe bound o 0 excep o nume ical
ole ances. Thus, using educed da ase s allows o educing he compu a ional cos s while
e aining he igh ness o he bounds on he op imal solu ion.
Con a ily, he s anda d B&B algo i hm pe o ms bes o he EIS model: i con e ges
wi hin 8h, whe eas all app oaches o he B&B algo i hm wi h g owing da ase s hi he CPU
ime limi . In he EIS model, we i a model wi h 7 unknown pa ame e s o a ull da ase D
R×R2wi h |D|=26 da a poin s and, wi h he de aul se ings, o educed da ase s con aining
3, 10, 17, and 24 da a poin s. Consequen ly, his pa ame e es ima ion p oblem is p one o
o e i ing, in pa icula , when using educed da ase s. In o he wo ds, he compu a ional
sa ings due o he da a educ ion come a he cos o loose lowe bounds. Ou -o -sample
es ima ion allows o imp o ing upon he quali y o he lowe bounds calcula ed based on
educed da ase s, c . Figu e 6.
Figu e 6p o ides an o e iew o he ange o inal lowe and uppe bounds ob ained by
he di e en algo i hms wi hin he CPU ime limi . No e ha he lowe bounds include, whe e
applicable, he co ec ion pe o med in he pos -p ocessing s ep and ha he exac alues a e
gi en in Online Resou ce 1. The i s ow o Figu e 6con ains he models conside ing exac
da a such ha he inal lowe bound is equal o ze o excep o nume ical ole ances and he
op imal solu ion is in he ange o he op imali y ole ance. Fo he emaining models, all
app oaches gi e a simila o e en he same solu ion a e he CPU ime limi , compa e he
uppe bounds depic ed in Figu e 6. Fo 7 ou o 10 models conside ing noisy da a, he SSE
heu is ic gi es he bes , i.e., la ges , inal lowe bound. Fo 2 o hese 10 models, he SSE
heu is ic and he s anda d B&B algo i hm pe o m simila ly. Only o IHMcon, he s anda d
B&B algo i hm inds he bes lowe bound. In acco dance wi h he esul s o Sec ion 5.1,
we he e o e conclude ha he SSE heu is ics allows o signi ican ly inc ease he inal lowe
bound wi hin a gi en CPU ime limi .
123
Jou nal o Global Op imiza ion (2025) 92:615–642 635
Table 4 To al CPU ime needed o con e gence o he B&B algo i hm. Only models which con e ge wi hin he CPU ime limi o a leas one o he algo i hmic app oaches,
namely he s anda d B&B algo i hm wi h objec i e (SSE)and(MSE), o he de e minis ic and heu is ic app oaches o he B&B algo i hm wi h g owing da ase s using di e en
augmen a ion ules a e lis ed. Bold numbe s indica e he as es un ime o he espec i e model
S anda d B&B De e minis ic App . (SSE) SSE heu is ic MSE heu is ic
Model (SSE)(MSE)cons scaling combi cons scaling ol cons oos ol
Wi hou esampling
EOS262 2.0h 2.1h 1.7h 44min 40 min 13.3h –a–a7.9h –a5.8h
EOS2262 –a–a–a7.5h7.5h–
a–a–a–a–a–a
EIS 9.2h 8.0h–
a–a–a–a–a–a–a–a–a
TSP 1.9h –a–a40min –a–a–a9.2h 2s2s2s
Wi h esampling
EOS262 2.0h 2.1h 1.8h 47min 38 min 12.8h –a–a12.1h –a5.7h
EOS2262 –a–a–a5.5h6.0h –a–a–a–a–a–a
EIS 9.2h 8.0h–
a–a–a–a–a–a–a–a–a
TSP 1.9h –a–a1.0h –a–a–a7.1h 2s2s2s
aHi ing CPU ime limi o 23h
123
636 Jou nal o Global Op imiza ion (2025) 92:615–642
Fig. 6 Final lowe bounds lko
lk(s ic ly below dashed line) and inal uppe bounds u(abo e dashed line)
on he op imal solu ion o he models o any o he app oaches, namely he s anda d B&B algo i hm (s d)
wi h objec i es (SSE)and(MSE) as well as he de e minis ic app oach (de ), he SSE heu is ic (heuS) and
he MSE heu is ic (heuM) o he B&B algo i hm wi h g owing da ase s using he augmen a ion ules depic ed
in Figu es 3and 4. I applicable, he inal lowe bounds a e subjec o pos -p ocessing. The squa es in he
loga i hmic plo s indica e lowe bounds equal o 0
We ecall ha models IHMunc and IHMcon a e ma hema ically equi alen . While he
op imiza ion a iables a e coupled ia equali y cons ain s in he o me , we use his ela ion
as an explici e alua ion unc ion o he la e , compa e also he ull-space and educed-
space o mula ions discussed in [2,54]. While he inal lowe bound epo ed o IHMunc
di e s om 0 only when using he heu is ic app oaches, only he s anda d B&B algo i hm
and he de e minis ic app oach de e mine lowe bounds la ge han 0 o IHMcon. The bes
lowe bound o model IHMunc is in o de o magni ude 106, while he bes lowe bound o
model IHMcon is in o de o magni ude 105. Thus, applying he heu is ic app oaches o he
123
Jou nal o Global Op imiza ion (2025) 92:615–642 637
B&B algo i hm wi h g owing da ase s o he educed-space o mula ion pe o ms bes o
he IHM model. In analogy, he equali y cons ain in GMMcon is used o ix an unknown
pa ame e in GMMineq. In his case, he educed-space o mula ion GMMineq seems o be
sligh ly ad an ageous o inding a good uppe bound, while he lowe bounds ob ained o
models GMMcon and GMMineq a e simila o he di e en app oaches.
When compa ing he CPU imes wi h and wi hou esampling, c . Table 4, he e is no
gene al endency. On he one hand, esampling equi es mo e compu a ional esou ces. On
he o he hand, esampling a ec s he lowe bound. Since MAiNGO uses he solu ion poin
o he lowe bounding p oblem o ini ialize he local sol e o he uppe bounding p oblem,
we may ob ain a much be e uppe bound wi h esampling by chance. In his case, we need
signi ican ly less i e a ions o con e gence. Apa om his, esampling does no seem o
a ec he inal lowe bounds in mos o he cases, see Figu e 6. In ac , he de ia ion in
he numbe o nodes p ocessed o e he 5 epe i i e uns a ec s he esul s in some cases
as much as he choice whe he o use esampling, e.g., he inal lowe bounds epo ed o
model EOS2262. No ing ha he esampling heu is ic was in oduced o educe he a iances
o he educed lowe bounds, we in e ha he B&B algo i hm wi h g owing da ase s does
no su e om la ge a iances.
6 Conclusions and ou look
We in es iga e ou -o -sample es ima ion o enhancing he B&B algo i hm wi h g owing
da ase s p oposed in ou p e ious wo k [10]. In de ail, we combine he lowe bound calcula ed
in a B&B node based on a educed da ase wi h an ou -o -sample e alua ion ob aining he
combined lowe bound. Al hough he combined lowe bound is only a heu is ic lowe bound,
we expec i o be close o he lowe bound calcula ed based on he ull da ase . We use his
heu is ic lowe bound o ex ending he de e minis ic app oach p esen ed in [10]aswellas
o p uning which esul s in wo heu is ic app oaches, he so-called SSE and MSE heu is ic.
To de ec and quan i y po en ial mis akes made by he SSE and MSE heu is ic, we in oduce
a pos -p ocessing check o he inal lowe bound a e he B&B algo i hm e mina ed.
We compa ed he pe o mance o he di e en app oaches o he B&B algo i hm wi h
g owing da ase s and he s anda d B&B algo i hm based on 13 eal-wo ld applica ions om
bo h li e a u e and ou p e ious wo ks. Fo he es ima ion p oblems wi h exac da a, he de e -
minis ic app oach o he B&B algo i hm wi h g owing da ase s yields he as es un imes.
Mos o ou p oblems wi h e o -p one da a do no con e ge wi hin he gi en CPU ime
limi . Fo hese models, all app oaches, including he s anda d B&B algo i hm, ind simila
uppe bounds. The SSE heu is ics yields he bes , i.e., la ges , inal lowe bound o 70% o
he models wi h noisy da a and a simila alue as he s anda d B&B algo i hm o 20% o
hese models. In u n, he SSE heu is ic may in oduce an e o in o he p uning p ocedu e.
Howe e , ou esul s sugges ha bo h he SSE and he MSE heu is ic a e almos de e minis i-
cally con e ging owa ds he global solu ion, whe e he p oposed pos -p ocessing p ocedu e
allows o de ec and quan i y he excep ions om his assump ion.
Apa om his, we show in heo y ha we can likely dec ease he a iance o he lowe
bounds calcula ed based on educed da ase s when esampling he da ase . Howe e , he
ac ual nume ical pe o mance o he B&B algo i hm wi h g owing da ase s o he models o
ou case s udy is ha dly a ec ed by he use o he esampling heu is ic. Since we always i
a compa a i ely small numbe o unknown pa ame e s o a la ge da ase , we seem o ob ain
small a iances o he educed lowe bounds making esampling echniques like bagging less
123
638 Jou nal o Global Op imiza ion (2025) 92:615–642
ad an ageous, c . [20]and[15, Sec ion 8.2]. No e ha he good gene aliza ion pe o mance
o ou solu ion o model ainANN, see Online Resou ce 1, is ano he indica ion o ha ing
small a iances.
The compu a ional ad an age o he B&B algo i hm wi h g owing da ase s depends on
he choice o he educed da ase s. On he one hand, es ima ion esul s based on a educed
da ase may be dis o ed by o e i ing o e en iden i iabili y issues i he ull da ase is al eady
small compa ed o he numbe o unknown pa ame e s. We ha e shown ha applying ou -
o -sample es ima ion allows o igh ening he lowe bound calcula ed based on he educed
da ase . Howe e , i he da a educ ion is insigni ican in absolu e numbe s, he esul ing
compu a ional sa ings canno compensa e o he emaining gap o he ull lowe bound.
As a consequence, he B&B algo i hm wi h g owing da ase s is s ill ou pe o med by he
s anda d algo i hm in such cases wi h small da ase s. On he o he hand, we expec ha he
pe o mance o he B&B algo i hm wi h g owing da ase s p o i s om exploi ing knowledge
abou he da ase o he da a educ ion. Fo example, he educed lowe bound may be a be e
i o he ull lowe bound i he educed da ase s con ain a su icien amoun o measu emen s
wi h he la ges measu emen e o s. An ex ension allowing o use -gi en educed da ase s
me i s he e o e ca e ul a en ion.
We make he pa ame e es ima ion p oblems o ou case s udy openly accessible ia epos-
i o y GloPSE2. In u u e wo k, we aim a ex ending he case s udy wi h es ima ion p oblems
con aining da a-dependen cons ain s, e.g., i ing bina y luid sys ems wi h cons ain s on
he measu ed mole ac ions [55] and he op imiza ion o Gaussian p ocesses wi h cons ain s
on each o he da a poin s o he aining se [56]. Fo his, we aim a implemen ing a speci ic
ea men o da a-dependen cons ain s o allow o an e icien handling o educed da ase s
o hese models.
Fo all compu a ions, we used ou open-sou ce sol e MAiNGO which uses McCo mick
elaxa ions [43,44] o calcula e con ex unde es ima o s o he lowe bounding p oblem.
MAiNGO can he e o e e icien ly handle educed-space o mula ions [2,54], meaning ha
he size o he da ase does no a ec he numbe o op imiza ion a iables bu solely he com-
pu a ional e o o unc ion e alua ions. In con as o ha , many DGO sol e s like BARON
[57,58], ANTIGONE [59], and SCIP [60,61] use he auxilia y alues me hod (AVM) [6,
62–64] o ob aining con ex unde es ima o s. An implemen a ion o he B&B algo ihm wi h
g owing da ase s in hese AVM-based sol e s is o high in e es since he AVM me hod may
add an auxilia y op imiza ion a iable o each o he da a poin s and we he e o e expec
AVM-based sol e s o p o i e en s onge om he use o g owing da ase s.
Supplemen a y In o ma ion The online e sion con ains supplemen a y ma e ial a ailable a h ps://doi.
o g/10.1007/s10898-025-01514-4.
Acknowledgemen s This wo k was unded by he Deu sche Fo schungsgemeinscha (DFG, Ge man
Resea ch Founda ion) unde g an MI 1851/10-1 “Pa ame e es ima ion wi h (almos ) de e minis ic global
op imiza ion”. Simula ions we e pe o med wi h compu ing esou ces g an ed by RWTH Aachen Uni e si y
unde p ojec w h1563. Susanne Sass is g a e ul o he associa ion o he In e na ional Resea ch T ain-
ing G oup (DFG) IRTG-2379 “Hie a chical and Hyb id App oaches in Mode n In e se P oblems” unde
g an 333849990/GRK2379. We hank Dominik Bonga z o his suppo in he implemen a ion o he no el
app oaches wi hin MAiNGO. Mo eo e , we hank Ian H. Bell, Tan i Raha , Alexande Ech e meye , and J.
Raphael Seidenbe g o hei assis ance wi h se ing up he EOS, TSP, IHM, and EIS model, espec i ely. We
a e g a e ul o Ian H. Bell o p o iding he da a o he EOS model as well as o Niklas Thissen, S e anie
Khan, and Anna K. Mechle o p o iding expe imen al measu emen s o he EIS model. Mo eo e , we hank
he anonymous e iewe whose commen s helped us wi h imp o ing and cla i ying his a icle.
Au ho Con ibu ions Concep ualiza ion: Susanne Sass, Angelos Tsoukalas; Me hodology: Susanne Sass,
Alexande Mi sos, Nikolay I. Nikolo (pa icula ly o Sec ion 4), Angelos Tsoukalas; So wa e: Susanne Sass;
123
