Augmenting bi-objective branch and bound by scalarization-based information

Bauß, Julius; S iglmay , Michael
A icle — Published Ve sion
Augmen ing bi-objec i e b anch and bound by
scala iza ion-based in o ma ion
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: Bauß, Julius; S iglmay , Michael (2024) : Augmen ing bi-objec i e b anch and
bound by scala iza ion-based in o ma ion, 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. 85-121,
h ps://doi.o g/10.1007/s00186-024-00854-3
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/314978
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:85–121
h ps://doi.o g/10.1007/s00186-024-00854-3
ORIGINAL ARTICLE
Augmen ing bi-objec i e b anch and bound by
scala iza ion-based in o ma ion
Julius Bauß1·Michael S iglmay 1
Recei ed: 7 Feb ua y 2023 / Re ised: 10 Janua y 2024 / Accep ed: 10 Feb ua y 2024 /
Published online: 15 Ap il 2024
© The Au ho (s) 2024
Abs ac
While b anch and bound based algo i hms a e a s anda d app oach o sol e single-
objec i e (mixed-)in ege op imiza ion p oblems, mul i-objec i e b anch and bound
me hodsa eonly a elyappliedcompa ed o hep edominan objec i espaceme hods.
In his pape we p opose modi ica ions o inc ease he pe o mance o mul i-objec i e
b anch and bound algo i hms by u ilizing scala iza ion-based in o ma ion. We use he
hype olume indica o as a measu e o he gap be ween lowe and uppe bound se o
implemen a mul i-objec i e bes - i s s a egy. By adap i ely sol ing scala iza ions in
he oo node o in ege op imali y we imp o e bo h, uppe and lowe bound se . The
ob ained lowe bound can hen be in eg a ed in o he lowe bounds o all ac i e nodes,
while he de e mined solu ion is added o he uppe bound se . Nume ical expe imen s
show ha he numbe o in es iga ed nodes can be signi ican ly educed by up o 83%
and he o al compu a ion ime can be educed by up o 80%.
Keywo ds Mul i-objec i e op imiza ion ·Mul i-objec i e b anch and bound ·In ege
p og amming ·Hype olume indica o
1 In oduc ion
Many op imiza ion p oblems occu ing in eal-wo d applica ions include a con lic o
in e es s and goals, o seconda y objec i es, in a wo d, hey a e mul i-objec i e. Thus,
he e is (in gene al) no one solu ion ha op imizes all objec i es a once. Following he
Julius Bauß and Michael S iglmay ha e con ibu ed equally o his wo k
BJulius Bauß
[email p o ec ed]
Michael S iglmay
[email p o ec ed]
1School o Ma hema ics and Na u al Sciences, IMACM, Uni e si y o Wuppe al, Gaußs . 20, 42119
Wuppe al, Ge many
123
86 J. Bauß, M. S iglmay
a pos e io i pa adigm o decision making, we aim a de e mining he se o so-called
e icien solu ions o he images, he so-called non-domina ed poin s, which canno be
imp o ed in one objec i e wi hou de e io a ion in a leas one o he objec i e. Thus,
e icien solu ions a e easonable choices o decision make s.
As we a e conside ing speci ically bi-objec i e in ege linea p og ams and hei
solu ion wi h mul i-objec i e b anch and bound me hods, he ollowing li e a u e su -
ey will also ocus on his and closely ela ed opics. A comp ehensi e in oduc ion o
mul i-objec i e op imiza ion in gene al is gi en, e.g., in S eue (1986), Eh go (2005).
Solu ion app oaches o mul i-objec i e op imiza ion p oblems a e o en ca e-
go ized in: objec i e space and decision space me hods. Objec i e space me hods
scala ize he unde lying p oblem, i.e., i is eplaced by a se ies o single-objec i e
p oblems o de e mine successi ely he se o e icien solu ions. In he case o
mul i-objec i e in ege p og amming, hese scala ized p oblems can be sol ed wi h
comme cial in ege p og amming sol e s like CPLEX o Gu obi. The u iliza ion o
hese op imized, single-c i e ia sol e s a e a majo ad an age and one o he easons
why hose me hods a e p edominan in mul i-objec i e op imiza ion.
The e a e nume ous objec i e space me hods and a popula one is he ε-cons ain
me hod ha was in oduced o wo objec i es by Haimes e al. (1971). In e e y
i e a ion he i s objec i e is op imized wi h an upda ed cons ain o ensu e an
imp o emen ega ding he second objec i e. In Laumanns e al. (2006) an ex ension
o h ee and mo e objec i es is p esen ed. Many app oaches based on he ε-cons ain
me hod ha e been published in he las decades, o example Boland e al. (2017) and
Ki lik and Sayın (2014) combine he me hod wi h educ ion o dimension in he i-
espec i ely mul i-dimensional case.
The weigh ed sum scala iza ion is an objec i e space me hod based on he op imiza-
ion o a weigh ed sum o he objec i e unc ions using non-nega i e weigh s. No e ha
no all e icien solu ions can be de e mined as op imal solu ions o he weigh ed sum
scala iza ion using sui able weigh s (see, e.g. Aneja and Nai 1979). E icien solu ions
which can be ob ained by using weigh ed sum scala iza ion a e deno ed as suppo ed
e icicen and hei co esponding non-domina ed poin s a e loca ed on he bounda y
o he con ex hull o easible image poin s. Ex ensions o he weigh ed sum me hod
o he mul i-objec i e case a e p oposed in P zybylski e al. (2010a), Özpeyni ci and
Köksalan (2010), Bökle and Mu zel (2015), and P zybylski e al. (2019).
Ulungu and Teghem (1995) in oduced he so-called wo-phase me hod o bi-
objec i e p oblems. In he i s phase he ex eme suppo ed non-domina ed poin s a e
gene a ed wi h an algo i hm simila o he ini ial weigh ed sum app oach. In he second
phase he emaining non-domina ed poin s a e gene a ed by sea ching in iangles
de ined by wo consecu i e ex eme suppo ed non-domina ed poin s. In P zybylski
e al. (2008) and Tuy ens e al. (2000) p oblem speci ic algo i hms a e sugges ed o
he second phase, while in P zybylski e al. (2010b) a wo-phase me hod o p oblems
wi h mo e han wo objec i es is p oposed.
The augmen ed weigh ed Tchebyche me hod, i s p esen ed in S eue and Choo
(1983), minimizes he augmen ed weigh ed Tchebyche dis ance be ween a p e-
de ined e e ence poin and he se o easible image poin s. Däche e al. (2012)
sugges ed an adap i e choice o he augmen a ion e m o he bi-objec i e case.
123
Augmen ing bi-objec i e b anch and bound 87
In Boland e al. (2015a), Boland e al. (2015b) ( o he bi-objec i e case), Däche
and Klam o h (2014), and Klam o h e al. (2015) ( o he i- espec i ely mul i-
objec i e case) sea ch egion spli ing me hods a e p oposed. In his class o objec i e
space me hods, he sea ch egion (based on he al eady de e mined non-domina ed
poin s) is spli ed in o so-called sea ch zones on which scala iza ions a e sol ed ind-
penden ly.
Besides hei ad an ages, objec i e space me hods sha e a sho coming: In each
i e a ion a scala ized in ege p og am is sol ed om sc a ch. E en hough in some
objec i e space me hods s a ing solu ions can be ans e ed om p e ious i e a ions,
a la ge numbe o e y simila p oblems has o be sol ed. In o de o a oid his e o ,
decision space me hods, mainly he b anch and bound me hod, ha e been inc easingly
in es iga ed in he ecen yea s.
Klein and Hannan (1982) de eloped one o he i s b anch and bound algo i hms
o mul i-objec i e in egege p og ams wi h a ypical one ee s uc u e. In Kizil an and
Yucao˘glu (1983) a gene al b anch and bound amewo k o mul i-objec i e in ege
p og ams wi h bina y a iables is p esen ed. Ulungu and Teghem (1997) and Visée
e al. (1998) p oposed p oblem speci ic b anch and bound app oaches o bi-objec i e
Knapsack p oblems, whe e he la e app oach is in eg a ed in a wo-phase me hod.
Ma o as and Diakoulaki (1998) ex end he b anch and bound app oach o mul i-
objec i e mixed in ege p og ams. Pa s o he algo i hm a e e ined in Ma o as
and Diakoulaki (2005). In Vincen e al. (2013) his algo i hm is imp o ed and i is
shown ha he o iginal algo i hm is no co ec because he inal dominance es is
incomple e. In Belo i e al. (2012) a b anch and bound me hod is p esen ed ha can
handle bi-objec i e mixed in ege p og ams wi h con inious a iables in bo hobjec i e
unc ions.
The b anch and bound me hod p oposed in Sou d and Spanjaa d (2008) uses a se
o poin s as lowe bound ins ead o jus using a single poin . Fu he mo e hype planes
a e used o a hom nodes by dominance. In S idsen e al. (2014) his idea is con inued.
They use hype planes as a lowe bound se ha a e gene a ed by sol ing weigh ed
sum scala iza ions. Addi ionally hey p esen he so-called Pa e o b anching and he
slicing echnique. Wi h Pa e o b anching i is possible o di ide he objec i e space
o possibly igno e pa s o i in speci ic nodes. Slicing pa i ions he objec i e space
in equally la ge pa s and a espec i e slice can be a homed i i is domina ed by an
al eady ound in ege poin . In S idsen and Ande sen (2018) hisalgo i hmisimp o ed
and an app oach o pa allelize he algo i hm is p esen ed. Based on his, he idea Pa e o
b anching is u he in es iga ed in Pa agh and T icoi e (2019) and Gadegaa d e al.
(2019) o he bi-objec i e case and Fo ge e al. (2022) o he i-objec i e case.
A sel -con ained su ey o mul i-objec i e b anch and bound app oaches is gi en in
P zybylski and Gandibleux (2017).
In hispape wep esen abi-objec i eb anchandboundalgo i hm ha isaugmen ed
by scala iza ion-based in o ma ion. We make use o op imized single-objec i e sol e s
o scala in ege p og ams and in eg a e he esul ing in o ma ion in o he bi-objec i e
b anch and bound by imp o ing lowe and uppe bounds. Fu he mo e, we p opose a
new adap i e node selec ion s a egy, which elies on objec i e space in o ma ion. In
ou nume ical analysis we show he e ec i eness o hese imp o emen s by compa ing
123
88 J. Bauß, M. S iglmay
hem wi h a gene ic mul i-objec i e b anch and bound algo i hm, which we use as ou
baseline algo i hm.
The emainde o he a icle is o ganized as ollows: In Sec .2, we in oduce no a-
ions and de ini ions o mul i-objec i e op imiza ion. In Sec .3, we p esen a gene al
mul i-objec i e b anch and bound amewo k and i s key componen s. Fu he mo e,
wedesc ibeaspeci ic(howe e s anda d)mul i-objec i eb anchandboundalgo i hm,
which will be used as baseline implemen a ion in ou nume ical es s. In Sec .4,we
p esen augmen a ions o he mul i-objec i e b anch and bound, ha u ilize objec i e
space in o ma ion o imp o e he node selec ion as well as he compu a ion o uppe
and lowe bounds. We p o ide nume ical esul s in Sec .5and in Sec .6, we ou line
conclusions and ou looks o u he esea ch.
2 P elimina ies
We in oduce a gene al mul i-objec i e in ege linea p og am which can be w i en
in he o m:
min z1(x), . . . , zp(x)
s. .Ax ≤b
x≥0
x∈Zn.
(MOILP)
The eby, z(x):=(z1(x),...,zp(x))=C·x∈Rp(wi h p≥2) deno es he objec i e
unc ion ec o , wi h C∈Rp×n he ma ix o objec i e coe icien s. The se o easible
solu ions X:={x∈Zn:A≤b,x≥0}is a subse o he decision space Rn, while i s
image Y:={Cx:x∈X}is a subse o he objec i e space Rp.
We use he Pa e o concep o op imali y which elies on he componen wise o de .
Le y1,y2∈Rp, hen we de ine he co esponding dominance ela ions as ollows:
•y1y2, i.e., y1weakly domina es y2i y1
k≤y2
k o k=1,...,p,
•y1<y2, i.e., y1s ic ly domina es y2i y1
k<y2
k o k=1,...,p,
•y1≤y2, i.e., y1domina es y2i y1y2and y1= y2.
A easible solu ion x∈Xis called e icien i he e is no o he solu ion ˆx∈X
domina ing i , i.e., z(ˆx)≤z(x). A easible solu ion x∈Xis called weakly e icien
i he e is no ˆx∈Xsuch ha z(ˆx)<z(x). The se o e icien solu ions is deno ed
by XE.ByYN={z(x)∈Y:x∈XE}we deno e he se o he non-domina ed poin s
in he objec i e space. Mo eo e , o any se Q⊆Rpwe deno e by QN he se o i s
non-domina ed poin s (i.e., q∈QN⇐⇒ q∈Q:q≤q). Fo a comp ehensi e
in oduc ion o mul i-objec i e op imiza ion see, e.g., Eh go (2005).
In his a icle we conside a minimal comple e se as solu ion o a mul i-objec i e
op imiza ion p oblem. A minimal comple e se deno es he se o all non-domina ed
poin s YNand one e icien solu ion o each non-domina ed poin . See Se a ini (1987)
o a compa ison o solu ion concep s in mul i-objec i e op imiza ion.
123

Augmen ing bi-objec i e b anch and bound 89
A s anda d solu ion app oach in mul i-objec i e op imiza ion is he weigh ed sum
scala iza ion gi en in (WSλ).
min WSλ(x):=λz(x)=
p

i=1
λizi(x)
s. .x∈X
(WSλ)
Ob iously, e e y op imal solu ion o he weigh ed sum scala iza ion o λ∈
Rp
>:={λ∈Rp:λ>0}is e icien o (MOILP). Howe e , in gene al no all e i-
cien solu ions a e op imal solu ions o a co esponding weigh ed sum p oblem. An
e icien solu ion x∈XEis called suppo ed i he e is a weigh ing ec o λ∈Rp
>
such ha xis op imal o (WSλ) o λ=λ, o he wise xis unsuppo ed. No e ha
he non-domina ed poin s co esponding o suppo ed e icien solu ions a e loca ed
on he bounda y o he con ex hull o Y, while he unsuppo ed non-domina ed poin s
a e loca ed in i s ( ela i e) in e io .
As al eady men ioned in he in oduc ion he compu a ion o uppe and lowe
bounds on he non-domina ed se is a c ucial componen o any mul i-objec i e b anch
and bound algo i hm. The igh es componen wise uppe and lowe bounds o YNa e
he ideal poin yIand he Nadi poin yNgi en by:
yI
k=min
y∈Yykand yN
k=max
y∈YN
yk o k=1,...p.
Ob iously, yIyyNholds o e e y y∈YN, i.e., YNis con ained in he hype box
spanned by he co ne poin s yIand yN. Howe e , hese single poin bounds a e in
gene al e y weak excep o he degene a e case o yI=yN. This mo i a es o
conside bound se s ins ead o bounds consis ing o a single poin . We will ely on he
de ini ion o bound se s p oposed in Eh go and Gandibleux (2007). Le Rp
:={y∈
Rp:y0}, hen
•Alowe bound se L⊂Rp o YNis a
–Rp
-closed (i.e., he se L+Rp
is closed),
–Rp
-bounded (i.e., he e exis s a y∈Rpsuch ha L⊂y+Rp
)
– s able se (i.e., L⊂(L+Rp
)N),
such ha YN⊂(L+Rp
).
•An uppe bound se U⊂Rp o YNis a
–Rp
-closed,
–Rp
-bounded,
– s able se s,
such ha YN⊂cl(U+Rp
).
123
90 J. Bauß, M. S iglmay
The uppe bound and lowe bound ha we will de ine o ou b anch and bound
amewo k in Sec .3will sui hese de ini ions. We say a lowe bound Lis weakly
domina ed by an uppe bound Ui o all l∈L he e exis s an u∈Usuch ha ul.
In he ollowing we es ic ou sel es o bi-objec i e bina y linea op imiza ion
p oblems, i.e., p oblems wi h wo linea objec i e unc ions and a iables x∈{0,1}n:
min z(x)=z1(x), z2(x)
s. . Ax ≤b
x∈{0,1}n.
(BO01LP)
3 A gene ic mul i-objec i e b anch and bound amewo k
In his sec ion we p esen a gene ic mul i-objec i e b anch and bound amewo k,
which we speci y and augmen by using scala iza ion based in o ma ion in he hen
ollowing sec ions.
B anchandboundme hods ollowa “di ideand conque ” pa adigm. A p oblem ha
is oo ha d o be sol ed di ec ly, is di ided in o smalle and hus easie subp oblems.
The eby, subp oblems a e associa ed wi h nodes in a ee da a s uc u e acco ding o
hei descen , i.e., node iis a descendan node o node ji he easible se o he
subp obem associa ed wi h node iis a subse o he easible se o he subp oblem
associa ed wi h node j. The co esponding subp oblems o he child nodes a e c ea ed
by subdi iding he easible se o he co esponding (sub)p oblem o he pa en node.
S a ing wi h he oo node, o which he o iginal op imiza ion p oblem is associa ed,
he algo i hm selec s in each i e a ion one ac i e node and upda es i s lowe bound and
uppe bound. Then he ac i e node can be a homed i he co esponding subp oblem
is ei he sol ed o i ele an o he de e mina ion o a minimal comple e se . I we
canno p une we subdi ide he co esponding p oblem in o new subp oblems and
c ea e co esponding child nodes (b anching). Fo a mo e de ailed in oduc ion and
su ey o mul i-objec i e b anch and bound algo i hms see P zybylski and Gandibleux
(2017). A ecen su ey o single-objec i e b anch and bound amewo ks is gi en e.g.
in Mo ison e al. (2016). In he ollowing we speci y he lowe bound, uppe bound,
b anching ule and node selec ion we use in ou amewo k.
Lowe bound: Lowe bound se s a e o en de e mined by sol ing elaxa ions o he
espec i e subp oblem. Like in he single-objec i e case, he mos equen ly used
elaxa ions a e linea and con ex elaxa ions. In o de o sol e he linea elaxa ion
we a e using in ou amewo k, we apply Benson’s ou e app oxima ion algo i hm
(Benson 1998; Eh go e al. 2012). The algo i hm is ini ia ed wi h a lowe bound,
whichisimp o ed in e e y i e a ion by gene a ing cu s. Due o he ou e app oxima ion
s uc u e he algo i hm can be abo ed a any ime e u ning a alid lowe bound.
Al e na i ely, linea (o con ex) elaxa ionscan beob ainedusingadicho omicscheme
(see, o example, Aneja and Nai 1979; Özpeyni ci and Köksalan 2010; P zybylski
e al. 2010a). In he ollowing we deno e a lowe bound se Las con ex lowe bound
123
Augmen ing bi-objec i e b anch and bound 91
se o con ex lowe bound i L+R2
≥is a con ex se . No e ha he se Lis he eby
no necessa ily con ex.
Uppe bound: The uppe bound se , in he ollowing deno ed by U,iss o edin he o m
o a so-called incumben lis . Th oughou he un o he algo i hm, i con ains all in ege
easible solu ions and hei co esponding ou come ec o s ha a e no domina ed
by ano he easible solu ion ound so a . In e e y i e a ion he ex eme suppo ed
solu ions o he compu ed lowe bound se s a e checked o in ege easibili y. An
in ege easible solu ion ¯x∈Xis hen appended o he incumben lis , i he e is no
x∈Udomina ing ¯x,i.e.,C(x)≤C(¯x). I a new solu ion ¯xis added o he incumben
lis Uall solu ions x∈Uwhich a e domina ed by ¯x(C(¯x)≤C(x)) a e emo ed om
i , ha is
U{¯x}:= Ui ∃x∈U:C(x)≤C(¯x)
{¯x}∪{x∈U:C(¯x)C(x)}o he wise.
No e ha an upda e o he incumben lis equi es a subsequen upda e o he lis o
local uppe bounds. A de ailed desc ip ion o local uppe bounds, hei compu a ion
and upda e in an a bi a y numbe o c i e ia is gi en in Klam o h e al. (2015). In
his amewo k we s a wi h an emp y uppe bound se . Howe e , i is also possible
o ini ialize he incumben lis by heu is ic me hods, o by sol ing scala iza ions like,
e.g., in he wo-phase me hod (Ulungu and Teghem 1995; Visée e al. 1998).
Node selec ion: In e e y i e a ion o he algo i hm an unexplo ed node is selec ed
om he ee o subp oblems. This node is called ac i e node. The o de in which
he nodes o he ee a e conside ed has a signi ican impac on he numbe o c ea ed
nodes ha ha e o be explo ed and hus on he compu a ion ime.
Two ypeso s a egiesneed obedis inguished:s a ic s a egiesand dynamic s a e-
gies. The wo mos common examples o s a ic s a egies a e he dep h- i s s a egy
and he b ead h- i s s a egy. Mos mul i-objec i e b anch and bound algo i hms in
li e a u e ollow a dep h- i s s a egy. Thus, we use his s a egy o ou baseline
implemen a ion as well.
In con as o he single-objec i e case, dynamic node selec ion s a egies a e a ely
appliedin hemul i-objec i ecase. Dynamic node selec ion s a egiesa e, o example,
applied in Belo i e al. (2012), S idsen e al. (2014), Jesus e al. (2021).
Fa homing: In o de o a oid he o al enume a ion o all easible solu ions, nodes a e
a homed i he espec i e subp oblem is ei he sol ed o op imali y o does no con ain
solu ions which a e necessa y o de e mine a minimal comple e se . In pa icula , he e
a e h ee di e en si ua ions in which a node can be a homed:
i) Fa homing by in easibili y: I he LP- elaxa ion o a subp oblem is in easible hen
he co esponding subp oblem is in easible as well, since he easible se o he
subp oblem is a subse o he easible se o i s elaxa ion.
ii) Fa homing by op imali y: Simila o he single-objec i e case we can a hom a
node by op imali y i he lowe bound Lis equal o he uppe bound U.This
implies he subp oblem is sol ed o op imali y and he associa ed node mus no
be subdi eded u he . Howe e , his can happen in he mul i-objec i e case only
123
92 J. Bauß, M. S iglmay
i he lowe and uppe bound consis o he same single poin , namely he ideal
poin .
iii) Fa homing by dominance: A node can be a homed by dominance i all easible
solu ions o his subp oblem a e domina ed by poin s in he incumben lis . In o de
o check dominance o all easible ou come ec o s o a subp oblem we compa e
he lowe bound Lo he co esponding node o he cu en uppe bound U.I o
all l∈L he e is a poin in he incumben lis u∈Uwi h ul hen all easible
poin s in he sub ee a e domina ed by he cu en incumben lis . In o he wo ds,
i he e is no local uppe bound de ined by Uabo e he compu ed lowe bound he
node can be a homed by dominance.
B anching: As men ioned in he beginning o his sec ion, one o he key aspec s o
b anch and bound is i e a i e subdi ision in o smalle subp oblems. The eby subp ob-
lems a e associa ed wi h nodes in a ee, such ha he subp oblem associa ed o a child
node is ob ained by one b anching s ep. Since we conside bina y op imiza ion p ob-
lems (BO01LP), we can di ide a (sub)p oblem in o wo new subp oblems by ixing a
speci ic a iable o 0 and espec i ely o 1 in he o he subp oblem. This esul s in a
bina y b anch and bound ee.
The b anching ule de e mines which a iable is selec ed as b anching a iable
in each i e a ion. The eby, one dis inguishes be ween s a ic and dynamic s a egies.
S a ic s a egies de e mine an o de o he a iables in ad ance. In each i e a ion o
he algo i hm he nex a iable in his lis is used as b anching a iable. Wi h dynamic
s a egies he b anching a iable is selec ed by conside ing in o ma ion ob ained om
p e ious i e a ions, i.e., om he solu ion o (linea ) elaxa ions o (sub)p oblems.
The basic idea o s a ic s a egies o single-objec i e p oblems is o so he a i-
ables, beginning wi h he mos p omising acco ding o he objec i e unc ion alues
(see, e.g., Kelle e e al. 2004). Howe e , his canno be easily ex ended o he mul i-
objec i e case due o con lic ing objec i e unc ions. Ne e heless he e a e some
app oaches o ex end s a ic s a egies o he mul i-objec i e case (see o example
Ulungu and Teghem 1997; Bazgan e al. 2009).
In con as o mos o he published pape s which apply s a ic s a egies we use a
dynamic s a egy as p oposed in Belo i e al. (2012). By sol ing he linea elaxa ion
o a (sub)p oblem we ob ain he lowe bound se L. Fo all ex eme poin s o Lwe
check how o en a a iable is ac ional in he co esponding solu ions. As b anching
a iable we choose he one which is mos o en ac ional.
4 Using objec i e space in o ma ion in mul i-objec i e b anch and
bound
In his sec ion, we p opose modi ica ions which imp o e he compu a ional e i-
ciency o bi-objec i e b anch and bound algo i hms in wo c i ical aspec s. One o he
weaknesses o mul i-objec i e b anch and bound as compa ed o i s single-objec i e
coun e pa is he bounding p ocedu e. While any easible solu ion ¯x∈Xdomina es
w. . . one (linea ) objec i e a hal -space in decision space (i.e., {x∈Rn:cx≥c¯x}),
he se o easible solu ions which a e domina ed by a solu ion ¯xin p≥2 objec i e
123
Augmen ing bi-objec i e b anch and bound 99
Fig. 3 Example o upda ing he lowe and uppe bound wi h he usage o he augmen ed weigh ed Tcheby-
che scala iza ion
ha has no been ound ye in Fig.3a. By using he local ideal poin o z1and z2as
he e e ence poin s,Fig.3b illus a es how he non-domina ed poin z3is ound by
applying he augmen ed weigh ed Tchebyche scala iza ion. In Fig.3c, d he esul ing
imp o emen s o he lowe and uppe bound a e shown. Ob iously he lowe bound
is imp o ed beyond he con ex hull o YN. We now de ine ou second hyb id b anch
and bound app oach:
Hyb id B anch and Bound Algo i hm using Augmen ed Weigh ed Tchebyche
Scala iza ion
•Lowe bound: linea elaxa ion
•Uppe bound: incumben lis
•Node selec ion: node wi h he bigges o al/local hype olume gap
•B anching ule: mos ac ional
123

100 J. Bauß, M. S iglmay
•Adap i ely sol e weigh ed sum and augmen ed weigh ed Tchebyche scala iza-
ions in he oo node o in ege op imali y o imp o e lowe and uppe bounds by
objec i e space in o ma ion
In addi ion o he weigh ed sum scala iza ion, we use he augmen ed weigh ed
Tchebyche scala iza ion. Since wo adjacen non-domina ed poin s a e equi ed as
inpu o he augmen ed weigh ed Tchebyche scala iza ion, we canno ely on poin s
in heincumben lis , which a eonlynon-domina edso a .In ac ,weapply augmen ed
weigh ed Tchebyche IP scala iza ions only o boxes spanned by poin s ob ained as
op imal solu ions o he weigh ed sum scala iza ion. Thus, we do no ely on pa am-
e e s om he cu en ly ac i e node, bu sol e he augmen ed weigh ed Tchebyche
scala iza ion in he la ges a ea de ined by wo adjacen known non-domina ed poin s.
When using augmen ed weigh ed Tchebyche IP scala iza ions, he lowe bound
can become igh e han he con ex hull o he se o non-domina ed poin s, which
educes he a ea whe e new non-domina ed poin s can be ound. Addi ionally, we
can ind non-suppo ed non-domina ed poin s in ea ly s ages o he algo i hm. This
imp o es he uppe bound in he beginning esul ing in a highe chance o a homing a
node by dominance. Howe e , his also implies ha he lowe bound ge s non-con ex
in gene al, which makes he a homing es s signi ican ly ha de , and he lowe bound
imp o es only locally.
4.3 Algo i hmic con ol o IP scala iza ions
In he p e ious subsec ions we did no speci y when o sol e IP scala iza ions, which
implies a signi ican compu a ional cos i sel . Howe e , his migh be he mos c ucial
pa wi hin he p esen ed me hods. Ob iously, we aim a gaining as much in o ma ion
as possible by sol ing IP scala iza ions. Mo e objec i e space in o ma ion will lead
o igh e bounds ha educe he numbe o c ea ed nodes, due o a highe p obabili y
o a homing by dominance and smalle sea ch zones. Mo eo e , a educed numbe
o c ea ed nodes will educe he o al compu a ion ime. A he same ime, sol ing
o e ly many IP scala iza ions will ha e a nega i e impac on he compu a ion ime.
Fu he mo e, a a ce ain poin he lowe and uppe bound will no imp o e anymo e
when sol ing addi ional IP scala iza ions.
So, he e exis s a ade-o be ween he educ ion o he numbe o c ea ed subp ob-
lems and he dec ease o he compu a ion ime. The di icul y is o ind an app op ia e
condi ion o igge an IP scala iza ion. Ob iously, sol ing IP scala iza ions mo e e-
quen ly in he beginning o he b anch and bound algo i hm is e y p omising. The
ea lie he lowe and uppe bounds a e imp o ed he mo e nodes migh be a homed.
Mo eo e , sol ing he IP scala iza ion when he ac i e node has weak bounds will
lead o s onge imp o emen s han in la e s ages o he algo i hm. This is comple-
men ed by ou adap i e b anching s a egy, which ends o selec subp oblems wi h
weak lowe bounds i s .
The hyb id b anch and bound algo i hm using augmen ed weigh ed Tchebyche
scala iza ion en ails also ano he p oblem. The augmen ed weigh ed Tchebyche
scala iza ion imp o es he lowe bound jus locally. I we use his scala iza ion a
he beginning o he algo i hm ins ead o he weigh ed sum scala iza ion, his could
123
Augmen ing bi-objec i e b anch and bound 101
lead o an inc ease o c ea ed nodes. Once again, he in ui i e idea is o s a wi h
he weigh ed sum IP scala iza ion mo e equen ly in he beginning o he algo i hm.
This ensu es ha he lowe bound imp o es globally a ea ly s ages o he b anch and
bound. The augmen ed weigh ed Tchebyche scala iza ion should be used in la e
s ages o he algo i hm o ind non-suppo ed non-domina ed poin s and o imp o e
he lowe bound locally. The e iciency o his idea and o he app oaches will be shown
in he nex sec ion whe e we p esen nume ical es esul s.
5 Nume ical esul s
All algo i hms we e implemen ed in Julia 1.7.1 and he linea elaxa ions we e sol ed
wi h Bensol e 2.1 (Löhne and Weißing 2017). The nume ical es s we e execu ed on
a single co e o a 3.20 GHz In el®Co e™ i7-8700 CPU p ocesso in a compu e wi h
32 GB RAM, unning unde openSUSE linux Leap 15.3.
We p esen nume ical esul s o ou new app oaches and compa e hem o he
gene al b anch and bound amewo k p esen ed in Sec .3which we use as baseline
implemen a ion. We conside h ee di e en ypes o p oblems: mul idimensional
knapsack p oblems, assignmen p oblems and disc e e acili y loca ion p oblems. The
implemen a ion o he p oposed mul iobjec i e b anch and bound me hod and he
conside ed benchma k ins ances a e publicly a ailable (Bauß and S iglmay 2023).
Mul iple combina ions o pa ame e se ings a e used o sol e hese es p oblems.
The eby, we compa e he a e age numbe o explo ed nodes, he a e age numbe o
sol ed IPs and he a e age compu a ion ime o 20 ins ances pe p oblem size. The
di e en e alua ed app oaches a e
• he gene ic bi-objec i e B anch and Bouch (BB),
•bi-objec i e b anch and bound using he local (BS1) espec i ely global (BS2)
hype olume gap as node selec ion c i e ion,
•hyb id b anch and bound including weigh ed sum IP scala iza ions (WS), and
•di e en combina ions o he hyb id b anch and bound algo i hm using weigh ed
sum IP scala iza ion (M1.α.β) and hyb id b anch and bound algo i hm using
weigh ed sum and augmen ed weigh ed Tchebyche IP scala iza ion (M2.α.β.γ).
The pa ame e α∈{1,2,3}con ols how o en IP scala iza ions a e applied. Since
he numbe o IP scala iza ions is chosen depending on he p oblem class, he meaning
o he di e en alues o αis desc ibed in de ail in he co esponding subsec ions.
In gene al, howe e , he la ge he pa ame e αis chosen, he ewe IP scala iza ions
a e sol ed. Wi h βwe dis inguish be ween he local (β=1) and he global (β=2)
hype olume gap s a egy. In he hyb id b anch and bound algo i hm using augmen ed
weigh ed Tchebyche scala iza ion we also dis inguish be ween in eg a ing he objec-
i e space in o ma ion o he augmen ed weigh ed Tchebyche in o he lowe bound
(γ=1) o no (γ=2).
No e ha he pa ame e alues ha e been chosen based on p elimina y esul s
ob ained om a di e en se s o ins ances, whe e hey shown o p o ide good esul s.
Thus, he pa ame e alues a e chosen depending on he p oblem class bu a e no
123
102 J. Bauß, M. S iglmay
op imized w. . . he speci ic es ins ances. Hence, we a oid an ins ance depending
i ing o he pa ame e s o he da a se .
5.1 Bi-objec i e mul idimensional knapsack p oblems
We conside bi-objec i e, mul idimensional knapsack p oblems wi h one, wo and
h ee linea es ic ions (i.e. m=1,2,3). Fo e e y p oblem size we andomly gen-
e a e 20 ins ances o he o m
max
n

i=1
ck
ixik=1,2
s. .
n

i=1
wixi≤b
n

i=1
ij xi≤djj=1,...,m−1
x∈{0,1}n
wi h ck
i∈[50,100],wi∈[5,15],b=5n,
ij ∈[5,15]and dj= n
2wi h
∈[5,15]. Depending on he pa ame e αwe speci y when and how o en IP scala -
iza ions a e sol ed. In M1.1.βand WS we apply he weigh ed sum scala iza ion e e y
10- h i e a ions. In M1.2.βwe apply i e e y 10- h i e a ion bu only wi hin he i s
n2i e a ions. In M1.3.βwe apply he weigh ed sum scala iza ion e e y 10- h i e a ion
wi hin he i s n2/3 i e a ions, e e y n- h i e a ion wi hin he nex n2/3 i e a ions
and e e y 2n- h i e a ion wi hin he hi d n2/3 i e a ions. In M2.1.β.γwe apply he
weigh ed sum scala iza ion e e y 10- h i e a ion and e e y 50- h i e a ion he aug-
men ed weigh ed Tchebyche scala iza ion is used ins ead. In M2.2.β.γwe ope a e
likeinM1.2.βbu a e he i s n2i e a ionsweapply heaugmen edweigh edTcheby-
che scala iza ion e e y 50- h i e a ion. In M2.3.β.γwe ope a e like in M1.3.βbu
a e he i s n2i e a ions we apply he augmen ed weigh ed Tchebyche scala iza ion
e e y 50- h i e a ion. I a scala iza ion canno be applied o he same IP scala iza ion
has al eady been sol ed be o e, no IP scala iza ion is sol ed in ha i e a ion.
Fi s o all, we no ice ha ou b anching s a egiesha ea huge impac on he numbe
o explo ed nodes and he compu a ion ime in knapsack p oblems. We obse e ha in
gene al he local hype olume gap s a egy wo ks be e han he global hype olume
gap s a egy. Wi h he local s a egy we can educe he numbe o explo ed nodes by up
o 76% (Table 1c, b) and he compu a ion ime by up o 73% (Table 1c). Al hough he
local s a egy wo ks be e he global hype olume gap s a egy has also a signi ican
impac . The numbe o explo ed nodes can be educed by up o 58% (Table 2c) and he
compu a ion ime by up o 52% (Table 2c). The numbe o nodes and he compu a ion
ime is educed in all ou app oaches and we can no ice ha combina ions wi h he
local hype olume s a egy wo k be e .
By limi ing he numbe o sol ed weigh ed sum IPs (i.e. in M1.2.β, M1.3.β,
M2.2.β.γand M2.3.β.γ) we no ice wo consequences. The numbe o nodes inc eases
while he numbe o sol ed IPs dec eases. Al hough he numbe o nodes (and hus
123
Augmen ing bi-objec i e b anch and bound 103
Table 1 Nume ical esul s o he
bi-objec i e, mul idimensional
knapsack p oblems
(a) Knapsack p oblem, m=1,n=50
Ve sion Nodes Time (s) Sol ed IPs
BB 27916.3 18.153 0.0
BS1 11788.1 8.339 0.0
WS 14270.7 10.507 33.75
M1.1.1 10789.7 8.452 26.4
M1.2.1 10793.5 8.188 21.2
M1.3.1 10795.7 8.116 17.95
M2.1.1.1 9888.5 10.873 48.7
M2.2.1.1 10140.3 9.437 32.65
M2.3.1.1 10521.0 8.774 25.65
M2.1.1.2 9840.1 8.396 45.55
M2.2.1.2 10130.6 8.422 32.35
M2.3.1.2 10401.8 8.288 26.25
BS2 16739.8 11.397 0.0
M1.1.2 11026.3 8.861 26.1
M1.2.2 11024.5 8.860 19.85
M1.3.2 11047.4 8.645 16.05
M2.1.2.1 10071.8 10.907 45.85
M2.2.2.1 10421.4 9.587 31.8
M2.3.2.1 10583.2 9.448 24.45
M2.1.2.2 9994.1 8.940 46.65
M2.2.2.2 10413.4 8.820 32.55
M2.3.2.2 10568.9 8.727 25.15
(b) Knapsack p oblem, m=1,n=80
Ve sion Nodes Time (s) Sol ed IPs
BB 153938.9 186.330 0.0
BS1 36392.0 50.952 0.0
WS 58825.7 79.545 54.0
M1.1.1 34337.7 50.431 41.65
M1.2.1 34333.9 50.312 33.1
M1.3.1 34307.1 50.505 26.35
M2.1.1.1 31643.7 81.625 100.2
M2.2.1.1 32708.9 68.939 76.2
M2.3.1.1 32986.3 69.848 63.6
M2.1.1.2 31274.5 46.721 102.85
M2.2.1.2 32795.7 48.576 76.3
M2.3.1.2 33025.8 48.358 63.4
123
104 J. Bauß, M. S iglmay
Table 1 con inued (b) Knapsack p oblem, m=1,n=80
Ve sion Nodes Time (s) Sol ed IPs
BS2 90976.0 116.847 0.0
M1.1.2 39745.1 59.321 45.25
M1.2.2 40083.2 59.350 31.2
M1.3.2 39918.1 58.999 24.5
M2.1.2.1 31905.8 80.505 99.7
M2.2.2.1 34496.9 79.444 84.0
M2.3.2.1 34571.7 72.955 65.15
M2.1.2.2 32074.9 48.510 104.85
M2.2.2.2 34169.8 51.464 87.15
M2.3.2.2 34943.3 51.887 63.1
(c) Knapsack p oblem, m=1,n=100
Ve sion Nodes Time (s) Sol ed IPs
BB 297345.3 484.676 0.0
BS1 68920.5 128.967 0.0
WS 128080.8 224.587 66.95
M1.1.1 67369.1 128.665 54.1
M1.2.1 67370.1 128.924 39.95
M1.3.1 67353.3 128.993 32.9
M2.1.1.1 58214.2 198.683 156.85
M2.2.1.1 61533.1 179.516 123.0
M2.3.1.1 62127.3 177.621 104.55
M2.1.1.2 58151.3 112.575 158.1
M2.2.1.2 61490.6 118.600 120.1
M2.3.1.2 61762.6 118.306 108.65
BS2 187306.9 318.524 0.0
M1.1.2 73766.2 144.684 54.75
M1.2.2 74065.4 144.677 37.9
M1.3.2 73865.0 144.306 31.0
M2.1.2.1 59512.7 200.754 158.05
M2.2.2.1 64489.2 192.211 127.0
M2.3.2.1 64330.5 187.803 114.65
M2.1.2.2 60470.8 118.479 157.75
M2.2.2.2 64943.8 127.428 123.5
M2.3.2.2 64711.1 126.525 113.5
(d) Knapsack p oblem, m=2,n=50
Ve sion Nodes Time (s) Sol ed IPs
BB 32655.6 25.8684 0.0
BS1 10982.3 9.6578 0.0
123

Augmen ing bi-objec i e b anch and bound 105
Table 1 con inued (d) Knapsack p oblem, m=2,n=50
Ve sion Nodes Time (s) Sol ed IPs
WS 14180.9 13.1749 33.25
M1.1.1 9784.7 9.5159 26.6
M1.2.1 9782.5 9.2684 19.65
M1.3.1 9791.1 9.1580 14.85
M2.1.1.1 8900.7 12.6639 47.75
M2.2.1.1 9407.5 11.5112 34.5
M2.3.1.1 9507.5 11.0256 24.8
M2.1.1.2 8892.9 9.2702 47.0
M2.2.1.2 9370.2 9.2053 33.05
M2.3.1.2 9484.3 9.1161 24.75
BS2 15639.2 13.1246 0.0
M1.1.2 10665.3 10.8423 28.5
M1.2.2 10671.3 10.5141 19.4
M1.3.2 10854.2 10.5765 15.7
M2.1.2.1 9045.3 12.8916 48.9
M2.2.2.1 9629.7 12.1913 34.9
M2.3.2.1 9814.7 11.6068 28.1
M2.1.2.2 9030.0 9.5854 48.2
M2.2.2.2 9608.5 9.7621 36.05
M2.3.2.2 9787.6 9.6722 28.35
he numbe o conside ed subp oblems) is inc easing, he o al compu a ion ime
dec eases. This implies ha he educed compu a ion ime o sol e IP scala iza ions
compensa es he inc ease o nodes, which esul s in a ade-o be ween he num-
be o explo ed nodes and he compu a ion ime. Ano he in e es ing aspec can be
obse ed in M2.α.β.1 and M2.α.β.2. The compu a ion ime can be educed i we do
no in eg a e he augmen ed weigh ed Tchebyche objec i e le el se in o he lowe
bound. This can be explained by he ac ha he lowe bound imp o emen s o aug-
men ed weigh ed Tchebyche a e only local and do no compensa e he compu a ion
ime needed o in eg a e he in o ma ion. The in ui i e assump ion ha he numbe o
explo ed nodes will hen ise signi ican ly is alse. So, bo h ou b anching s a egies
wo k be e , i we do no conside he local upda es o he lowe bound.
We can each a educ ion o he explo ed nodes by up o 83% (Table 2b) and a educ-
ion o he compu a ion ime by up o 80% (Table 2b) in he bes case. The s a egies
M2.1.1.1 and M2.1.1.2 seem o wo k bes o knapsack p oblems. In mos cases hese
wo s a egies ha e he la ges impac on he numbe o explo ed nodes. Ne e heless,
M2.1.1.2 achie es o all ins ance sizes he bes compu a ion imes, since compu a-
ion ime is sa ed by no in eg a ing he augmen ed weigh ed Tchebyche objec i e
space in o ma ion in o he lowe bound. No e ha wi h ising numbe s o a iables
123
106 J. Bauß, M. S iglmay
Table 2 Nume ical esul s o he
bi-objec i e, mul idimensional
knapsack p oblems
(a) Knapsack p oblem, m=2,n=80
Ve sion Nodes Time (s) Sol ed IPs
BB 159911.4 287.925 0.0
BS1 41092.0 88.121 0.0
WS 63215.0 130.338 55.0
M1.1.1 37799.1 82.654 43.9
M1.2.1 37835.8 82.544 30.55
M1.3.1 37811.3 82.369 24.75
M2.1.1.1 31615.0 115.164 102.55
M2.2.1.1 34772.5 102.965 72.5
M2.3.1.1 35127.1 100.706 60.6
M2.1.1.2 31590.2 69.290 104.7
M2.2.1.2 34977.7 77.063 72.45
M2.3.1.2 35170.3 77.279 61.3
BS2 115223.3 224.926 0.0
M1.1.2 43581.8 97.039 47.8
M1.2.2 43744.8 97.874 29.1
M1.3.2 45481.1 102.689 23.45
M2.1.2.1 32388.8 116.173 106.25
M2.2.2.1 36453.2 120.161 78.3
M2.3.2.1 35942.7 116.972 69.05
M2.1.2.2 33264.8 74.207 104.75
M2.2.2.2 36578.1 81.915 77.2
M2.3.2.2 35505.1 77.971 69.55
(b) Knapsack p oblem, m=2,n=100
Ve sion Nodes Time (s) Sol ed IPs
BB 428526.3 1074.21 0.0
BS1 100962.6 326.98 0.0
WS 166108.1 464.71 67.25
M1.1.1 98831.5 323.54 54.8
M1.2.1 99313.5 325.32 38.95
M1.3.1 98770.6 322.65 32.6
M2.1.1.1 69951.9 402.48 149.35
M2.2.1.1 73433.8 379.33 119.6
M2.3.1.1 73424.7 371.63 102.95
M2.1.1.2 70172.3 212.40 153.15
M2.2.1.2 72824.8 219.73 121.55
M2.3.1.2 73651.5 221.96 107.5
123
Augmen ing bi-objec i e b anch and bound 107
Table 2 con inued (b) Knapsack p oblem, m=2,n=100
Ve sion Nodes Time (s) Sol ed IPs
BS2 271110.8 720.46 0.0
M1.1.2 113605.9 381.46 57.45
M1.2.2 117188.3 394.57 36.45
M1.3.2 113665.3 378.63 29.85
M2.1.2.1 70603.0 404.28 150.8
M2.2.2.1 77836.0 400.18 121.4
M2.3.2.1 76818.2 399.89 110.8
M2.1.2.2 72316.9 219.91 148.4
M2.2.2.2 78135.2 240.57 121.3
M2.3.2.2 77073.0 235.49 112.45
(c) Knapsack p oblem, m=3,n=50
Ve sion Nodes Time (s) Sol ed IPs
BB 54430.4 51.5026 0.0
BS1 15260.1 17.9276 0.0
WS 18112.9 20.5208 36.2
M1.1.1 13522.4 16.8431 28.8
M1.2.1 13530.7 16.4735 19.0
M1.3.1 13576.5 16.4442 14.95
M2.1.1.1 12345.3 22.1289 51.15
M2.2.1.1 12973.5 19.7592 34.5
M2.3.1.1 13014.0 19.6348 28.8
M2.1.1.2 12241.1 16.1190 53.55
M2.2.1.2 12934.3 16.2933 35.15
M2.3.1.2 12908.3 16.1009 30.35
BS2 22597.3 24.5736 0.0
M1.1.2 14645.7 18.6425 29.55
M1.2.2 14573.2 18.0521 16.75
M1.3.2 14597.0 17.9793 14.5
M2.1.2.1 12617.9 22.3518 54.65
M2.2.2.1 13324.9 20.7655 33.4
M2.3.2.1 13252.3 20.4366 30.55
M2.1.2.2 12682.4 16.8670 56.65
M2.2.2.2 13180.2 16.7601 33.6
M2.3.2.2 13274.4 16.8497 32.15
(d) Knapsack p oblem, m=3,n=80
Ve sion Nodes Time (s) Sol ed IPs
BB 263971.6 724.999 0.0
BS1 81609.9 287.899 0.0
123
108 J. Bauß, M. S iglmay
Table 2 con inued (d) Knapsack p oblem, m=3,n=80
Ve sion Nodes Time (s) Sol ed IPs
WS 121360.8 376.247 56.4
M1.1.1 80406.5 282.897 47.35
M1.2.1 79971.5 279.885 32.2
M1.3.1 80089.6 279.686 26.55
M2.1.1.1 54187.1 340.389 115.7
M2.2.1.1 55915.9 328.411 85.45
M2.3.1.1 58486.8 330.347 66.9
M2.1.1.2 53396.0 164.755 116.0
M2.2.1.2 56572.6 174.131 86.25
M2.3.1.2 57452.9 176.657 67.85
BS2 140681.4 390.578 0.0
M1.1.2 92175.8 334.414 50.45
M1.2.2 96339.3 350.148 29.05
M1.3.2 96099.5 348.915 24.0
M2.1.2.1 54119.5 349.261 112.5
M2.2.2.1 59379.8 344.899 89.1
M2.3.2.1 60326.6 349.874 74.15
M2.1.2.2 54595.6 176.090 119.65
M2.2.2.2 62851.9 211.373 88.9
M2.3.2.2 61200.8 205.413 76.6
and cons ain s he hyb idiza ion echniques ha e la ge impac on he pe o mance
o he b anch and bound algo i hm.
5.2 Bi-objec i e assignmen p oblems
We conside bi-objec i e assignmen p oblems ha ing n=2 a iables,
max


i=1


j=1
ck
ij xij k=1,2
s. .


i=1
xij =1j=1,...,


j=1
xij =1i=1,...,
x∈{0,1}×
whe e he cos coe icien s ck
ij ∈[50,100]. The algo i hmic s a egy o he solu ion
o IP scala iza ions depending on he alue o he pa ame e αis chosen simila ly o
123
Augmen ing bi-objec i e b anch and bound 115
Table 4 con inued (b) Facili y loca ion p oblem n=84
Ve sion Nodes Time (s) Sol ed IPs
BS2 7084.4 11.5822 0.0
M1.1.2 4873.8 8.7719 26.35
M1.2.2 4874.8 8.7534 17.45
M1.3.2 4894.1 8.7031 12.6
M2.1.2.1 4673.6 9.5755 49.65
M2.2.2.1 4832.0 8.9275 23.6
M2.3.2.1 4812.8 8.8050 17.4
M2.1.2.2 4628.9 8.7019 46.15
M2.2.2.2 4825.9 8.7491 24.4
M2.3.2.2 4807.5 8.5984 17.5
(c) Facili y loca ion p oblem n=130
Ve sion Nodes Time (s) Sol ed IPs
BB 17461.9 51.6307 0.0
BS1 10684.0 34.5157 0.0
WS 16795.9 50.9317 51.35
M1.1.1 10753.9 35.4356 37.1
M1.2.1 10753.9 35.2764 25.5
M1.3.1 10753.9 35.1007 19.15
M2.1.1.1 10104.4 38.3909 89.65
M2.2.1.1 10678.1 35.7434 39.35
M2.3.1.1 10722.3 35.6262 27.7
M2.1.1.2 10103.0 34.5003 85.95
M2.2.1.2 10691.2 35.3730 39.05
M2.3.1.2 10718.6 35.1690 27.45
BS2 15474.7 46.5130 0.0
M1.1.2 11548.8 38.4891 39.3
M1.2.2 11601.4 38.5848 24.6
M1.3.2 11535.1 38.2917 18.0
M2.1.2.1 10684.3 39.8639 81.5
M2.2.2.1 11381.8 39.1988 37.15
M2.3.2.1 11336.0 38.7754 28.45
M2.1.2.2 10695.5 36.9098 78.25
olume gap s a egy chooses he node wi h he la ges sea ch zone, which has he
bigges po en ial o educe his gap. Mo eo e , he local hype olume gap s a egy
aims a an uni o m dis ibu ion o poin s in he incumben lis . In ou nume ical es ,
M2.1.1.2 u n ou o be he bes choice in mos cases wi h espec o he numbe o
explo ed nodes and compu a ion ime. In his e sion, we use he local hype olume
gap s a egy o he choice o he ac i e node, e e y 10- h i e a ion he weigh ed sum
123

116 J. Bauß, M. S iglmay
Table 4 con inued (c) Facili y loca ion p oblem n=130
Ve sion Nodes Time (s) Sol ed IPs
M2.2.2.2 11341.6 38.2646 39.55
M2.3.2.2 11352.1 38.0063 25.9
(d) Facili y loca ion p oblem n=186
Ve sion Nodes Time (s) Sol ed IPs
BB 67369.3 373.238 0.0
BS1 31844.1 203.145 0.0
WS 62192.8 349.741 69.95
M1.1.1 32106.6 206.244 53.05
M1.2.1 32097.9 206.851 33.4
M1.3.1 32148.5 207.199 23.75
M2.1.1.1 28384.2 224.486 186.8
M2.2.1.1 31074.5 218.314 101.15
M2.3.1.1 32004.8 209.608 50.1
M2.1.1.2 28558.8 186.010 172.7
M2.2.1.2 30946.4 202.329 97.75
M2.3.1.2 32011.8 207.715 47.5
BS2 50759.0 292.344 0.0
M1.1.2 35150.1 230.687 55.5
M1.2.2 35789.8 233.967 30.8
M1.3.2 35255.0 233.163 21.95
M2.1.2.1 29704.3 230.016 172.65
M2.2.2.1 33959.7 236.351 81.75
M2.3.2.1 34228.0 233.553 50.2
M2.1.2.2 30412.6 202.719 167.4
M2.2.2.2 34511.8 229.970 69.95
M2.3.2.2 34405.0 229.021 47.1
IP scala iza ion is applied and e e y 50- h i e a ion we apply he augmen ed weigh ed
Tchebyche scala iza ion ins ead. Fu he mo e, he objec i e space in o ma ion gained
by he augmen ed weigh ed Tchebyche scala iza ion is no used o upda e he lowe
bound se , since i s local imp o emen s do no compensa e he inc eased compu a ion
ime. Al hough we need o sol e mo e IPs han in mos o he app oaches, he compu-
a ion ime is he lowes compa ed o he o he s. So, using he augmen ed weigh ed
Tchebyche scala iza ion in he beginning o he b anch and bound wo ks bes . Due
o he likelihood o inding non-suppo ed non-domina ed poin s in he ea ly s ages
o he algo i hm, he uppe bound can be u he imp o ed. This esul s o a highe
p obabili y o a homing a node by dominance. Ne e heless, wi h e sion BS1 we
also achi e a ema kable educ ion in e ms o he numbe o explo ed nodes and
compu a ion ime by using he local hype olume gap s a egy o node selec ion.
123
Augmen ing bi-objec i e b anch and bound 117
Fig. 4 Visualiza ion o b anch and bound node educ ion and un ime educ ion o a ying es ins ance
sizes on a selec ion o app oaches
123
118 J. Bauß, M. S iglmay
6 Conclusion and ou look
In his pape , we p opose wo app oaches o inco po a e objec i e space in o ma-
ion in bi-objec i e b anch and bound. By using he local o global (app oxima ed)
hype olume gap as a node selec ion c i e ion, we adap he un o he b anch and
bound algo i hm o he p oblem ins ance. Addi ionally, we adap i ely sol e scala -
iza ions o in ege op imali y o imp o e he lowe and he uppe bound se by he
ob ained objec i e space in o ma ion. Ou nume ical esul s show he e ec i eness o
bo h app oaches and in pa icula o hei combina ion. The dynamic b anching ule
based on he local (app oxima ed) hype olume gap has la ge impac on he numbe
o explo ed subp oblems, is compua ionally e icien and can be easily in eg a ed in
o he mul i-objec i e b anch and bound algo i hms.
While we es ed in his pape he indi idual con ibu ions o ou augmen a ions
on a gene ic bi-objec i e b anch and bound, we will con inue o ex end ou ideas o
mul iple dimensions and in eg a e hem in o a compe e i e mul i-objec i e b anch and
bound amewo k. Pa icula ly in highe dimensions, i may be p omising o combine
ou app oaches wi h objec i e space b anching.
Funding Open Access unding enabled and o ganized by P ojek DEAL. The au ho s hank ully acknowl-
edge inancial suppo by Deu sche Fo schungsgemeinscha , P ojec Numbe KL 1076/11-1.
Da a a ailabili y The implemen a ion in Julia and he used es da ase s a e a ailable in Gi eposi o y
h ps://gi .uni-wuppe al.de/bauss/augmen ed-bi-objec i e-b anch-and-bound.
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.
Open Access This a icleislicensedunde aC ea i eCommonsA ibu ion4.0In e na ionalLicense,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
Aneja YP, Nai KPK (1979) Bic i e ia anspo a ion p oblem. Manag Sci 25(1):73–78. h ps://doi.o g/10.
1287/mnsc.25.1.73
Bauß J, S iglmay M (2023) Augmen ed Bi-objec i e B anch and Bound. Gi eposi o y. h ps://gi .uni-
wuppe al.de/bauss/augmen ed-bi-objec i e-b anch-and-bound
Bazgan C, Hugo H, Vande poo en D (2009) Sol ing e icien ly he 0–1 mul i-objec i e knapsack p oblem.
Compu Ope Res 36(1):260–279. h ps://doi.o g/10.1016/j.co .2007.09.009
Belo i P, Soylu B, Wiecek MM (2012) A b anch-and-bound algo i hm o biobjec i e mixed-in ege p o-
g ams. Technical epo . h ps://op imiza ion-online.o g/?p=12266
123
Augmen ing bi-objec i e b anch and bound 119
Benson HP (1998) An ou e app oxima ion algo i hm o gene a ing all e icien ex eme poin s in he
ou come se o a mul iple objec i e linea p og amming p oblem. J Glob Op im 13(1):1–24. h ps://
doi.o g/10.1023/A:1008215702611
Bökle F, Mu zel P (2015) Ou pu -sensi i e algo i hms o enume a ing he ex eme nondomina ed poin s
o mul iobjec i e combina o ial op imiza ion p oblems. In: Algo i hms—ESA 2015. Sp inge , Be lin,
pp 288–299. h ps://doi.o g/10.1007/978-3-662-48350-3_25
Boland N, Cha khga d H, Sa elsbe gh M (2015a) A c i e ion space sea ch algo i hm o biobjec i e in ege
p og amming: he balanced box me hod. INFORMS J Compu 27(4):735–754. h ps://doi.o g/10.
1287/ijoc.2015.0657
Boland N, Cha khga d H, Sa elsbe gh M (2015b) A c i e ion space sea ch algo i hm o biobjec i e mixed
in ege p og amming: he iangle spli ing me hod. INFORMS J Compu 27(4):597–618. h ps://doi.
o g/10.1287/ijoc.2015.0646
Boland N, Cha khga d H, Sa elsbe gh M (2017) The quad an sh inking me hod: a simple and e icien
algo i hm o sol ing i-objec i e in ege p og ams. Eu J Ope Res 260(3):873–885. h ps://doi.o g/
10.1016/j.ejo .2016.03.035
Däche K, Klam o h K (2014) A linea bound on he numbe o scala iza ions needed o sol e disc e e
ic i e ia op imiza ion p oblems. J Glob Op im 61(4):643–676. h ps://doi.o g/10.1007/s10898-014-
0205-z
Däche K, Go ski J, Klam o h K (2012) An augmen ed weigh ed Tchebyche me hod wi h adap i ely
chosen pa ame e s o disc e e bic i e ia op imiza ion p oblems. Compu Ope Res 39(12):2929–2943.
h ps://doi.o g/10.1016/j.co .2012.02.021
Dech e R,Pea lJ(1985)Gene alizedbes - i s sea chs a egiesand heop imali yo A∗.JACM32(3):505–
536. h ps://doi.o g/10.1145/3828.3830
Eh go M (2005) Mul ic i e ia Op imiza ion. Sp inge , Be lin. h ps://doi.o g/10.1007/3-540-27659-9
Eh go M, Gandibleux X (2007) Bound se s o biobjec i e combina o ial op imiza ion p oblems. Compu
Ope Res 34(9):2674–2694. h ps://doi.o g/10.1016/j.co .2005.10.003
Eh go M, Löhne A, Shao L (2012) A dual a ian o Benson’s “ou e app oxima ion algo i hm” o mul iple
objec i e linea p og amming. J Glob Op im 52:757–778
Fo ge N, Gadegaa d SL, Klam o h K, Nielsen LR, P zybylski A (2022) B anch-and-bound and objec i e
b anching wi h h ee o mo e objec i es. Compu Ope Res 148:106012. h ps://doi.o g/10.1016/j.co .
2022.106012
Gadegaa dSL,NielsenLR,Eh go M(2019)Bi-objec i eb anch-and-cu algo i hmsbasedonLP elaxa ion
and bound se s. INFORMS J Compu 31(4):790–804. h ps://doi.o g/10.1287/ijoc.2018.0846
Haimes Y, Lasdon L, Wisme D (1971) On a bic i e ion o ma ion o he p oblems o in eg a ed sys em iden-
i ica ion and sys em op imiza ion. IEEE T ans Sys Man Cybe ne . h ps://doi.o g/10.1109/TSMC.
1971.4308298
Jesus AD, Paque e L, De bel B, Lie ooghe A (2021) On he design and any ime pe o mance o indica o -
based b anch and bound o mul i-objec i e combina o ial op imiza ion. In: P oceedings o he gene ic
and e olu iona y compu a ion con e ence. ACM, Lille. h ps://doi.o g/10.1145/3449639.3459360
Kelle e H, P e schy U, Pisinge D (2004) Knapsack p oblems. Sp inge , Be lin. h ps://doi.o g/10.1007/
978-3-540-24777-7
Ki lik G, Sayın S (2014) A new algo i hm o gene a ing all nondomina ed solu ions o mul iobjec i e
disc e e op imiza ion p oblems. Eu J Ope Res 232(3):479–488. h ps://doi.o g/10.1016/j.ejo .2013.
08.001
Kizil an G, Yucao˘glu E (1983) An algo i hm o mul iobjec i e ze o-one linea p og amming. Manag Sci
29(12):1444–1453. h ps://doi.o g/10.1287/mnsc.29.12.1444
Klam o h K, Lacou R, Vande poo en D (2015) On he ep esen a ion o he sea ch egion in mul i-objec i e
op imiza ion. Eu J Ope Res 245(3):767–778. h ps://doi.o g/10.1016/j.ejo .2015.03.031
Klein D, Hannan E (1982) An algo i hm o he mul iple objec i e in ege linea p og amming p oblem.
Eu J Ope Res 9(4):378–385. h ps://doi.o g/10.1016/0377-2217(82)90182-5
LaumannsM, Thiele L, Zi zle E (2006) Ane icien ,adap i epa ame e a ia ionscheme o me aheu is ics
based on he epsilon-cons ain me hod. Eu J Ope Res 169(3):932–942. h ps://doi.o g/10.1016/j.
ejo .2004.08.029
Löhne A, Weißing B (2017) The ec o linea p og am sol e bensol e—no es on heo e ical backg ound.
Eu J Ope Res 260(3):807–813. h ps://doi.o g/10.1016/j.ejo .2016.02.039
123
120 J. Bauß, M. S iglmay
Ma o as G, Diakoulaki D (1998) A b anch and bound algo i hm o mixed ze o-one mul iple objec i e
linea p og amming. Eu J Ope Res 107(3):530–541. h ps://doi.o g/10.1016/s0377-2217(97)00077-
5
Ma o as G, Diakoulaki D (2005) Mul i-c i e ia b anch and bound: a ec o maximiza ion algo i hm o
mixed 0–1 mul iple objec i e linea p og amming. Appl Ma h Compu 171(1):53–71. h ps://doi.o g/
10.1016/j.amc.2005.01.038
Mie inen K (1998) Nonlinea mul iobjec i e op imiza ion. Sp inge , New Yo k. h ps://doi.o g/10.1007/
978-1-4615-5563-6
Mo ison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) B anch-and-bound algo i hms: a su ey o ecen
ad ances in sea ching, b anching, and p uning. Disc e Op im 19:79–102. h ps://doi.o g/10.1016/j.
disop .2016.01.005
Özpeyni ci Ö, Köksalan M (2010) An exac algo i hm o inding ex eme suppo ed nondomina ed poin so
mul iobjec i e mixed in ege p og ams. Manag Sci 56(12):2302–2315. h ps://doi.o g/10.1287/mnsc.
1100.1248
Pa agh SN, T icoi e F (2019) B anch-and-bound o bi-objec i e in ege p og amming. INFORMS J Com-
pu 31(4):805–822. h ps://doi.o g/10.1287/ijoc.2018.0856
P zybylski A, Gandibleux X (2017) Mul i-objec i e b anch and bound. Eu J Ope Res 260(3):856–872.
h ps://doi.o g/10.1016/j.ejo .2017.01.032
P zybylski A, Gandibleux X, Eh go M (2008) Two phase algo i hms o he bi-objec i e assignmen
p oblem. Eu J Ope Res 185(2):509–533. h ps://doi.o g/10.1016/j.ejo .2006.12.054
P zybylski A, Gandibleux X, Eh go M (2010a) A ecu si e algo i hm o inding all nondomina ed ex eme
poin s in he ou come se o a mul iobjec i e in ege p og amme. INFORMS J Compu 22(3):371–386.
h ps://doi.o g/10.1287/ijoc.1090.0342
P zybylski A, Gandibleux X, Eh go M (2010b) A wo phase me hod o mul i-objec i e in ege p og am-
mingandi sapplica ion o heassignmen p oblemwi h h eeobjec i es.Disc e e Op im 7(3):149–165.
h ps://doi.o g/10.1016/j.disop .2010.03.005
P zybylski A, Klam o h K, Lacou R (2019) A simple and e icien dicho omic sea ch algo i hm o mul i-
objec i e mixed in ege linea p og ams. a Xi . h ps://doi.o g/10.48550/ARXIV.1911.08937
Se a ini P (1987) Some conside a ions abou compu a ional complexi y o mul i objec i e combina o ial
p oblems. In: Recen ad ances and his o ical de elopmen o ec o op imiza ion. Sp inge , Be lin,
pp 222–232. h ps://doi.o g/10.1007/978-3-642-46618-2_15
Sou d F, Spanjaa d O (2008) A mul iobjec i e b anch-and-bound amewo k: applica ion o he biobjec i e
spanning ee p oblem. INFORMS J Compu 20(3):472–484. h ps://doi.o g/10.1287/ijoc.1070.0260
S eue RE (1986) Mul iple c i e ia op imiza ion: heo y, compu a ion and applica ion. Wiley, New Yo k.
h ps://doi.o g/10.1002/oca.4660100109
S eue RE, Choo E-U (1983) An in e ac i e weigh ed Tchebyche p ocedu e o mul iple objec i e p o-
g amming. Ma h P og am 26(3):326–344. h ps://doi.o g/10.1007/BF02591870
S idsen T, Ande sen KA (2018) A hyb id app oach o biobjec i e op imiza ion. Disc e Op im 28:89–114.
h ps://doi.o g/10.1016/j.disop .2018.02.001
S idsen T, Ande sen KA, Dammann B (2014) A b anch and bound algo i hm o a class o biobjec i e
mixed in ege p og ams. Manag Sci 60(4):1009–1032. h ps://doi.o g/10.1287/mnsc.2013.1802
Tuy ens D, Teghem J, Fo emps P, Nieuwenhuyze KV (2000) Pe o mance o he MOSA me hod o he
bic i e ia assignmen p oblem. J Heu is 6(3):295–310. h ps://doi.o g/10.1023/a:1009670112978
Ulungu EL, Teghem J (1995) The wo phases me hod: an e icien p ocedu e o sol e bi-objec i e combi-
na o ial op imiza ion p oblems. Found Compu Decis Sci 20:149–156
Ulungu EL, Teghem J (1997) Sol ing mul i-objec i e knapsack p oblem by a b anch-and-bound p ocedu e.
In: Mul ic i e ia analysis. Sp inge , Be lin, pp 269–278. h ps://doi.o g/10.1007/978-3-642-60667-
0_26
Vincen T, Seipp F, Ruzika S, P zybylski A, Gandibleux X (2013) Mul iple objec i e b anch and bound o
mixed 0–1 linea p og amming: co ec ions and imp o emen s o he biobjec i e case. Compu Ope
Res 40(1):498–509. h ps://doi.o g/10.1016/j.co .2012.08.003
Visée M, Teghem J, Pi lo M, Ulungu EL (1998) Two-phases me hod and b anch and bound p ocedu es
o sol e he bi-objec i e knapsack p oblem. J Glob Op im 12(2):139–155. h ps://doi.o g/10.1023/A:
1008258310679
Zi zle E, Thiele L (1999) Mul iobjec i e e olu iona y algo i hms: a compa a i e case s udy and he s eng h
pa e o app oach. IEEE T ans E ol Compu 3(4):257–271. h ps://doi.o g/10.1109/4235.797969
123

Augmen ing bi-objec i e b anch and bound 121
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