Robust combinatorial optimization problems under budgeted interdiction uncertainty

Goe igk, Ma c; Khos a i, Mohammad
A icle — Published Ve sion
Robus combina o ial op imiza ion p oblems unde
budge ed in e dic ion unce ain y
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Goe igk, Ma c; Khos a i, Mohammad (2024) : Robus combina o ial op imiza ion
p oblems unde budge ed in e dic ion unce ain y, OR Spec um, ISSN 1436-6304, Sp inge , Be lin,
Heidelbe g, Vol. 47, Iss. 1, pp. 255-285,
h ps://doi.o g/10.1007/s00291-024-00772-0
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323262
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/
Vol.:(0123456789)
OR Spec um (2025) 47:255–285
h ps://doi.o g/10.1007/s00291-024-00772-0
ORIGINAL ARTICLE
Robus combina o ial op imiza ion p oblems
unde budge ed in e dic ion unce ain y
Ma cGoe igk1 · MohammadKhos a i1
Recei ed: 8 July 2023 / Accep ed: 27 May 2024 / Published online: 5 June 2024
© The Au ho (s) 2024
Abs ac
In obus combina o ial op imiza ion, we would like o ind a solu ion ha pe o ms
well unde all ealiza ions o an unce ain y se o possible pa ame e alues. How
we model his unce ain y se has a decisi e in luence on he complexi y o he
co esponding obus p oblem. Fo his eason, budge ed unce ain y se s a e o en
s udied, as hey enable us o decompose he obus p oblem in o easie subp oblems.
We p opose a a ian o disc e e budge ed unce ain y o ca dinali y-based
cons ain s o objec i es, whe e a weigh ec o is applied o he budge cons ain .
We show ha while he ad e sa ial p oblem can be sol ed in linea ime, he obus
p oblem becomes NP-ha d and no app oximable. We discuss di e en possibili ies
o model he obus p oblem and show expe imen ally ha despi e he ha dness
esul , some models scale ela i ely well in he p oblem size.
Keywo ds Robus op imiza ion· Combina o ial op imiza ion· Budge ed
unce ain y· Knapsack unce ain y
1 In oduc ion
Unce ain y can mani es in a ious o ms, such as imp ecise da a o he inhe en
unp edic abili y o he u u e. A no able case s udy u ilizing linea p og ams (Ben-
Tal and Nemi o ski 2000) demons a ed ha e en sligh changes in p oblem da a can
signi ican ly shi an op imal solu ion owa ds in easibili y, ende ing i p ac ically
useless. Consequen ly, a ange o decision-making app oaches unde unce ain y
ha e been de eloped, including s ochas ic p og amming (Kail and Maye 2005),
uzzy op imiza ion (Lodwick and Kacp zyk 2010), and obus op imiza ion (Ben-
Tal Aha on e al. 2009). O en, such app oaches make he esul ing decision-making
p oblems mo e challenging o sol e han hei nominal coun e pa s. The ocus o
* Mohammad Khos a i
mohammad.khos a[email p o ec ed]
1 Business Decisions andDa a Science, Uni e si y o Passau, D .-Hans-Kap inge -S aße 30,
94032Passau, Ge many
256
M.Goe igk, M.Khos a i
his pape is on obus combina o ial decision p oblems, which ha e he dis inc
ad an age ha a p obabili y dis ibu ion on he unce ain da a does no need o be
known. Mo e o mally, conside some nominal combina o ial p oblem
whe e we w i e ec o s in bold and use he no a ion [n] o deno e se s
{1, …,n}
. In
addi ion, assume ha he da a
c
c
c
in he objec i e unc ion is no known exac ly. Gi en
a se o possible da a alues
U
, he classic min-max app oach o obus op imiza ion
is o sol e he p oblem
Many mo e a ian s o obus op imiza ion p oblems exis , see e.g. Goe igk and
Schöbel (2016), Kaspe ski and Zieliński (2016) and Buchheim and Ku z (2018) o
an o e iew. Wha hey ha e in common is ha a se
U
con aining all scena ios
can be o mula ed by he decision make , and is made a ailable o he op imiza ion
p oblem. Da a-d i en obus op imiza ion (Be simas e al. 2018) aims a au oma ing
his s ep by o mula ing sui able unce ain y se s based on a ailable da a (e.g., by
using on he isk p e e ence o he decision make ).
The e is ypically a ade-o be ween he modeling capabili ies o he unce ain y
se
U
and he complexi y o he esul ing p oblem. A disc e e scena io se
U
o e s
b oad lexibili y as i allows di ec u iliza ion o any amoun o his o ical da a
obse a ions in he model. Howe e , i comes wi h a d awback ha he obus
e sions o ele an combina o ial p oblems a e al eady compu a ionally di icul
(NP-ha d) e en when conside ing only wo scena ios (Kaspe ski and Zieliński
2016). Rep esen ing
U
using a gene al polyhed on, de ined by i s inne o ou e
desc ip ion, su e s om he same limi a ion (Goe igk e al. 2022).
A signi ican b eak h ough was made wi h he in oduc ion o budge ed
unce ain y se s, also known as he Be simas–Sim app oach (2003, 2004). This
app oach add esses an unce ain linea objec i e
c
c
c⊺x
x
x
, whe e each coe icien
i∈[n]
is bounded by a lowe bound
ci
and an uppe bound
ci
. Mo eo e , only a ixed in ege
Γ
o coe icien s a e allowed o de ia e simul aneously om hei lowe o uppe
bounds. In o he wo ds,
U
inco po a es a ca dinali y cons ain o he ollowing
o m:
The in oduc ion o his simple idea has had a p o ound impac on he ield o
obus op imiza ion. The wo pape s ha p esen ed his idea con inue o be widely
ci ed, highligh ing hei signi icance. The appeal o unce ain y se s o his na u e
lies in hei simplici y and in ui i e na u e. Fu he mo e, i has been demons a ed
ha he obus min–max p oblem can be decomposed in o a manageable numbe
min
∑
i∈[n]
cixi
(Nom)
s. . x
x
x∈
X
⊆{0, 1}
n
min
x
x
x∈Xmax
c
c
c∈U
∑
i∈[n]
cixi
(RO)
UΓ=
{
c
c
c∈ℝn∶∃𝛿
𝛿
𝛿∈{0, 1}ns. . ci=ci+(
ci−ci)𝛿i,
∑
i∈[n]
𝛿i≤Γ
}
257
Robus combina o ial op imiza ion p oblems unde budge ed…
(speci ically, O(n)) o nominal- ype p oblems (Nom). This decomposi ion allows
o inc eased modeling lexibili y wi hou incu ing signi ican compu a ional
complexi y. I he nominal p oblem can be sol ed in polynomial ime, he
co esponding obus p oblems can be sol ed in polynomial ime as well.
The ad an ages o e ed by budge ed unce ain y se s ha e esul ed in hei
widesp ead and a ied applica ions o eal-wo ld p oblems. These applica ions
encompass a ange o domains, including po olio managemen (Be simas and
Pachamano a 2008), wine g ape ha es ing (Bohle e  al. 2010), supply chain
con ol (Be simas and Thiele 2006), u ni u e p oduc ion planning (Douglas
and Mo abi o 2012), ain load planning (B uns e al. 2014), and many o he s.
The e sa ili y o budge ed unce ain y se s has made hem a aluable ool in
add essing unce ain y and op imizing decision-making in nume ous p ac ical
scena ios.
A no ewo hy cha ac e is ic o
UΓ
is ha i
Γ
is an in ege , we can u ilize
con inuous de ia ions
𝛿
𝛿
𝛿∈[0, 1]n
wi hou al e ing he p oblem. This is due o
he ac ha when inding an op imal s a egy o he ad e sa y in he p oblem
maxc
c
c∈Uc
c
c⊺x
x
x
gi en a ixed solu ion
x
x
x
, i is su icien o so he i ems chosen by
x
x
x
based on he po en ial cos de ia ion
ci
−ci
, and selec he
Γ
la ges alues.
Consequen ly, he equi alence be ween “disc e e” and “con inuous” budge ed
unce ain y holds. Howe e , his equi alence does no gene ally hold in he case
o mul i-s age obus p oblems, whe e ecou se ac ions can be aken a e he cos
scena io has been e ealed (see, e.g., he discussion in Goe igk e al. (2022)).
The e ec i eness o budge ed unce ain y se s has led o he eme gence o
a ious a ian s and gene aliza ions o his app oach. In he pape by Be simas
e al. (2004), no m-based unce ain y se s we e in oduced. I was demons a ed
ha he adi ional budge ed unce ain y se can be cons uc ed using a speci ic
no m known as he D-no m. Ano he a ian is mul i-band unce ain y (Büsing
and D’and eagio anni 2012), which in ol es a sys em o de ia ion alues
d1
ij
<d
2
ij
<…<d
K
ij
wi h bo h lowe and uppe bounds on he numbe o possible
de ia ions om each band
k∈[K]
. In a iable budge ed unce ain y (Poss 2013),
he numbe o de ia ions
𝛾
aken in o accoun may depend on he size
‖x
x
x‖1
o he
solu ion
x
x
x
o which he ad e sa ial p oblem is being sol ed.
Addi ionally, he e is knapsack unce ain y (Poss 2018), which can be
ep esen ed as ollows:
He e, he se o possible scena ios is bounded by m linea knapsack cons ain s.
When he alue o m is ixed, simila esul s o hose ob ained o he o iginal se
UΓ
can be de i ed. A special case o his ype o se is locally budge ed unce ain y,
see Goe igk and Lendl (2021) and Yaman (2023), whe e each o he knapsack
cons ain s a ec s a subse o a iables, and hese subse s a e disjoin be ween
cons ain s. These a ian s and gene aliza ions o budge ed unce ain y se s p o ide
U
knap =
{
c
c
c∈ℝn∶∃𝛿
𝛿
𝛿∈[0, 1]ns. . ci=ci+(
ci−ci)𝛿i,
∑
i∈[n]
aji𝛿i≤bj,j∈[m]
}
258
M.Goe igk, M.Khos a i
addi ional lexibili y and adap abili y o a ious p oblem se ings, enhancing he
obus ness o decision-making unde unce ain y.
In his pape we conside a new ype o unce ain y se , applicable o an objec i e
o cons ain s ha in ol e he ca dinali y1
‖x
x
x‖1
, e.g., o p oblems whe e he ask is
o maximize he size o a se , o whe e his ca dinali y is no allowed o all below
a ce ain h eshold. The mo i a ion o conside such se s comes om a eal-wo ld
p oblem in ol ing he composi ion o eams o ake on a se o jobs unde unce ain
skill equi emen s (see Anoshkina and Meisel 2019; Anoshkina e al. 2020). In such
p oblems, one would like o compose eams ha can ake on he maximum possible
numbe o jobs. F om an ad e sa ial pe spec i e, he ask is o change he job skill
equi emen s in a way ha minimizes he numbe o jobs ha can be ca ied ou
success ully. F om a mo e heo e ical pe spec i e, he s udy o obus combina o ial
p oblems o en makes use o selec ion- ype p oblems (see, e.g., A e bakh 2001;
Dolgui and Ko ale 2012; Deineko and Woeginge 2013; Kaspe ski e al. 2015). In
he mos basic o m, he selec ion p oblem equi es us o selec p ou o n possible
i ems, i.e., o sol e
wi h known cos s
d
d
d∈ℝn
+
. While his nominal p oblem is i ial o sol e, ea ing
obus a ian s becomes mo e complex. A new pe spec i e on p oblems o his ype
is o loca e he unce ain y no (only) on he i em cos s; ins ead, i ems ha e di e en
deg ees o eliabili y, and an ad e sa y ies o iola e he cons ain
∑i∈[n]
x
i
≥
p
.
Mo i a ed by hese wo p oblems, bu being applicable o a wide ange o
p oblems as well, he “budge ed in e dic ion” app oach ha we hus p opose is o
conside unce ain y se s o he o m
wi h
w
w
w∈ℕn
and
B∈ℕ
. The ad e sa y can he e o e in e dic a solu ion (i.e.,
le i ems ail), bu has a speci ied budge o his pu pose. Th oughou he pape ,
we assume ha each
wi
is no la ge han B; o he wise, i s coe icien canno be
a acked and is he e o e no unce ain. The unce ain y can a ec a ca dinali y
objec i e unc ion
(1
1
1−c
c
c)⊺x
x
x
ha should be maximized, o a ca dinali y cons ain
(1
1
1−c
c
c)⊺x
x
x
≥
p
. No e ha in he co esponding nominal p oblems, ec o
c
c
c
is no
p esen , bu is in oduced in he obus p oblem o model he unce ain y o he
ec o
1
1
1
. Ca dinali y cons ain s also play a ole in many op imiza ion p oblems
ha allow a cu -based o mula ion. Fo example, he sho es pa h p oblem can be
w i en as
min {
d
d
d⊺x
x
x∶
∑
i∈[n]
xi≥p,x
x
x∈{0, 1}n
}
U
=
{
c
c
c∈{0, 1}n∶
∑
i∈[n]
wici≤B
}
1 As
x
x
x
is bina y, i co esponds o a subse X o [n], whe e
X={i∈[n]∶xi=1}
. The no ion o ca di-
nali y e e s o
�X�=‖x
x
x‖1
.

259
Robus combina o ial op imiza ion p oblems unde budge ed…
wi h
S={S⊆V∶s∈S, ∉S}
. Cu -based p oblem o mula ions a e also used
o he gene alized S eine ee, spanning ee, eedback e ex se , o a eling
salespe son p oblems (Ko e and Vygen 2018).
Obse e ha his de ini ion o unce ain y se is essen ially he budge ed
unce ain y se
UΓ
“upside down”: while
UΓ
has a bound on he numbe o
coe icien s ha can de ia e and he e ec o de ia ion is gi en by some pa ame e
ci
−ci
, he e we wan o maximize he numbe o de ia ions and each de ia ion has a
cos pa ame e
wi
. No e ha di e en o
Uknap
, he e is a single budge cons ain , we
conside a disc e e ins ead o con inuous de ia ion, and in pa icula , he ec o
c
c
c
is
bina y.
As an example, conside he selec ion p oblem
whe e he ca dinali y cons ain
∑i∈[4]
x
i
≥
1
is unce ain and hus can be a acked
by an ad e sa y. The ca dinali y cons ain o he obus coun e pa o his example
becomes
whe e he unc ion
𝜙(x
x
x)
ep esen s he numbe o i ems ha can ail. To u he
illus a e his se ing, le us assume ha
ha is, in he de ini ion o
U
, we use
B=10
and
w=(3, 7, 4, 10)⊺
. A possible
solu ion o he obus p oblem is o pick i ems 1, 2 and 3 a cos
2+3+4=9
. The
ad e sa y can a ack i ems 1 and 3, bu does no ha e su icien budge o le all h ee
i ems ail. An e en be e solu ion is o pick i ems 1 and 4 a cos
2+5=7
. In his
case, he ad e sa y can only a ack one o he wo i ems.
The emainde o his pape is s uc u ed as ollows. In Sec .2, we discuss he
complexi y o he obus p oblem wi h budge ed in e dic ion unce ain y, and
p o e ha he p oblem is no app oximable. Fu he mo e, we p o ide i e compac
o mula ions o sol e p oblems wi h ca dinali y cons ain s unde in e dic ion
unce ain y se in Sec . 3. Expe imen al esul s illus a ing he pe o mance o
he models o he selec ion, job assignmen and 2-edge-connec ed subg aph
p oblems a e collec ed in Sec . 4. We summa ize ou indings and poin ing ou
min ∑
i∈E
dexe
s. . ∑
e∈𝛿(S)
xe≥1∀S∈
S
xe∈{
0, 1
}
min {
2x1+3x2+4x3+5x4∶
∑
i∈[4]
xi≥1,x
x
x∈{0, 1}4
}
min
c
c
c∈U(1
1
1−c
c
c)⊺x
x
x=
∑
i∈[n]
xi−max
c
c
c∈U
c
c
c⊺x
x
x=
∑
i∈[n]
xi−𝜙(x
x
x)≥
1
𝜙
(x
x
x)=max
{∑
i∈[n]
xici∶3c1+7c2+4c3+10c4≤10, c
c
c∈{0, 1}4
}
260
M.Goe igk, M.Khos a i
u he esea ch ques ions in Sec .5. The de ailed in o ma ion on how o model he
compac o mula ion o bo h job assignmen and cu -based p oblems a e p o ided in
AppendixA and B, espec i ely.
2 Complexi y analysis
In o de o check he complexi y le el o he obus selec ion p oblem unde
in e dic ion budge ed unce ain y, we i s need o in oduce he compac o mula ion
o i , hus we ha e
whe e he ad e sa y p oblem is
o a gi en
x
x
x∈{0, 1}n
. The e is a i ial algo i hm o sol e his p oblem; namely,
we so i ems i wi h
xi=1
by non-dec easing weigh
wi
, and pack i ems in his o de
un il he budge B canno accommoda e any u he i ems. Hence, he ad e sa ial
p oblem can be sol ed in O(n) ime (as i is no necessa y o so he comple e ec o ,
see, e.g. (Ko e and Vygen 2018, Chap e  17.1). Now we show ha he decision
e sion o he obus selec ion p oblem wi h in e dic ion unce ain y a ec ing he
cons ain s (ROSel) is ha d.
Theo em1 The ollowing decision p oblem is NP-comple e: Gi en
d
d
d∈ℕn
,
w
w
w∈ℕn
,
B∈ℕ
, and
V∈ℕ
, is he e a ec o
x
x
x∈{0, 1}n
wi h
∑i∈[n]
x
i
−𝜙(x
x
x)≥
1
and
∑i∈[n]
d
i
x
i
≤V?
P oo Obse e ha i is i ial o check i
∑i∈[n]
x
i−
𝜙
(
x
x
x
)
≥
1
and
∑i∈[n]
d
i
x
i
≤V o
a gi en
x
x
x
, which means ha he decision p oblem is indeed in NP.
To show NP-comple eness, we make use o he pa i ion p oblem: Gi en posi i e
in ege s
1,…, n
, is he e a se
S⊆[n]
such ha
∑i∈S
i=
V wi h
V=∑i∈[n]
i∕2
?
Gi en such an ins ance o he pa i ion p oblem, we cons uc a obus p oblem
wi h budge ed in e dic ion in he ollowing way. Se
di=wi= i
and
B=V−1
.
Then he cons ain
wi h
min
∑
i∈[n]
dixi
s. . ∑
i∈[n]
xi−𝜙(x)≥p∀c∈U
x∈{
0, 1
}
n
𝜙
(x
x
x)=max
{∑
i∈[n]
xici∶
∑
i∈[n]
wici≤B,ci∈{0, 1}∀i∈[n]
}
∑
i∈[n]
xi−𝜙(x
x
x)≥
1
261
Robus combina o ial op imiza ion p oblems unde budge ed…
equi es us o pack i ems o o al weigh s ic ly g ea e han
V−1
o a oid ha ing
all i ems in e dic ed. This means ha he pa i ion p oblem is a Yes-ins ance i and
only i he e is a easible solu ion
x
x
x∈{0, 1}n
wi h objec i e alue less o equal o
V. As he pa i ion p oblem is well-known o be NP-comple e (Ga ey and Johnson
1979), he claim ollows.
◻
This b ie analysis shows ha we lose a main ad an age o classic budge ed
unce ain y, whe e he obus p oblem can be decomposed in o a se o nominal
p oblems. No e ha Theo em1 applies o op imiza ion p oblems wi h an unce ain
ca dinali y cons ain and an objec i e
∑i∈[n]
d
i
x
i
ha should be minimized, bu
i also applies o he case o ha ing one linea cons ain
∑i∈[n]
d
i
x
i
≤
V
and an
unce ain ca dinali y objec i e ha should be maximized. In pa icula , in he la e
case his means ha i is NP-comple e o ind a solu ion wi h a non-ze o objec i e
alue; in o he wo ds, i is no possible o ind a polynomial- ime app oxima ion
algo i hm o his se ing, unless P = NP. Hence we conclude he ollowing esul .
Co olla y 2 The op imiza ion p oblem
maxx
x
x∈
Xmin
c
c
c∈
U
∑i∈[n]
(1−c
i
)x
i
is no app oxi-
mable, e en i
maxx
x
x∈
X
∑i∈[n]
x
i
can be sol ed in polynomial ime.
P oo Gi en a pa i ion p oblem as in he p oo o Theo em 1, se
X={
x
x
x
∈{0, 1}n∶∑i∈[n]
i
x
i
≤V
}
. Then he e is a solu ion wi h objec i e alue
g ea e o equal o one i and only i he pa i ion p oblem is a Yes-ins ance. Hence,
he e canno be an
𝛼
-app oxima ion o any
𝛼>0
, unless P = NP.
◻
3 Model o mula ions
In his sec ion, we in oduce i e compac o mula ions o he obus p oblem, whe e
we ocus on an unce ain ca dinali y cons ain
∑i∈[n]
x
i
≥
p
o ease o p esen a ion.
Addi ional cons ain s on
x
x
x
may be conside ed, which a e assumed o be modeled
indi ec ly in he se
X⊆{0, 1}n
. Tha is, we conside e o mula ions o he ollowing
ype o obus p oblem wi h ca dinali y cons ain s:
whe e he nominal p oblem co esponds o he case
c
c
c=0
0
0
. In addi ion, wi hou
loss o gene ali y, we assume ha he i ems a e so ed based on hei weigh s (
wi
),
non-dec easingly.
𝜙
(x
x
x)=max
{∑
i∈[n]
xici∶
∑
i∈[n]
ici≤V−1
}
min ∑
i∈[n]
dixi
s. . ∑
i∈[n]
(1−ci)xi≥p∀c
c
c∈U
x
x
x∈X
262
M.Goe igk, M.Khos a i
3.1 IP‑1
The i s idea o ind a compac o mula ion o he p oblem is only applicable
o he case
p=1
wi h in ege weigh s
w
w
w
. This means we only need o ha e one
i em a e he ad e sa y a acks, a case ha emains ha d, as Theo em1 shows.
The e o e, i su ices o pack i ems wi h minimum cos whose o al weigh s ic ly
exceeds he ad e sa ial budge B. This idea can be o mula ed as ollows:
3.2 IP‑2
We now conside he gene al case o a bi a y alues o p. As no ed, he
ad e sa ial p oblem
𝜙(x
x
x)
can be sol ed in polynomial ime by packing i ems wi h
smalles weigh i s . The e o e, we in oduce a iables
𝜆k∈{0, 1}
o all
k∈[n]
,
whe e
𝜆k
is ac i e i and only i we a ack he i s k i ems (no e ha he case
k=0
can be igno ed, as we can always a ack a leas one i em, due o each
wi
being
no la ge han B). An a ack only incu s cos s on he in e dic ion budge i
xi=1
.
Hence, we ob ain he ollowing in ege p og am:
By Cons ain (3), we can only choose one o he candida e a acks ep esen ed by
𝜆k
. Due o Cons ain (2), we canno use a ack
𝜆k
i
∑i∈[k]
w
i
x
i
>
B
. I is easy o see
ha we can elax he in eg ali y cons ain s o
𝜆k
, which gi es an LP o mula ion o
𝜙(x
x
x)
. By using linea p og amming duali y, we hus can ob ain he o mula ion o
he obus p oblem unde budge ed in e dic ion unce ain y:
min ∑
i∈[n]
dixi
(IP-1)
s. . ∑
i∈[n]
wixi≥B+1
x
x
x∈X
(1)
𝜙
(x
x
x)=max
∑
k∈[n]
(
∑
i∈[k]
xi)𝜆
k
(2)
s. .(∑
i∈[k]
wixi−B
)
𝜆k≤0∀k∈[n
]
(3)
∑
k∈[n]
𝜆k≤
1
(4)
𝜆k∈{0, 1}∀k∈[n]
269
Robus combina o ial op imiza ion p oblems unde budge ed…
We use wo echniques o gene a e ins ances o he selec ion p oblem unde
budge ed in e dic ion unce ain y, called Gen-1 and Gen-2. In Gen-1, he
weigh s a e chosen independen ly om he co esponding cos s, which means
ha he e may be bo h pa icula ly good i ems (wi h low
ci
and high
wi
) and bad
i ems. In Gen-2, he weigh o i ems depend on hei cos s, which in ui i ely
may lead o ha de ins ances compa ed o Gen-1. The gene a ion me hods a e
conside ed as ollows:
• Gen-1: o each
i∈[n]
we choose
di,wi
om
{1, …, 100}
independen ly andom
uni o m
• Gen-2: o each
i∈[n]
he alue o
wi
depends on he alue o
di
, hus we choose
di
om
{1, …, 100}
and
wi
om
{max(1, di−5),…, min(100, di+5)}
andomly
uni o m
In bo h cases, we se
4.1.2 Expe imen 1
He e we ocus on he LP- elaxa ion o all models and compa e he lowe bounds
ob ained by each o hem. In his expe imen we ix
n=10
and
p=1
o include
all models. We sol e he LP elaxa ions o 1000 ins ances o each combina ion
o gene a ion and solu ion me hods using CPLEX. We hen pe o m a pai wise
compa ison o he esul ing lowe bounds.
B
=
�∑
i∈[n]wi
4
�
Table 2 LB compa ison (Gen-
1)IP-1 IP-2 IP-3 IP-4 IP-5
%
IP-1 – 979 967 993 983 98.05
IP-2 21 – 5 368 92 12.15
IP-3 33 982 – 878 412 57.63
IP-4 7 628 118 – 9 19.05
IP-5 17 898 575 987 – 61.93
Table 3 LB compa ison (Gen-
2)IP-1 IP-2 IP-3 IP-4 IP-5
%
IP-1 – 1000 999 1000 1000 99.98
IP-2 0 – 0 999 586 39.63
IP-3 1 1000 – 1000 1000 75.03
IP-4 0 1 0 – 0 0.03
IP-5 0 414 0 1000 – 35.35

270
M.Goe igk, M.Khos a i
The esul s o his expe imen is p esen ed in Tables 2 and 3 o Gen-1 and
Gen-2, espec i ely. Each numbe shows how many imes he me hod in he
espec i e ow p o ided a s ic ly be e (in his case highe ) lowe bound han he
model in he co espondence column. The las column shows he a e age o cases
pe ow whe e he model has been be e hen he compa ison model in pe cen .
Based on he in o ma ion p o ided in Table 2 o Gen-1, we no e ha IP-1
domina es all o he models in o e 98% o cases (which is no su p ising, as i is
he mos specialized model). The nex bes model is IP-5, ollowed by IP-3. Wi h
some gap behind hese wo models ollow IP-4 and IP-2. The weakes model, IP-2,
is s onge han ano he model in only a ound 12% o cases.
In e es ingly, his o de ing changes when using ins ances o ype Gen-2,
see Table3. While IP-1 s ill ou pe o ms o he models o he models in nea ly all
cases (o e 99%), he second bes model is IP-3, which pe o ms ela i ely be e
han be o e. Simila ly, IP-2 has imp o ed in he anking, while IP-5 (which was he
second bes choice in Table2 is now elega ed o ou h place. IP-4 can p o ide a
be e bound han ano he model in only one single ins ance.
4.1.3 Expe imen 2
In his expe imen , we a y he p oblem size in
n∈{20, 25, …, 100}
. The expe i-
men is di ided in o wo pa s. In he i s pa , we ix p o 1 so ha all solu ion
me hods could be included, and also conside
p=5
o compa e he pe o mance o
solu ion me hods which can be applied o cases whe e
p>1
. In he second pa , we
use p
=n
5
so ha p g ows linea ly in n. Fo each combina ion o gene a ion and solu-
ion me hods we sol ed 50 ins ances using CPLEX and wi h a 600s ime limi . We
always p esen a plo o a e age solu ion imes and a pe o mance p o ile.
Figu e1 shows he solu ion imes o
p=1
. Clea ly, IP-1 is he as es model o
sol e ins ances o bo h Gen-1 and Gen-2, ollowed by IP-3. O he models also
show simila beha io o bo h gene a ion me hods. In e es ingly, IP-2 may e en
become as e as n inc eases, which seems coun e in ui i e, bu can be explained by
0.001
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP1
IP2
IP3
IP4
IP5
(a) Gen-1
0.001
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP1
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 1 Selec ion—Exp2—solu ion imes (
p=1
)
271
Robus combina o ial op imiza ion p oblems unde budge ed…
he ac ha p emains cons an . The pe o mance p o iles (see Fig.2) e lec a simi-
la ela i e pe o mance o he i e models.
In Figs.3 and 4, we show he a e age solu ion imes and pe o mance p o iles
o he case
p=5
, whe e IP-1 is no included. A simila beha io o he cases when
p=1
can be seen. As IP-1 is excluded, he e IP-3 has he bes a e age solu ion ime.
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP1
IP2
IP3
IP4
IP5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP1
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 2 Selec ion—Exp2—pe o mance p o iles (
p=1
)
0.001
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP2
IP3
IP4
IP5
(a) Gen-1
0.001
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 3 Selec ion—Exp2—solu ion imes (
p=5
)
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 4 Selec ion—Exp2—pe o mance p o iles (
p=5
)
272
M.Goe igk, M.Khos a i
The di e ence is ha IP-3 ails o be as e han IP-5 o ins ances wi h smalle size
o n. Simila ly, in he pe o mance p o ile, IP-3 domina es o he models. The main
di e ence compa ed o he case wi h
p=1
is ha none o he models is always
supe io o o he s.
We now conside he case p=
n
5
, i.e., p g ows linea ly wi h n. The a e age solu-
ion imes and pe o mance p o iless o his expe imen a e p esen ed in Figs.5 and
6, espec i ely.
The esul s o he second pa is closely simila o he i s pa esul s when
p=5
. Tha is, IP-3 bea s all o mula ions excep IP-5 wi h
n=20, 30, 40
o Gen-
1 and
n=20, 30
o Gen-2. In addi ion, he beha io o IP-2 and IP-4 is simila ,
howe e hei compa ison is di icul because o he ime limi . In his expe imen ,
IP-4 has be e solu ion ime han IP-2 o Gen-1, bu o Gen-2, IP-2 is sligh ly
as e han IP-4.
4.1.4 Expe imen 3
In his expe imen , we ix he numbe o i ems n and change he numbe o i ems we
wan o selec p. We conside he cases
n=20
and
n=40
. In bo h cases, p is chosen
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP2
IP3
IP4
IP5
(a)
Gen-1
0.01
0.1
1
10
100
1000
20 30 40 50 60 70 80 90 100
Solu ion Time
Size o (n)
IP2
IP3
IP4
IP5
(b)
Gen-2
Fig. 5 Selec ion—Exp2—solu ion imes ( p
=
n
∕5
)
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 6 Selec ion—Exp2—pe o mance p o iles (
p=n∕5
)
273
Robus combina o ial op imiza ion p oblems unde budge ed…
om
{1, 2, …, 10}
. As be o e, we sol ed 50 ins ances using CPLEX wi h a 600-sec-
ond ime limi o each combina ion o gene a ion and solu ion me hods. The esul s
o his expe imen is p o ided in Figs.7, 8, 9 and 10.
0.01
0.1
1
10
100
1000
1 2 3 4 5 6 7 8 9 10
Solu ion Time
Size o (p)
IP2
IP3
IP4
IP5
(a) Gen-1
0.01
0.1
1
10
100
1000
1 2 3 4 5 6 7 8 9 10
Solu ion Time
Size o (p)
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 7 Selec ion—Exp3—solu ion imes (
n=20
)
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 8 Selec ion—Exp3—pe o mance p o iles (
n=20
)
0.01
0.1
1
10
100
1000
1 2 3 4 5 6 7 8 9 10
Solu ion Time
Size o (p)
IP2
IP3
IP4
IP5
(a) Gen-1
0.01
0.1
1
10
100
1000
1 2 3 4 5 6 7 8 9 10
Solu ion Time
Size o (p)
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 9 Exp3, solu ion imes o
n=40
274
M.Goe igk, M.Khos a i
In e es ingly, he expe imen o ins ances wi h
n=20
shows ha IP-2, IP-3 and
IP-4 a e domina ed by IP-5 excep o
p=1
o bo h Gen-1 and Gen-2. In his sin-
gle case, IP-5 is ou pe o med by IP-3. This expe imen shows ha he p oblem sol ed
as e o la ge alue o p. This can be explained by he obse a ion ha o la ge
alues o p, nea ly all i ems need o be selec ed ( ecall ha we need o pack mo e han p
i ems o espec he unce ain y). Simila o o he expe imen s, he pe o mance p o ile
(see Fig.8) ep esen s he ob ained esul s o he a e age solu ion imes also holds o
he ins ance-wise compa isons o he gi en models.
The esul s depic ed in Figs.9 and 10 show ha he p oblems i s end o become
ha de o sol e and hen he solu ion ime alls. No ably, unlike he case wi h
n=20
,
IP-3 has he bes pe o mance wi h ega d o he solu ion ime. Ano he di e ence is
ha IP-3 is always supe io in compa ison o he o he ma hema ical o mula ions. In
his case he p oblem in conside ably ha de o sol e han cases wi h
n=20
. In his
sense, he p oblem hi s he ime limi e en o
p=1
, while IP-3 ne e eaches e en
close o he ime limi . The pe o mance p o ile shows ha IP-3 is almos always as e
han o he IPs.
4.2 Job assignmen
4.2.1 Se up
We now conside a job assignmen p oblem wi h m jobs and n wo ke s. Each job has
a p o i
pj
and wo ke s demand o
dj
o all
j∈[m]
. He e, ins ead o weigh s o each
i em in he selec ion p oblem, we ha e a ailu e p obabili y o each wo ke
wi
o all
i∈[n]
. The e o e, he obus job assignmen p oblem unde he budge ed in e dic ion
unce ain y can be o mula ed as ollows
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP2
IP3
IP4
IP5
(b) Gen-2
Fig. 10 Selec ion—Exp3—pe o mance p o iles (
n=40
)

275
Robus combina o ial op imiza ion p oblems unde budge ed…
In his case and in o de o see he pe o mance o ou IPs o e he job assignmen
p oblem, we only conside IP-2, IP-3, IP-4 and IP-5. The compac o mula ions
o hese ou IPs a e collec ed in “Appendix A”. Fu he mo e, we in oduce wo
expe imen s, whe e in expe imen  1 we ix he numbe o jobs and change he
numbe o wo ke s; while in expe imen 2 we ix he numbe o wo ke s and a y
he numbe o jobs.
Simila o he expe imen s on he selec ion p oblem, we use wo ypes o ins ance
gene a ion me hods o he job assignmen p oblem unde budge ed in e dic ion
unce ain y, called Gen-1 and Gen-2. In Gen-1, he job demands a e chosen
independen ly om he co esponding p o i s. In Gen-2, howe e , he p o i s o
jobs depend on hei demands. The gene a ion me hods a e conside ed as ollows:
Gen-1
• o each
i∈[m]
we choose
di
om
{
1, …,
2n
m}
independen ly andom uni o m.
• o each
i∈[m]
we choose
pi
om
{1, …, 25}
independen ly andom uni o m.
Gen-2
• o each
i∈[m]
we choose
di
om
{
1, …,
2n
m}
independen ly andom uni o m.
• o each
i∈[m]
he alue o
pi
depends on he alue o
di
. I
d
i≤
n
m
hen
pi
is
chosen om
{1, …, 25}
, o he wise we choose
pi
om
{10, …, 34}
andomly
uni o m.
In bo h cases, we choose
wi
om
{101, …, 150}
andomly uni o m o all
i∈[n]
.
Then we se
4.2.2 Expe imen 1
In his expe imen , we ix he numbe o jobs (m) and change he numbe o wo ke s
(n). To his end, we conside he case when
m=5
and
n={5, 10, …, 40}
. Fo each
combina ion we sol e 50 ins ances wi h a ime limi o 600s and show he a e age
solu ion imes. The esul s o his expe imen is p o ided in Figs.11 and 12.
max ∑
j∈[m]
pj
zj
s. . ∑
i∈[n]
(1−ci)xij ≥dj
zj∀j∈[m],c
c
c∈U
∑
j∈[m]
xij ≤1∀i∈[n]
x
ij
,z
j
∈{0, 1}
B
=
�∑
i∈[n]
2w
i
n
�
276
M.Goe igk, M.Khos a i
The solu ion imes p esen ed in Fig. 11 show ha all in oduced IPs pe o m
simila ly o e he gi en gene a ion me hods. I can be seen ha he p oblem
cons an ly ends o be ha de o sol e om
n=5
o
n=30
and hen solu ion imes
o all IPs dec ease sligh ly. He e, IP-4 and IP-5 (which is one o he bes also o
he selec ion p oblem) a e he as es IPs. The eason is hey ha e ewe numbe o
cons ain s.
Like he solu ion imes, Fig.12 illus a es ha IP-5 leads o he bes pe o mance
p o ile, meaning ha o mos o ins ances i is he as es IP ollowing by IP-4. In
his se ing IP-2 is he wo s IP in e ms o solu ion imes.
4.2.3 Expe imen 2
In he second expe imen o he job assignmen p oblem, we ix he numbe o
wo ke s (
n=20
) and change he numbe o jobs (
n={2, 3, …,9}
). Simila ly, o
each gi en combina ion we sol e 50 ins ances wi h a ime limi o 600s and show
0.001
0.01
0.1
1
10
100
1000
5 10 15 20 25 30 35 40
Solu ion Time
Numbe o wo ke s (n)
IP-2
IP-3
IP-4
IP-5
(a) Gen-1
0.001
0.01
0.1
1
10
100
1000
5 10 15 20 25 30 35 40
Solu ion Time
Numbe o wo ke s (n)
IP-2
IP-3
IP-4
IP-5
(b) Gen-2
Fig. 11 Job assignmen —Exp1—solu ion imes (
m=5
)
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP-2
IP-3
IP-4
IP-5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP-2
IP-3
IP-4
IP-5
(b) Gen-2
Fig. 12 Job assignmen —Exp1—pe o mance p o iles
m=5
277
Robus combina o ial op imiza ion p oblems unde budge ed…
he a e age solu ion imes. The ime pe o mance o his expe imen al se ing is
shown in Figs.13 and 14.
He e, again he same end as expe imen 1 (4.2.2) can be obse ed in e ms o
bo h solu ion imes and he co esponding pe o mance p o ile. The esul s o he
in oduced gene a ion me hods a e equi alen . Howe e , he d op o he solu ion
imes o he la ge case o ins ances a e less no iceable. Likewise, IP-5 has bo h he
bes a e age and ins ance-wise solu ion imes and he slowes IP is again IP-2.
4.3 2‑Edge‑connec ed spanning subg aph
4.3.1 Se up
In he NP-ha d 2-edge-connec ed spanning subg aph p oblem, an undi ec ed g aph
G=(V,E)
is gi en wi h edge weigh s
d
d
d
∈ℝ
|E|
+
. The objec i e is o ind a subse o
edges
E′
wi h minimum weigh such ha
G[E�]
is 2-edge-connce ed, i.e., he e a e
wo edge-disjoin pa hs be ween any pai o nodes (see, e.g., Woonghee 2004). We
0.001
0.01
0.1
1
10
100
1000
2 3 4 5 6 7 8 9
Solu ion Time
Numbe o jobs (m)
IP-2
IP-3
IP-4
IP-5
(a) Gen-1
0.001
0.01
0.1
1
10
100
1000
2 3 4 5 6 7 8 9
Solu ion Time
Numbe o jobs (m)
IP-2
IP-3
IP-4
IP-5
(b) Gen-2
Fig. 13 Job assignmen —Exp2—solu ion imes
n=20
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP-2
IP-3
IP-4
IP-5
(a) Gen-1
0
0.2
0.4
0.6
0.8
1
1.2
1 4 16 64 256 1024
Time Pe o mance
Ra io
IP-2
IP-3
IP-4
IP-5
(b) Gen-2
Fig. 14 Job assignmen —Exp2—pe o mance p o iles
n=20
278
M.Goe igk, M.Khos a i
conside a obus e sion whe e edges can ail, bu he subg aph is s ill equi ed o
emain 2-edge-connec ed.
The nominal p oblem can be o mula ed as ollows:
whe e
C
deno es he se o all cu s in he g aph G. As he e a e exponen ially many
cons ain s, we use an i e a i e p ocedu e. In “Appendix B”, we desc ibe models
IP-2, IP-3, IP-4 and IP-5 o a subse
C′⊆C
o cu s. We begine wi h
C�=�
, sol e
he co esponding o mula ion, and check i he esul ing solu ion
x
x
x
is easible wi h
espec o all cu s
C
. To check i a cu is iola ed, we sol e he ollowing IP:
I a iola ed cu can be ound, i is added o
C′
, and he obus p oblem is sol ed
again, un il con e gence is eached.
We in oduce one expe imen whe e he numbe o nodes o he gi en g aph a y.
We also se he densi y (D) o he g aph equal o 0.8.
Unlike he expe imen s on bo h he selec ion and job assignmen p oblem, we
jus in oduce on app oach o ins ance gene a ion o he cu based p oblem unde
budge ed in e dic ion unce ain y. In his case ou g aph has n nodes and m edges,
whe e
m
=D×
n(n−1)
2
. He e, o each
e∈E
we choose
de
om
{1, …, 10}
and
we
om
{5, …, 10}
andomly uni o m. Mo eo e , we se
B=15
.
4.3.2 Expe imen
In he only expe imen o he cu based p oblem, we change he numbe o nodes
and hus choose n om
{10, 12, …, 30}
. Simila ly, o each ins ance size we sol e
50 ins ances wi h a ime limi o 600s and show he a e age solu ion imes. The
ime pe o mance o his expe imen al se ing is shown in Fig.15.
min ∑
{i,j}∈E
dijxij
s. . ∑
{i,j}∈C
xij ≥2∀C∈C
x
ij
∈{0, 1} ∀{i,j}∈E
min ∑
e∈E
ye+𝜖ze
s. . zij ≥ui−uj∀{i,j}∈
E
zij ≥uj−ui∀{i,j}∈
E
1≤∑
i∈[n]
ui≤n−1
ye≥xe+ze−ce−1∀e∈
E
∑
e∈E
wece≤B
yi,ci,zi∈{0, 1
}∀
i∈[m
]
ui∈{
0, 1
}∀i∈[n]
285
Robus combina o ial op imiza ion p oblems unde budge ed…
B uns F, Goe igk M, Knus S, Schöbel A (2014) Robus load planning o ains in in e modal anspo a-
ion. OR Spec um 36(3):631–668
Buchheim C, Ku z J (2018) Robus combina o ial op imiza ion unde con ex and disc e e cos unce -
ain y. EURO J Compu Op im 6(3):211–238
Büsing C, D’and eagio anni F (2012) New esul s abou mul i-band unce ain y in obus op imiza ion.
In: In e na ional symposium on expe imen al algo i hms, pp 63–74. Sp inge
Deineko VG, Woeginge GJ (2013) Complexi y and in-app oximabili y o a selec ion p oblem in obus
op imiza ion. 4OR 11(3):249–252
Dolan Elizabe h D, Mo é Jo ge J (2022) Benchma king op imiza ion so wa e wi h pe o mance p o iles.
Ma h P og am 91:201–213
Dolgui A, Ko ale S (2012) Min–max and min–max ( ela i e) eg e app oaches o ep esen a i es selec-
ion p oblem. 4OR 10(2):181–192
Ga ey MR, Johnson DS (1979) Compu e s and in ac abili y. W. H. F eeman and Company, New Yo k
Goe igk M, Kaspe ski A, Zieliński P (2022) Robus wo-s age combina o ial op imiza ion p oblems
unde con ex second-s age cos unce ain y. J Comb Op im 43(3):497–527
Goe igk M, Lendl S (2021) Robus combina o ial op imiza ion wi h locally budge ed unce ain y. Open J
Ma h Op im 2:1–18
Goe igk M, Lendl S, Wul L (2022) On he complexi y o obus mul i-s age p oblems in he polynomial
hie a chy. a Xi p ep in a Xi : 2209. 01011
Goe igk M, Schöbel A (2016) Algo i hm enginee ing in obus op imiza ion. In: Algo i hm enginee ing,
pp 245–279. Sp inge
Kail P, Maye J (2005) S ochas ic linea p og amming, models, heo y, and compu a ion. Sp inge , New
Yo k
Kaspe ski A, Ku pisz A, Zieliński P (2015) App oximabili y o he obus ep esen a i es selec ion p ob-
lem. Ope Res Le 43(1):16–19
Kaspe ski A, Zieliński P (2016) Robus disc e e op imiza ion unde disc e e and in e al unce ain y: a
su ey. In: Robus ness analysis in decision aiding, op imiza ion, and analy ics, pp 113–143. Sp inge
Ko e B, Vygen J (2018) Combina o ial op imiza ion. Algo i hms and combina o ics. Sp inge , Be lin
Lodwick WA, Kacp zyk J (2010) Fuzzy op imiza ion: ecen ad ances and applica ions, ol 254.
Sp inge , Be lin
Poss M (2013) Robus combina o ial op imiza ion wi h a iable budge ed unce ain y. 4OR 11(1):75–92
Poss M (2018) Robus combina o ial op imiza ion wi h knapsack unce ain y. Disc e Op im 27:88–102
Tim Huh W (2004) Finding 2-edge connec ed spanning subg aphs. Ope Res Le 32(3):212–216
Yaman H (2023) Sho pape -a no e on obus combina o ial op imiza ion wi h gene alized in e al
unce ain y. Open J Ma h Op im 4:1–7
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.