Ki s , Pe e ; Füllne , Ch is ian
A icle — Published Ve sion
On he use o es ic ion o he igh -hand side in spa ial
b anch-and-bound algo i hms o ensu e e mina ion
Compu a ional Op imiza ion and Applica ions
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Ki s , Pe e ; Füllne , Ch is ian (2025) : On he use o es ic ion o he igh -hand
side in spa ial b anch-and-bound algo i hms o ensu e e mina ion, Compu a ional Op imiza ion
and Applica ions, ISSN 1573-2894, Sp inge US, New Yo k, NY, Vol. 90, Iss. 3, pp. 691-720,
h ps://doi.o g/10.1007/s10589-025-00652-5
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323335
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/
Compu a ional Op imiza ion and Applica ions (2025) 90:691–720
h ps://doi.o g/10.1007/s10589-025-00652-5
On he use o es ic ion o he igh -hand side in spa ial
b anch-and-bound algo i hms o ensu e e mina ion
Pe e Ki s 1
·Ch is ian Füllne 2
Recei ed: 12 Oc obe 2023 / Accep ed: 16 Janua y 2025 / Published online: 8 Feb ua y 2025
© The Au ho (s) 2025
Abs ac
Spa ial b anch-and-bound algo i hms o global minimiza ion o non-con ex p oblems
equi e bo h lowe and uppe bounding p ocedu es ha inally con e ge o a globally
op imal alue in o de o ensu e e mina ion o hese me hods. Whe eas con e gence
o lowe bounds is commonly gua an eed o s anda d app oaches in he li e a u e,
his does no always hold o uppe bounds. Fo his eason, di e en so-called con-
e gen uppe bounding p ocedu es a e p oposed. These me hods a e no always used
in p ac ice, possibly due o hei addi ional complexi y o possibly due o inc easing
un imes on a e age p oblems. Fo ha eason, in his a icle we p opose a e inemen
o classical b anch-and-bound me hods ha is simple o implemen and comes wi h
ma ginal o e head. We p o e ha his small imp o emen al eady leads o con e gen
uppe bounds, and hus show ha e mina ion o spa ial b anch-and-bound me hods
is ensu ed unde mild assump ions.
Keywo ds global op imiza ion ·b anch-and-bound ·uppe bounding p ocedu e ·
easible poin s · easibili y e i ica ion · es ic ion o he igh -hand side
Ma hema ics Subjec Classi ica ion 90C26
1 In oduc ion
In his a icle, we add ess he compu a ion o uppe bounds in spa ial b anch-and-bound
algo i hms in global op imiza ion, as well as he e mina ion o hese algo i hms. In
BPe e Ki s
pe e .ki s @wu .nl
Ch is ian Füllne
[email p o ec ed]
1Ope a ions Resea ch and Logis ics (ORL), Wageningen Uni e si y & Resea ch (WUR),
Wageningen, The Ne he lands
2Ins i u e o Ope a ions Resea ch, S ochas ic Op imiza ion, Ka ls uhe Ins i u e o Technology,
Ka ls uhe, Ge many
123
692 P. Ki s , C. Füllne
his con ex , we conside p oblems o he o m
P(B):min
x∈Rn (x)
s. .gi(x)≤0,i∈I,
x∈B
wi h a ini e se I. The box Bis de ined by B=x∈Rn|b≤x≤bwi h
b,b∈Rn,b<b, whe e inequali ies a e unde s ood componen -wise. We assume he
unc ions and gi o be con inuous, bu we do no equi e and gi o be con ex. Fo
ha eason, he easible se
M(B):= {x∈B|gi(x)≤0,i∈I}
does no need o be con ex ei he . In o al, p oblem P(B)is a non-con ex p oblem.
Th oughou his a icle he de ini ion M(X):= X∩M(B)will be con enien o
some box X⊂B.
Fo a p oblem o ype P(B)and some p ede ined op imali y ole ance ε >0a
ypical aim in global op imiza ion is o de e mine a so-called ε -op imal easible poin
x∗∈M(B), i.e. a easible poin x∗wi h
(x∗)≤ (x)+ε
o all x∈M(B). Clea ly, his immedia ely implies ∗≤ (x∗)≤ ∗+ε whe e
∗deno es he globally minimal alue o P(B). No e ha we impose ha d cons ain s
he e, which means ha app oxima ely easible poin s sa is ying he ε -op imali y
c i e ion a e no accep ed.
The mos common app oach o globally sol e p oblems o ype P(B)in his sense
is o apply spa ial b anch-and-bound algo i hms. In such me hods, he p oblem is
i e a i ely b anched in o subp oblems P(X)o he o m
P(X):min
x∈Rn (x)s. .x∈M(X)
wi h sub-boxes X⊂B. Then, o hose subp oblems lowe bounds a e cons uc ed
and, u he mo e, o e all lowe bounds a he globally minimal alue ∗o he o iginal
p oblem P(B)a e compu ed as a minimum o all hese lowe bounds. Whe e e
possible, boxes ha canno con ain globally op imal poin s a e excluded om he
sea ch space. In addi ion, uppe bounds a globally minimal alues a e compu ed and
he algo i hm e mina es i lowe and uppe bounds a e su icien ly close o each o he .
Whe eas con e gence is ypically ensu ed o lowe bounds, his is no gua an eed
o commonly used uppe bounding p ocedu es. Uppe bounds o ∗can be con-
s uc ed by explici ly e alua ing he objec i e unc ion a easible poin s o P(B)o
by applying local sol e s, which implici ly make use o such e alua ion. Howe e , as
he p oblem P(B)is non-con ex, inding a easible poin is al eady NP-ha d, which
makes i challenging o gene a e a sequence o easible poin s ha lead o imp o ed
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 693
uppe bounds. The e o e, mos esea ch on uppe bounding p ocedu es ocuses on
heu is ics which pe o m su icien ly well o many p ac ical applica ions, bu a e
no gua an eed o ensu e con e gence o uppe bounds in spa ial b anch-and-bound
me hods in gene al [10,11].
A popula s a egy is he a o emen ioned app oach o sol e he non-con ex p ob-
lem P(B), o some subp oblem P(X), locally [7]. Al hough his o en wo ks well in
p ac ice, in gene al his does no gua an ee su icien ly good uppe bounds o e -
mina ion o b anch-and-bound algo i hms. Since exac easibili y is ha d o ensu e,
ano he common concep is o accep so-called ε - easible poin s, i.e. poin s x∈B
wi h gi(x)≤ε ,i∈I, o some ole ance ε >0. Howe e , his concep is no
su icien o compu e alid uppe bounds o ∗ei he . This e en holds o ε close o
ze o, as discussed in de ail by Tuy [56] and Ki s e al. [30].
Hence, whe eas o mos lowe bounding p ocedu es in he li e a u e ce ain con-
e gence esul s a e a ailable, un o una ely, his does no hold o classical uppe
bounding p ocedu es. Since spa ial b anch-and-bound algo i hms ely on con e gen
alid uppe bounds in he e mina ion c i e ion, howe e , such con e gence gua an-
ees o he uppe bounds a e c ucial o ensu e e mina ion a e a ini e numbe o
i e a ions.
Resea ch in his di ec ion has been limi ed so a . As discussed abo e, compu ing
uppe bounds o ∗and iden i ying easible poin s a e closely ela ed. The e o e, he
wo k ha does exis is mos ly ocused on easibili y e i ica ion. Once e i ica ion is
success ul o some box X, alid uppe bounds a e ob ained by compu ing an uppe
bound o he objec i e unc ion o e X.In[13,28,29] se e al di e en easibil-
i y e i ica ion me hods a e p esen ed. They a e based on compu ing app oxima ely
easible poin s, e.g., by using con en ional nonlinea sol e s, and hen e i ying he
exis ence o easible poin s in speci ically cons uc ed boxes a ound such poin s using
in e al New on me hods. While hese me hods a e igo ous in he sense ha hey ule
ou alse posi i e easibili y e i ica ion, and hus do yield alid uppe bounds o ∗,
he e exis no p o en con e gence gua an ees. In ou emphasis on he con e gence o
he uppe bounding p ocedu e, ou wo k clea ly di e s om hese me hods.
Fo he case o pu ely inequali y-cons ained and box-cons ained p oblems, a con-
e gen uppe bounding p ocedu e is p esen ed in [30] based on pe u bing in easible
i e a es along Mangasa ian-F omo i z di ec ions. I is no s aigh o wa d o ex end
his app oach o equali y-cons ained p oblems, hough. In e e se, o he case o
pu ely equali y-cons ained and box-cons ained p oblems, a con e gen uppe bound-
ing p ocedu e is p esen ed in [19] based on a gene aliza ion o Mi anda’s Theo em
[37]. This me hod, howe e , does no allow o inequali y cons ain s in p oblems
P(B)and equi es he box cons ain s o be s ic ly sa is ied. An ex ension o p ob-
lems ha also include inequali y cons ain s is p esen ed in [18] based on u ilizing
app oxima ions o ac i e index se s o inequali ies.
Ano he common d awback o he exis ing uppe bounding p ocedu es wi h p o en
con e gence in he li e a u e is ha hey a e a he echnical and o en edious o imple-
men . On he con a y, some e y simple uppe bounding p ocedu es, such as s a ing
non-linea sol e s a di e en poin s du ing he solu ion p ocess, a e no gua an eed
o ensu e con e gence o spa ial b anch-and-bound algo i hms in gene al, bu p o ide
su icien ly good uppe bounds o achie e e mina ion o many p oblems in p ac ice.
123
694 P. Ki s , C. Füllne
In his a icle, we p opose a new uppe bounding p ocedu e ha exploi s he
s eng hs and o e comes he weaknesses o bo h ypes o app oaches. Tha is, ou
p oposed p ocedu e
•is simple o implemen ,
•is compu a ionally e icien in he sense ha he e is a mos li le o e head,
•can be combined easily wi h o he common me hods such as he local solu ion o
he p oblem a hand,
•bu is s ill p o en o p o ide su icien ly good uppe bounds in o de o e mina e
he algo i hm a e a ini e numbe o i e a ions unde mild assump ions.
No e ha , al hough some illus a i e compu a ional examples a e p o ided using a
simple implemen a ion as a p oo -o -concep , i is no ou aim o de elop an en i e new
sol e . Ins ead, we ocus on a new uppe bounding p ocedu e ha can be inco po a ed
in a wide a ie y o sol e s.
The main idea in his a icle is based on he concep o es ic ion o he igh -
hand side, which has ecen ly been p oposed in [40,41] in he con ex o semi-in ini e
p og amming o compu e easible poin s. Whe eas his echnique is used o (s anda d
as well as gene alized) semi-in ini e p og ams in [40,41], o ou bes knowledge i
has ne e been examined o s anda d non-con ex p oblems in global op imiza ion.
This a icle is s uc u ed as ollows. In Sec . 2we b ie ly e iew some basic con-
cep s om global op imiza ion and u he discuss di icul ies o non-con e gen uppe
bounding p ocedu es. In Sec .3we explain how he concep o es ic ion o he igh -
hand side om he li e a u e can be applied wi hin a spa ial b anch-and-bound me hod
o con inuous non-linea global op imiza ion. Based on his, in Sec .4we p o e ha
his leads o a con e gen algo i hm gi en some assump ions, which a e discussed in
Sec .5. In Sec .6we p o ide compu a ional esul s o some illus a i e es p oblems,
which highligh ha , while p o iding p o en con e gence gua an ees, he p oposed
me hod has li le compu a ional o e head. Finally, Sec .7concludes he pape wi h
some inal ema ks.
The no a ion in his a icle is s anda d. In pa icula , D deno es he ow ec o o
pa ial de i a i es o a unc ion and by diag(X)we deno e he diagonal leng h o a
box X.
2 P elimina ies and assump ions
In his sec ion we b ie ly e iew some impo an concep s om he li e a u e ha
a e needed o ou app oach. We s a wi h a small o e iew on spa ial b anch-and-
bound me hods in global op imiza ion whe e we ocus in pa icula on lowe bounding
p ocedu es. A gene al de ini ion o a con e gen lowe bound aken om [30]is
desc ibed in Sec .2.2. The concep o es ic ion o he igh -hand side, which is he
basis o ou new uppe bounding p ocedu e, is b ie ly explained in Sec .2.3.
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 695
2.1 Lowe bounding p ocedu es o spa ial b anch-and-bound me hods
Spa ial b anch-and-bound algo i hms o global op imiza ion we e i s p oposed by
Falk and Soland in [16]. Since hen, a ious enhancemen s ha e been de eloped, o
ins ance, b anch-and- educe [47,48], symbolic b anch-and-bound [51,52], b anch-
and-con ac [59] o b anch-and-cu [55]. In addi ion o hese pu ely scien i ic wo ks,
many s a e-o - he-a global op imiza ion sol e s a e based on implemen a ions o spa-
ial b anch-and-bound algo i hms, o example Ba on [49], Couenne [9], An igone
[39], LindoGlobal [33]o Scip [1,57]. Fo monog aphs co e ing he heo y on
global op imiza ion and, in pa icula , spa ial b anch-and-bound algo i hms we e e o
[17,23,34].
Typically, in spa ial b anch-and-bound algo i hms, lowe bounds o ∗a e ob ained
by special bounding p ocedu es. A well-known app oach is o compu e lowe bounds
by sol ing con ex elaxa ions o p oblems P(X) o op imali y. De e mining hese
elaxa ions, in u n, is based on compu ing as igh as possible con ex unde es ima o s
o he unc ions and gi,i∈I, con ained in P(B). Many di e en unde es ima o s
ha e been p oposed o speci ic classes o unc ions, among hem unde es ima o s
and en elopes o bilinea e ms [35], polynomials [32], non-con ex piecewise lin-
ea unc ions [24] and gene al lowe -semicon inuous unc ions [53,54]. Addi ionally,
gene ic con ex unde es ima o s can be cons uc ed o a bi a y non-con ex unc-
ions, as desc ibed in [2,21,36] and applied in he αBB algo i hm [3,4,7]. Since igh
unde es ima o s can only be de e mined explici ly o unc ions in low dimensions,
hese echniques a e usually combined wi h ac o iza ion and symbolic e o mula ion
app oaches [35,52]. Howe e , ecen ly he e has also been some p og ess on ob aining
igh elaxa ions o composi e unc ions di ec ly [22]. Mo eo e , con ex unde es-
ima o s can o en be conside ably s eng hened by bounds igh ening echniques
[9,44]. Di e en lowe bounding p ocedu es a e based on exploi ing duali y [14,
15], using piecewise linea app oxima ions [20,38,45,46], using Lipschi z cons an s
[43] o applying in e al a i hme ic [42] and ela ed concep s, such as cen e ed o ms
[8,31]. Fo se e al o hose lowe bounding p ocedu es i is p o en ha he de e mined
lowe bounds con e ge o ∗ o dec easing box sizes, as hey na u ally occu in spa ial
b anch-and-bound algo i hms.
2.2 Con e gence o lowe bounding p ocedu es
In his a icle we assume ha con e gen lowe bounding p ocedu es a e a ailable,
which is commonly ul illed o he a o emen ioned app oaches. Howe e , in o de
o keep he exposi ion as gene al as possible we b ie ly e iew some de ini ions om
[30], which will be con enien h oughou his a icle. Fu he mo e, his enables us o
p o e con e gence in a a he gene al manne wi hou es ic ing ou conside a ion o
a pa icula lowe bounding p ocedu e. We s a wi h some special classes o bounding
p ocedu es.
123
696 P. Ki s , C. Füllne
De ini ion 1 (Bounding p ocedu es, om [30])
•A unc ion om he se o all sub-boxes Xo B o Ris called M-dependen lowe
bounding p ocedu e o he objec i e unc ion o P(B),i (X)≤in x∈M(X) (x)
holds o all sub-boxes X⊆Band any choice o he unc ions ,gi,i∈I.
•A unc ion om he se o all sub-boxes Xo B o Ris called M-independen
lowe bounding p ocedu e o a unc ion, i i sa is ies (X)≤minx∈Xφ(x) o
all sub-boxes X⊆Band any choice o he unc ion φ:B→R.
•A lowe bounding p ocedu e is called mono one, i (X1)≥(X2)holds o all
boxes X1⊆X2⊆B.
In he ollowing, by φwe deno e an M-independen lowe bounding p ocedu e
applied o a speci ic unc ion φ,e.g. o gi,i∈I.
To make su e ha ou spa ial b anch-and-bound algo i hm con e ges, i is c ucial
ha all applied lowe bounding p ocedu es a e con e gen . To de ine he concep o
con e gen lowe bounding p ocedu es, we conside so-called exhaus i e sequences
o boxes and apply he bounding p ocedu es o hese sequences. A sequence o boxes
(Xk)k∈Nis called exhaus i e, i i is nes ed (Xk⊂Xk−1 o all k∈N), con ains no
emp y boxes (Xk=∅ o all k∈N) and sa is ies limk→∞ diag(Xk)=0. We e e o
[23] o mo e in o ma ion.
Fo commonly applied box di ision s a egies in global op imiza ion, e.g., di iding
a box along he midpoin o a longes edge, any exhaus i e sequence o boxes (Xk)k∈N
con e ges o a single poin ˜x, i.e. we ha e k∈NXk={˜x}. No e ha unde con inui y
o , his implies
lim
k→∞ min
x∈Xk
(x)= (˜x),
and in pa icula he limi exis s [30]. We can now in oduce he no ion o con e gen
bounding p ocedu es.
De ini ion 2 (Con e gen bounding p ocedu es, om [30])
•An M-independen lowe bounding p ocedu e φis called con e gen i i sa is ies
lim
k→∞φ(Xk)=lim
k→∞ min
x∈Xk
φ(x)
o any exhaus i e sequence o boxes (Xk)k∈Nand any unc ion φ:B→R.
•An M-dependen lowe bounding p ocedu e is called con e gen i i sa is ies
lim
k→∞(Xk)=lim
k→∞ min
x∈M(Xk) (x),
whe e limk→∞ minx∈M(Xk) (x)=+∞i ˜x/∈M(B), o any exhaus i e
sequence o boxes (Xk)k∈N.
2.3 Res ic ion o he igh -hand side
Con e gence o lowe bounds o many spa ial b anch-and-bound algo i hms in global
op imiza ion is ensu ed. Simila ly, i is s aigh o wa d o compu e a sequence o poin s
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 697
(xk)k∈N ha possesses a con e gen subsequence (xkν)ν∈Nsuch ha limν→∞ xkν=
x∗, whe e x∗deno es a globally minimal poin o he p oblem P(B). This ollows
immedia ely om he heo y on global op imiza ion (see, e.g., [23]) and is ensu ed
unde mild assump ions. Depending on he exac ype o algo i hm, o ins ance, he
midpoin s o he boxes ha a e cu en ly examined in he b anch-and-bound amewo k
possess a subsequence ha ul ills his equi emen , as we shall see in Sec . 4.In
con as , simila con e gence esul s o uppe bounds ha e no been es ablished in
gene al, as discussed in Sec .1.
In his a icle, we a e conce ned wi h he compu a ion o con e gen uppe bounds.
As al eady discussed be o e, compu ing alid uppe bounds is closely ela ed o inding
easible poin s because e alua ion o he objec i e unc ion a a easible poin imme-
dia ely yields an uppe bound o ∗. The e o e, ou new uppe bounding p ocedu e
is based on an e icien me hod o gene a e easible poin s o p oblem P(B).
As a key idea, ou app oach d aws on a echnique called es ic ion o he igh -
hand side, which is in oduced in [40,41] o (gene alized) semi-in ini e p oblems.
Using his echnique, we in oduce some ole ance in he cons ain s. Impo an ly,
in con as o he concep o ε - easibili y, he e i is used o u he es ic hem.
Hence, we equi e gi(x)≤−ε o all cons ain s gi. Clea ly, a poin sa is ying hese
condi ions is also easible o P(B).
Howe e , i ε is chosen oo la ge, he easible se can become emp y. Mo eo e ,
using a ixed alue o ε in gene al does no lead o a con e gen uppe bounding
p ocedu e. Fo ha eason, in o de o combine es ic ion o he igh -hand side wi h
a s anda d b anch-and-bound algo i hm in global op imiza ion, a c ucial componen o
ou p ocedu e is o d i e ε o ze o in an app op ia e way. As we shall see h oughou
his a icle, his can be achie ed such ha con e gence o uppe bounds is ensu ed,
and hus b anch-and-bound algo i hms a e p o en o e mina e.
We ema k ha in [40,41] in p esence o semi-in ini e cons ain s se e al nonlinea
p oblems ha e o be sol ed om sc a ch using di e en pa ame e se ings o ob ain
he desi ed uppe bounds. Howe e , in s anda d global op imiza ion, i.e. in he absence
o semi-in ini e cons ain s, i is no possible o sol e se e al op imiza ion p oblems
om sc a ch in o de o compu e he solu ion o a single op imiza ion p oblem, since
his is by a oo expensi e om a compu a ional poin o iew. The e o e, in his
a icle we p opose o ca e ully inco po a e he concep o es ic ion o he igh -hand
side in o a spa ial b anch-and-bound algo i hm, such ha we ge along wi hou his
equi emen . Essen ially, as we shall see, his inco po a ion esul s in a di e en box
selec ion ule in he b anch-and-bound algo i hm.
3 Inco po a ion o es ic ion o he igh -hand side in o spa ial
b anch-and-bound me hods
In his sec ion, we p opose a new uppe bounding p ocedu e which is con e gen .
I is based on inding easible poin s o P(B)wi h gua an ee and hen e alua ing
he objec i e unc ion in such poin s. To achie e his, he main idea is o exploi
con e gence o subsequences (xki)i∈N o a sligh ly al e ed p oblem.
123
698 P. Ki s , C. Füllne
Mo e p ecisely, gi en a pa ame e δ>0, we conside a p oblem o he o m
P(B,δ):min
x∈Rn (x)
s. .gi(x)≤−δ, i∈I,
x∈B.
We e e o hisas he es ic ed p oblem. The easible se o P(B,δ)is deno ed by
M(B,δ)and, mo eo e , le xdeno e a globally op imal poin o P(B,δ).
Acco ding o he explana ion a he beginning o his sec ion, gi en ha δis chosen
ca e ully such ha M(B,δ)s ill con ains a easible poin , by applying a b anch-and-
bound algo i hm a subsequence (xkν)ν∈Nis gene a ed ha sa is ies limν→∞ xkν=x.
This implies gi(x)≤−δand due o con inui y o he unc ions gi he e exis s someν
such ha o all ν≥νwe ha e gi(xkν)<0. Thus, as he box cons ain s a e ul illed
as well, xkνis easible o he o iginal p oblem P(B), and we ob ain an uppe bound
o ∗by e alua ing he objec i e unc ion in xkν. No e ha he main di e ence o
applying he same easoning o he o iginal p oblem P(B)is ha by es ic ion o he
igh -hand side we ensu e ha a easible poin sa is ying gi(x)≤0 is ound a e a
ini e numbe o s eps and no only in limi .
Simply applying a spa ial b anch-and-bound algo i hm o he p oblem P(B,δ)
ins ead o he o iginal p oblem P(B)is s ill no su icien o ou pu pose. In pa icula ,
in ha case he ob ained lowe bounds con e ge o he op imal alue o he es ic ed
p oblem which may di e om he alue o in e es ∗. This is clea ly no desi ed.
Mo eo e , simply using some ixed δ>0 is no su icien o ob ain a sequence o
uppe bounds ha con e ges o ∗as uppe bounds may emain oo la ge in such a
se ing.
Fo ha eason, ou main idea is o combine he solu ion o he o iginal p oblem
P(B)and he use o es ic ion o he igh -hand side in a easonable way. To his end,
we conside a s anda d spa ial b anch-and-bound algo i hm o sol ing P(B)and, in
addi ion, inco po a e he solu ion o mo e es ic ed p oblems o di e en alues o
δ. This is explained in he ollowing and s a ed o mally in Algo i hm 1.
As is common o spa ial b anch-and-bound algo i hms in global op imiza ion,
each i e a ion kis s a ed by choosing a uple (Xk,
k) om a lis Lo boxes s ill o
explo e, wi h ka lowe bound o he op imal alue ∗(Xk)on Xk(S ep 1). In e e y
second i e a ion, we ollow he selec ion ule o classical spa ial b anch-and-bound
algo i hms in global op imiza ion, which ypically means ha a box wi h he smalles
lowe bound is chosen, as i appea s mos p omising o con ain a globally minimal
poin x∗. We e e o his as a no mal selec ion s ep.
In he emaining i e a ions, we only choose boxes Xk ha may con ain easible
poin s o he es ic ed p oblems P(Xk,δ), hus aiming a he solu ion o p oblems
P(B,δ). This is checked by compu ing lowe bounds gi(Xk) o all gi,i∈I,onXk
using lowe bounding p ocedu es, such as in e al a i hme ic [42]. In case ha no such
box can be selec ed, we educe he alue δ>0 in o de o e ine he app oxima ion
ob ained by es ic ion o he igh -hand side. The same e inemen is applied i a
easible poin o P(B)is ound (see S ep 4) in o de o ensu e con e gence o he
uppe bounds o ∗. We e e o his as a es ic ed selec ion s ep.
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 705
P oo We conside an exhaus i e subsequence o boxes (Xkν)ν∈Nchosen in S ep 1
wi h
max
i∈Igi(Xkν)≤−δ o all ν∈N.
Fi s , we poin ou ha gi en he box selec ion ule in S ep 1 such an exhaus i e
sequence o boxes exis s, p o ided he possibly in ini e b anch-and-bound p ocedu e
co esponding o ε =0 does no e mina e. This ollows immedia ely using s anda d
a gumen s om global op imiza ion. In o de o see his, i is impo an o no e ha
he e a e a mos a ini e numbe o such boxes in he lis Lin e e y i e a ion and a
leas in e e y second i e a ion one mus choose such an elemen . Fo a mo e o mal
explana ion we e e o he p oo o Theo em IV.1. as well as o Co olla y IV.1. in
[23].
We now conside a poin x ha is con ained in all boxes Xkν o all ν∈N.F om he
de ini ion o M-independen lowe bounding p ocedu es as well as con inui y o he
de ining unc ions i ollows limν→∞ gi(Xkν)=gi(x) o all i∈I, and hence we
ha e maxi∈Igi(x)≤−δ. Again, using con inui y o he unc ions gi, o νsu icien ly
la ge we conclude ha all poin s in Xkνa e easible o P(B). The e o e, e e y poin
xkν ha is chosen om his box is easible as well, which concludes he p oo .
Re isi ing ou discussion on easibili y e i ica ion om Sec .3, we obse e ha
he p oo o Lemma 2allows o check easibili y o se s M(Xj
k,¯
δ) wi h 0 <¯
δ<δ
in S ep 4 o Algo i hm 1wi hou comp omising he esul .
Impo an ly, i can be shown ha he assump ions o Lemma 2a e always sa is ied
a e a ini e numbe o s eps.
Lemma 3 Assume ha Assump ion 1and Assump ion 2a e sa is ied, and ha he
possibly in ini e b anch-and-bound p ocedu e co esponding o ε =0in Algo i hm 1
does no e mina e. Le (δk)k∈Ndeno e he sequence o δob ained in Algo i hm 1. Then,
he e exis s some ¯
k∈Nsuch ha he i s condi ion om Lemma 2is sa is ied o all
k≥¯
k.
P oo Fi s , we no e ha due o he exis ence o a Sla e poin ˜x∈M(B)sa is ying
gi(˜x)<0 o all i∈I(Assump ion 2), o some su icien ly small ¯
δ>0, he
i s condi ion om Lemma 2is gua an eed o be sa is ied. By cons uc ion, i is also
sa is ied o all δ<¯
δ hen. We now p o e ha such a ¯
δis eached in Algo i hm 1a e
a ini e numbe o s eps.
We assume ha his does no hold and de i e a con adic ion. Hence, we assume
ha o all k∈N,weha egi(x)>−δk o all x∈M(B)and a leas one i∈I.
We now conside an exhaus i e subsequence o boxes (Xkν)ν∈Nob ained in Algo-
i hm 1, wi h ¯x∈Xkν o all ν∈N.Weha e ¯x∈M(B),asbyLemma4.1in[30],
o he wise he boxes (Xkν)ν∈Nwould no longe be selec ed and e ined in Algo i hm 1
a e a ini e numbe o s eps.
As he M-independen lowe bounding p ocedu e gi,i∈I,is con e gen acco d-
ing o Assump ion 1, o a leas one i∈Iwe ob ain limν→∞ gi(Xkν)=gi(¯x)>
−δkν. F om con inui y i ollows ha he e exis s some ¯ν∈Nsuch ha also
maxi∈Igi(Xkν)>−δkν o all ν≥¯ν.
123
706 P. Ki s , C. Füllne
Howe e , his means ha o all ν≥¯ν he lis ¯
Lis emp y and he pa ame e δkis
dec eased in S ep 1 o Algo i hm 1. The same a gumen can be epea ed, so we ob ain
limν→∞ δkν=0, and hus also limk→∞ δk=0. This is a con adic ion o ¯
δno being
eached a e a ini e numbe o s eps.
Rema k 1 Lemma 3in combina ion wi h Lemma 2implies ha a e ini ely many
s eps in Algo i hm 1a easible poin is iden i ied, and hus he global uppe bound
ukis upda ed. In pa icula , he e exis s a non-emp y subsequence (ukν)ν∈No uppe
bounds ela ed o i e a ions kν,ν ∈N,whe e he uppe bound is upda ed.
Rema k 2 F om Lemma 3i also ollows ha he e exis s some ˜
k∈Nsuch ha o
all k≥˜
kwe ha e M(B,δ˜
k)=∅. The e o e, by es ic ing o a subsequence (δkν)ν∈N
wi h kν≥˜
k o all ν∈N, all condi ions o Lemma 1a e sa is ied.
Wi h hese esul s, we a e now able o p o e con e gence o he sequence o uppe
bounds gene a ed by Algo i hm 1.
Theo em 4 Conside p oblem P(B)wi h non-emp y easible se M(B). Le Assump-
ions 1and 2hold. Then, i he possibly in ini e b anch-and-bound p ocedu e
co esponding o ε =0in Algo i hm 1does no e mina e, he sequence o uppe
bounds (uk)k∈Ncon e ges o he globally op imal alue ∗.
P oo The sequence (uk)k∈No uppe bounds gene a ed by Alo i hm 1is mono on-
ically dec easing and bounded om below by he op imal alue ∗o he o iginal
p oblem P(B). Thus, he sequence (uk)k∈Nis con e gen .
Howe e , i emains o be shown ha his sequence eally con e ges o he glob-
ally op imal alue ∗o P(B). To his end, we conside he non-emp y subsequence
(ukν)ν∈Nwhe e he e is an upda e o he uppe bound in i e a ion kν. Acco ding o
Lemma 3and Rema k 2such a sequence exis s. The alues ukνa e compu ed by
e alua ing he objec i e unc ion a easible poin s (xkν)ν∈N. Since all hese poin s a e
easible and since he easible se is compac , he e mus be a clus e poin xo his
sequence o poin s wi h x∈M(B).
Nex , we show ha xis, in ac , a globally op imal poin o p oblem P(B).To
achie e his, we assume ha his is no he case and de i e a con adic ion. Hence, i
xis easible and no op imal, hen we ha e (x)>
∗. Mo eo e , in iew o he box
selec ion ule o Algo i hm 1 he e mus be an exhaus i e sequence o boxes (Xμ)μ∈N
c ea ed by he algo i hm such ha x∈Xμ o all μ∈N. By Assump ion 1ou lowe
bounding p ocedu es a e con e gen , so we ha e
lim
μ→∞(Xμ)= (x)>
∗.
In pa icula , he e is some μsuch ha
(Xμ)>1
2 (x)+ ∗ o all μ≥μ. (1)
We now con inue o show ha his is ac ually no possible. To his end, we conside
an a bi a y i e a ion k oge he wi h he co esponding δk. A e a ini e numbe o
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 707
i e a ions we ei he ha e ha he lis Lis emp y o o he wise, as shown in Lemma 3,
ha a easible poin is ound. In bo h cases, in hese i e a ions k he alue δkis dec eased
by le ing δk+1=γδ
k(ei he in S ep 1 o in S ep 4). Induc i ely, o ha eason, we
ha e limk→∞ δk=0.
Addi ionally, by Lemma 3and Rema k 1, o su icien ly la ge k, all condi ions o
Lemma 1a e sa is ied. Hence, we conclude ha he sequence o op imal alues ∗
ko
he p oblems P(B,δ
k)con e ges o ∗. In pa icula , he e is some k∈Nsuch ha
∗
k≤1
2 (x)+ ∗ o all k≥k.
Then, howe e , o k≥k, nei he in i e a ions wi h an e en i e a ion numbe kno in
i e a ions wi h an odd i e a ion numbe kwe selec a box in S ep 1 o Algo i hm 1wi h
a lowe bound la ge han ∗
k≤1
2( (x)+ ∗), because he e a e always boxes wi h
a smalle lowe bound con ained in he lis Land L, espec i ely. In pa icula , ha
means ha inequali y (1) is iola ed o μsu icien ly la ge, such ha he sequence
(Xμ)μ∈Nis no c ea ed by he algo i hm a all. This con adic s ou assump ion and,
hence, he poin xmus be a globally op imal poin o he p oblem P(B).
Since ou uppe bounds a e c ea ed by e alua ing he objec i e unc ion a he poin s
(xkν)ν∈Nand since his sequence possesses he easible poin xas a clus e poin , he
asse ion now ollows om con inui y o he objec i e unc ion .
4.2 Con e gence o lowe bounds and op imal poin s
In his sec ion we es ablish con e gence o he sequence o he o e all lowe bounds k
o Algo i hm 1. Toge he wi h he con e gen uppe bounding p ocedu e his ensu es
ini e e mina ion o he b anch-and-bound algo i hm. Simila ly, one can es ablish a
con e gence esul o op imal poin s.
P oposi ion 5 Le M(B)=∅and le Assump ion 1hold. Then, i he possibly in i-
ni e b anch-and-bound p ocedu e o Algo i hm 1co esponding o ε =0does no
e mina e, o he o e all lowe bounds kin e e y i e a ion k he limi sa is ies
limk→∞ k= ∗whe e ∗deno es he op imal alue o P(B).
P oo We apply Theo em IV.3. om [23]. To his end, wo main p ope ies need o be
ensu ed, i.e. he bounding ope a ion needs o be bound imp o ing and consis en .The
o me means ha a e a ini e numbe o i e a ions a essela ion elemen needs o be
selec ed whe e he lowes bound is a ained. Clea ly, in Algo i hm 1in e e y second
i e a ion such a box is chosen.
The la e , i.e. consis ency o he bounding ope a ion, is a bi mo e in ol ed. In
iew o he box di ision ule in Algo i hm 1 o ou se ing his means ha o e e y
exhaus i e sequence o boxes (Xkν)ν∈Nc ea ed by he algo i hm we ha e
lim
ν→∞ukν−(Xkν)=0.
123
708 P. Ki s , C. Füllne
Clea ly, his exp ession canno be nega i e, since boxes Xwhe e he lowe bound (X)
is s ic ly la ge han he cu en uppe bound uka e a homed in S ep 6 o he algo i hm.
Mo eo e , o any h eshold τ>0 he di e ence ukν−(Xkν)canno emain la ge
han τ, as we show now. F om Theo em 4we know ha o he subsequence o uppe
bounds (ukν)ν∈Nwe ha e
lim
ν→∞ukν= ∗.
Fu he mo e, by mono onici y o he lowe bounding p ocedu e he sequence o lowe
bounds ((Xkν))ν∈Nis mono onically inc easing. As i is also bounded om abo e by
∗, i is con e gen . Le us now assume o a momen ha
lim
ν→∞(Xkν)= <
∗.
Then, he e exis s a easible poin x∈Xkν o all νwi h (x)= , see Lemma 4.1
in [30]. Howe e , ha means ha ∗could no be he op imal alue o he p oblem,
which con adic s ou assump ion. Hence, we ha e
0≤ukν−(Xkν)=ukν− ∗+ ∗−(Xkν)
and he asse ion ollows by sandwiching he exp ession in he middle.
In classical b anch-and-bound algo i hms in global op imiza ion one can easily
conside con e gen subsequences o poin s in boxes and usually hese subsequences
con e ge o globally op imal poin s o he o iginal p oblem. Due o he ac ha
no always boxes wi h he mos p omising lowe bounds a e selec ed in S ep 1, in
Algo i hm 1one could hink ha his migh no necessa ily be he case. Howe e , in
he nex esul we show ha his esul s ill holds unde his modi ica ion.
P oposi ion 6 Le M(B)=∅, le Assump ion 1and Assump ion 2hold and le us
assume ha he possibly in ini e b anch-and-bound p ocedu e o Algo i hm 1co e-
sponding o ε =0does no e mina e. Mo eo e , we conside a subsequence o boxes
(Xk)k∈Nchosen in S ep 1, and le xk∈Xk o all k ∈N. Then, (xk)k∈Npossesses a
clus e poin and any such clus e poin is a globally op imal poin o P(B).
P oo Due o xk∈B o all k∈Nand due o he ac ha Bis bounded, he sequence
(xk)k∈Npossesses a clus e poin . We now conside a con e gen subsequence (xkν)ν∈N
o (xk)k∈Nand pu x:= limν→∞ xkν.
Nex , we assume ha xis no a globally op imal poin and de i e a con adic ion
by dis inguishing wo di e en cases.
Case 1: x∈M(B)and (x)>
∗.Then, he e exis s an exhaus i e sequence o
boxes (Xkμ)μ∈Ngene a ed by he algo i hm wi h x∈Xkμ o all μ∈N. Acco ding
o Assump ion 1in S ep 3 an M-dependen lowe bounding p ocedu e is used, so we
ha e limμ→∞ (Xkμ)= (x). Using a gumen s om he p oo o Theo em 4we can
show ha a e a ini e numbe o i e a ions no box wi h (Xkμ)> 1
2( (x)+ ∗)is
selec ed and, hence, he exhaus i e sequence o boxes (Xkμ)μ∈Nis no c ea ed a all,
con adic ing he assump ion.
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 709
Case 2: x/∈M(B). Then, by Assump ion 1we ha e limμ→∞ (Xkμ)=+∞.
Again, his can be uled ou by using he same line o a gumen s as in he p oo o
Theo em 4.
Acco ding o Theo em 4, he o e all uppe bounds gene a ed by Algo i hm 1con-
e ge o he globally op imal alue i he assump ions o Theo em 4hold. Mo eo e ,
in iew o P oposi ion 5lowe bounds a e ensu ed o con e ge o he globally op i-
mal alue as well. The e o e, he b anch-and-bound me hod e mina es a e a ini e
numbe o i e a ions o ε >0. This immedia e consequence is s a ed o mally in he
ollowing esul .
Co olla y 7 Conside p oblem P(B)wi h non-emp y easible se M(B)and le a pos-
i i e e mina ion ole ance ε >0be gi en. Fu he assume ha Assump ion 1
and Assump ion 2hold. Then, i a con e gen lowe bounding p ocedu e is used,
Algo i hm 1 e mina es a e a ini e numbe o i e a ions.
P oo Since he lowe bounding p ocedu e is assumed o be con e gen we ha e om
P oposi ion 5 he limi limk→∞ k= ∗. Mo eo e , acco ding o Theo em 4we ha e
limk→∞ uk= ∗. Thus, we ob ain
lim
k→∞(uk− k)=lim
k→∞(uk− ∗)+( ∗− k)=0.
The e o e, a e a ini e numbe o i e a ions we ha e uk− k≤ε , and he asse ion
mus hold.
Le us ema k ha we ha e no add essed he case o an emp y easible se ye .
Typically, spa ial b anch-and-bound algo i hms in global op imiza ion a e able o ec-
ognize his by s opping wi h a ce i ica e o in easibili y. In his case, no box can be
selec ed in S ep 1 anymo e, since he lis Lbecomes emp y. In p inciple, his also holds
o Algo i hm 1. In o de o show his o mally, i is equi ed ha he lowe bounding
p ocedu e is no only con e gen , bu also ecognizes emp y boxes Xby e alua ing
o he ex ended eal alue (X)=+∞, p o ided ha he box Xis su icien ly small.
This is also ul illed o common lowe bounding p ocedu es (see, e.g., [3,4,7]).
5 Discussion o he assump ions
In he ollowing we b ie ly discuss ou main equi emen s ha need o be ul illed so
ha he concep o es ic ion o he igh -hand side in Algo i hm 1is su icien o ensu e
e mina ion o spa ial b anch-and-bound algo i hms. We s a wi h Assump ion 1 ha
is s aigh o wa d in his ega d, as i comp ises a common equi emen ega ding he
lowe bounding p ocedu e in global op imiza ion. In ac , lowe bounding p ocedu es
ha ul ill his a e widely used and ypically equi ed o basically all algo i hms in
ha domain (see, e.g., [23,30]).
In con as , Assump ion 2is a ely used in global op imiza ion, al hough e y
common in local op imiza ion. Mo eo e , unde he addi ional assump ion ha all
de ining unc ions a e di e en iable, i can e en be shown o be a s aigh o wa d
123
710 P. Ki s , C. Füllne
consequence o o he (weak) cons ain quali ica ions ha a e also common in non-
linea local op imiza ion. This holds, o ins ance, o he Mangasa ian-F omo i z
cons ain quali ica ion (MFCQ). In o de o o mula e his o p oblem P(B)we
explici ly ew i e he box cons ain s as addi ional cons ain s, see [30]:
hi(x)=bi−xi≤0i=1,...,n
hj(x)=xi−bi≤0j=n+1,...,2n.
Then, MFCQ is said o hold a a easible poin x∈M(B), i he e is a di ec ion
d∈Rnsuch ha
Dgi(x)d<0 o all ac i e indices, i.e. indices iwi h gi(x)=0
Dhj(x)d<0 o all ac i e indices, i.e. indices jwi h hj(x)=0.
Hence, i MFCQ holds a e e y globally op imal poin x∗, hen s anda d a gumen s
show ha o λ>0 su icien ly close o ze o we ha e
gi(x∗+λd)<0 o all i∈I
and hj(x∗+λd)<0 o all j=1,...,2n,
and hus a Sla e poin exis s in e e y neighbou hood N(x∗)a ound a poin x∗.In
pa icula , ha means ha Assump ion 2holds.
Hence, Assump ion 2is mild in he sense ha i is a di ec consequence o MFCQ,
which, in u n, is implied by he Linea Independence Cons ain Quali ica ion (LICQ).
This, howe e , is al eady mild in he sense ha i is p o en o gene ically hold e e y-
whe e in he easible se M(B)(see [27]). The la e means, in pa icula , ha in case
o i s iola ion i may be expec ed o hold a leas unde small pe u ba ions o he
p oblem da a. We b ie ly s a e he a o emen ioned conside a ion in he nex ema k.
Rema k 3 Le MFCQ o LICQ hold in e e y globally op imal poin o p oblem P(B).
Then, Assump ion 2is ul illed.
Fu he mo e, we poin ou ha in nonlinea local op imiza ion he assump ion o
LICQ e en in all locally minimal poin s is s anda d o con e gence p oo s. This
means, in pa icula , ha common uppe bounding p ocedu es in spa ial b anch-and-
bound me hods which ely on he local solu ion o NLP subp oblems implici ly use
his o ela ed assump ions as well and, hence, Assump ion 2is no es ic i e in his
ega d.
Finally, le us s ess ha e en in case ha Assump ion 2is iola ed, ou uppe
bounding p ocedu e may s ill p o ide alid uppe bounds, al hough i may happen
ha hese uppe bounds do no con e ge o he globally op imal alue ∗. As becomes
clea om he p oo o Lemma 1i is no possible, hough, ha a alue is compu ed
ha is s ic ly smalle han ∗, in con as o many o he app oaches such as accep ance
o ε - easible poin s.
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 711
Table 1 Tes p oblems and
dimensions name np
boo h 2 1
hs011 2 1
simpllpa 2 2
zece ic4 2 2
hs030 3 1
congigmz 3 5
hs044 4 6
hs268 5 5
ex3_1_2 5 6
hs098 6 4
hs113 10 8
6 Illus a i e compu a ional esul s
In his sec ion, we p o ide illus a i e compu a ional esul s o 11 small es p oblems
om he COCONUT benchma k lib a y [50], which a e summa ized in Table 1wi h
hei name, a iable dimension and numbe o inequali y cons ain s.
We should emphasize ha we do no p esen esul s o ex ensi e compu a ional es s
and la ge p oblem ins ances, and his is o he ollowing eason: The me i o es ic-
ion o he igh -hand side is ha i is a e y simple, bu powe ul concep ha allows
o ensu e de e minis ic and ini e con e gence o spa ial b anch-and-bound me hods
wi h ma ginal addi ional compu a ional e o . Fo mos o he implemen a ions o
such algo i hms, his is no gua an eed. Howe e , sol e s like ANTIGONE, BARON,
LINDOGlobal, Oc e ac o SCIP a e highly- uned and pe o m ex emely well
o many es p oblems. The e o e, we do no expec a simple implemen a ion using
es ic ion o he igh -hand side o be compu a ionally compe i i e wi h hese sol e s.
We a he ad oca e o inco po a e ou p oposed app oach in o exis ing me hods as an
addi ional way o ob ain uppe bounds and as a con e gence gua an ee. The esul s in
his sec ion a e included o illus a i e easons and as a p oo -o -concep .
6.1 Implemen a ion and es de ails
Ou implemen a ion is based on Algo i hm 1wi h only sligh modi ica ions. The
algo i hm is implemen ed in Py hon 3.7. Fo nume ic ope a ions Numpy and Scipy
a e used, and o in e al a i hme ic ope a ions we apply he In alPy package [6].
The lowe bounds a e compu ed using cen e ed o ms [31]. Mo eo e , as indica ed in
Sec .3, o each k, he alueδ(Xk)=maxi∈Igi(Xk)is compu ed once when he box
Xkis cons uc ed. We do no use bounds igh ening o simila accele a ion echniques.
In S ep 4 o Algo i hm 1, we use h ee di e en s a egies o choose candida e poin s
xj
k:
(a) Mid: He e, we choose xj
k:= mid(Xj
k), and hen check o easibili y.
123
712 P. Ki s , C. Füllne
(b) Mid + Loc: He e, in addi ion o (a), i mid(Xj
k)/∈M(Xj
k),we unIPOPT
[58] o ob ain a local solu ion o P(Xj
k)as an al e na i e candida e o xj
k.This
candida e is hen checked o easibili y.
(c) Mid + Loc-Res: Same app oach as (b), bu o kbeing e en, we sol e he
es ic ed p oblem P(Xj
k,δ
k)locally; see also ou discussion a he end o Sec . 3.
In each case, we do no allow o ε - easibili y when checking whe he xj
k∈
M(Xj
k).
To access IPOPT as a local sol e , we use he de aul unc ion minimize_ipop om
he Py hon package cyipop [5]. We use he de aul easibili y ole ance o 10−4,bu
do no p o ide in o ma ion on g adien s o Hessians manually.
Fo es ic ion o he igh -hand side, we choose δ0=1,γ =0.95 and pe o m
a es ic ed selec ion s ep in e e y κ- h i e a ion wi h κ∈{2,10,100}. We compa e
his o a b anch-and-bound me hod wi h only no mal selec ion s eps (no es ic ion).
No e ha o case Mid + Loc-Res we only conside κ∈{2,10}, since sol ing
he es ic ed p oblems locally only seems wo hwhile i es ic ed p oblems occu
su icien ly o en.
Fo he e mina ion c i e ion we se ε =10−3and addi ionally in oduce a ime
limi o 7,200s and an i e a ion limi o 10,000 i e a ions. The expe imen s a e execu ed
on a Windows machine wi h 2.5GHz In el Co e i5-6300U CPU and 12GB o RAM.
6.2 Discussion o esul s
The esul s a e summa ized in Tables 2. The columns compa e he esul s o di e en
alues o κ(wi h “-” indica ing ha no es ic ion is applied) and wi h di e en selec-
ion s a egies o xj
k. In each column, he o al numbe o i e a ions un il e mina ion
(i e m), he i s i e a ion in which a easible poin is ound and an uppe bound is
compu ed (i eas), he o al ime in seconds ( ime) and he solu ion s a us (s a us) a e
epo ed. I he p oblem is no sol ed o op imali y, we epo he emaining ela i e
op imali y gap UB−LB
|UB|as he s a us.
The esul s show ha he compu a ional pe o mance o using es ic ion o he
igh -hand side and o using only no mal selec ion s eps do no di e by much ( o
all s a egies, Mid,Mid + Loc and Mid + Loc-Res). On i s sigh , his seems
de imen al, as we do no see a clea pe o mance ad an age o ou p oposed me hod.
Howe e , he esul s highligh ha es ic ion o he igh -hand side p o ides a con-
e gence gua an ee a low compu a ional o e head, i.e. wi hou comp omising he
pe o mance o he spa ial b anch-and-bound me hod by much. Fo se e al p oblems,
he numbe o i e a ions and o al ime equi ed un il e mina ion a e a bi lowe i only
no mal selec ion s eps a e applied, bu his is no always he case.
In ac , we see ha in one case, o p oblem congigmz, es ic ion o he igh -hand
side wi h a su icien ly small κand xj
k=mid(Xj
k)leads o an ea ly iden i ica ion o a
easible poin , and hus compu a ion o a alid uppe bound o ∗. In con as , wi hou
es ic ion o he igh -hand side no ini e uppe bound can be compu ed wi hin he
gi en ime and i e a ion limi .
123
On he Use o Res ic ion o he Righ -hand Side in Spa ial B anch… 713
Table 2 Compu a ional esul s o Algo i hm 1 (pa 1)
Mid Mid +Loc Mid +Loc-Res
κ2 10 100 - 2 10 100 - 2 10
boo h
i 527 527 2 527 2 2 2 2 2 2
i 526 526 1 526 1 1 1 1 1 1
ime1821417322222
s a us* op op op op op op op op op op
hs011
i 1683 1673 1672 1672 1672 1672 1672 1672 1671 1672
i 1111111111
ime 57 56 52 56 673 613 627 599 1004 710
s a us* op op op op op op op op op op
simpllpa
i 106 92 89 89 106 92 89 89 100 92
i 1111111111
ime3 3 6 4 201918182720
s a us* op op op op op op op op op op
zece ic4
i 609 579 572 570 603 579 572 572 570 579
i 4444444424
ime 27 29 29 47 532 506 542 509 521 667
s a us* op op op op op op op op op op
hs030
i max max max max 400 400 400 400 414 400
i - - - - 111111
ime 334 292 386 345 354 349 356 338 494 413
s a us* - - - - op op op op op op
congigmz
i max max max max 852 839 728 920 594 511
i 964 1580 - -------
ime 1042 1017 1345 1049 max max max max max max
s a us* 0.02 0.21 - -------
hs044
i 398 283 268 268 398 283 269 269 384 283
i 47 47 47 47 47 47 47 47 47 47
ime 46 43 36 40 2194 1870 1614 1577 2195 1746
s a us* op op op op op op op op op op
123
714 P. Ki s , C. Füllne
Table 2 con inued
Mid Mid +Loc Mid +Loc-Res
κ2 10 100 - 2 10 100 - 2 10
hs268
i max max max max 902 839 738 912 862 780
i ----- - - - - -
ime 1536 1926 1914 1466 max max max max max max
s a us* ----- - - - - -
ex3_1_2
i max max max max 613 710 652 714 732 221
i 22222 2 2 2 4 2
ime 2793 2871 2619 2384 max max max max max max
s a us* 0.01 0.01 0.01 0.01 5.65 1.97 2.01 1.90 5.65 6.59
hs098
i max max max max 525 529 493 529 522 350
i ----299223210210420
ime 2102 2418 2323 2518 max max max max max max
s a us* - - - - 71.83 68.02 68.05 67.15 71.88 72.70
hs113
i max max 6725 max 79 73 62 82 69 74
i ----- - - - - -
ime 3456 4360 max 6995 max max max max max max
s a us* ----- - - - - -
*op :anε-op imal solu ion has been de e mined;
o he wise he emaining ela i e gap UB−LB
|UB|is epo ed (“-” i no UB has been ound)
Whe eas he addi ional usage o basic IPOPT does no lead o signi ican ly mo e
ins ances being sol ed (only hs030), and also slows down he solu ion p ocess, he
esul s illus a e ha local sol e s can be easily combined wi h es ic ion o he igh -
hand side and le e aged o ind easible poin s mo e quickly (see boo h, hs030, hs098).
Fo 2 ou o 12 es p oblems, e en wi h es ic ion o he igh -hand side, no alid
uppe bound is de e mined wi hin he gi en ime and i e a ion limi . Addi ionally, o
5 p oblems, ini e uppe bounds a e de e mined, bu no con e gence is achie ed in
he p ede ined i e a ion and ime limi , e en i o congigmz and ex3_1_2 a leas e y
small ela i e op imali y gaps a e eached.
This lack o pe o mance can be assumed o be explained by he e y simple b anch-
and-bound implemen a ion. In p ac ical applica ions, a b anch-and-bound me hod
using es ic ion o he igh -hand side could be uned by in oducing imp o ed lowe
bounding p ocedu es, bounds igh ening, addi ional s a egies o iden i y easible
poin s and se e al mo e accele a ion echniques. Also IPOPT could be uned, o
ins ance by p o iding de i a i e in o ma ion.
Finally, le us no e ha e en in cases whe e we only examine box midpoin s o
easibili y, o 6 ou o 12 es p oblems, he b anch-and-bound me hod e mina es
123
