Halbig, Ka in; Göß, Ad ian; Weninge , Die e
A icle — Published Ve sion
Exploi ing use -supplied Decomposi ions inside Heu is ics
Jou nal o Heu is ics
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Halbig, Ka in; Göß, Ad ian; Weninge , Die e (2025) : Exploi ing use -supplied
Decomposi ions inside Heu is ics, Jou nal o Heu is ics, ISSN 1572-9397, Sp inge US, New Yo k, NY,
Vol. 31, Iss. 4,
h ps://doi.o g/10.1007/s10732-025-09572-3
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/330213
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 ps://c ea i ecommons.o g/licenses/by/4.0/
Jou nal o Heu is ics (2025) 31:36
h ps://doi.o g/10.1007/s10732-025-09572-3
Exploi ing use -supplied Decomposi ions inside Heu is ics
Ka in Halbig1·Ad ian Göß2·Die e Weninge 1,3
Recei ed: 24 May 2024 / Re ised: 5 July 2025 / Accep ed: 4 Oc obe 2025
© The Au ho (s) 2025
Abs ac
Nume ous indus ial ields, like supply chain managemen , ace mixed-in ege op i-
miza ion p oblems on a egula basis. Such p oblems ypically show a spa se s uc u e
and a y in size, as well as complexi y. Howe e , in o de o sa is y cus ome demands,
i is c ucial o ind good solu ions o all such p oblems quickly. Cu en esea ch o en
ocuses on he de elopmen o a ailo ed app oach o one speci ic p oblem class
wi h a common s uc u e. In o ma ion supplied by e e yday use s is usually o e -
looked, bu may esul in a decomposi ion wi h weakly connec ed blocks due o he
s uc u al spa si y. Hence, we p esen h ee heu is ics o exploi decomposi ion in o -
ma ion and analyze hei alue based on he ype o decomposi ion. In pa icula , we
newly in oduce he heu is ic Dynamic Pa i ion Sea ch, enhance he Penal y Al e -
na ing Di ec ion Me hod published ea lie in a basic o m, and ex end a amewo k
om li e a u e o Decomposi ion Ke nel Sea ch. All heu is ics a e implemen ed in
he non-comme cial sol e SCIP. We examine hei pe o mance in a comp ehensi e
compu a ional s udy ac oss h ee di e en es se s. The compu a ional esul s indi-
ca e ha knowledge abou ele an decomposi ion in o ma ion can boos he solu ion
p ocess o mixed-in ege op imiza ion p oblems.
Keywo ds Mixed-in ege p og amming ·Heu is ic ·Decomposi ion ·Op imiza ion
sol e ·Supply chain managemen
BKa in Halbig
[email p o ec ed]
Ad ian Göß
[email p o ec ed]
Die e Weninge
die e .weninge @ au.de
1Depa men o Da a Science, F ied ich-Alexande -Uni e si ä E langen-Nü nbe g, Caue s . 11,
91058 E langen, Ge many
2Analy ics & Op imiza ion Lab, Uni e si y o Technology Nu embe g (UTN), Ulmens . 52i,
90443 Nu embe g, Ge many
3Depa men o Ma hema ics, F ied ich-Alexande -Uni e si ä E langen-Nü nbe g, Caue s . 11,
91058 E langen, Ge many
0123456789().: V,- ol 123
36 Page 2 o 38 K. Halbig e al.
Ma hema ics Subjec Classi ica ion 90C11 ·90C59 ·90C90 ·90B06
1 In oduc ion
Decomposi ion me hods ha e been used o sol ing linea and mixed-in ege p oblems
o o e hal a cen u y. The publica ions o Dan zig and Wol e (1960) and o Bende s
(1962/63) can be ega ded as impo an miles ones in he en i e ield o esea ch.
In addi ion, Lag angian elaxa ion (Geo ion 1974) and i s special case Lag angian
decomposi ion (Guigna d and Kim 1987) ha e played an impo an ole o many
yea s. In Soumis (1997) a su ey on di e en decomposi ion me hods is gi en. De ailed
desc ip ions o he mos impo an decomposi ion algo i hms wi h applica ions o
mixed-in ege p oblems a e gi en in Ralphs and Gala i (2005); Vande beck and Wolsey
(2010); Wolsey (2020).
When modeling p ac ical applica ions as mixed-in ege p oblems, he cons ain
ma ices a e ypically e y spa se, ha is, only ew en ies a e nonze o. In pa icula , in
MIPLIB 2017 (Gleixne e al. 2021), which comp ises 1065 ins ances o mixed-in ege
p oblems a ising om mo e han 400 dis inc applica ions, he ac ion o nonze o
en ies, he so-called densi y, anges om 10−7 o 1 (100%), bu shows an a e age
o less han 3% (see Zuse Ins i u e Be lin (2023) o mo e de ails). Such spa si y is
pa icula ly e iden in mixed-in ege supply chain models (Schewe e al. 2020). Spa se
p oblems can usually be decomposed in o loosely coupled blocks (Bo ndö e e al.
1998), which opens he possibili y o decomposi ion me hods.
Besides aking ad an age o spa si y o decomposi ion, i can be bene icial o
le e age highe -le el p oblem s uc u es. The e is a s a ic and a dynamic way on how
o p oceed in his ega d. In a s a ic app oach, ce ain a iables and cons ain s o a
model a e pe manen ly assigned o elemen s o an algo i hm. A dynamic app oach
allows a iables and cons ain s o be assigned o elemen s o an algo i hm based on
addi ional in o ma ion. On he example o Bende s decomposi ion (Bende s 1962/63),
he di ision in mas e and subp oblem can be pe o med s a ically, which is well
sui ed o speci ic p oblems such as capaci a ed acili y loca ion p oblems (Fische i
e al. 2016; Weninge and Wolsey 2023). The u iliza ion o he p oblem s uc u e
is achie ed he e by ixing he decision a iables in he mas e p oblem so ha he
emaining subp oblem is a con enien low p oblem o sol e. In con as , a dynamic
implemen a ion allows o a lexible alloca ion o a iables and cons ain s o he
mas e o subp oblem on he basis o addi ional decomposi ion in o ma ion. This
app oach is applied in so wa e packages such as CPLEX (2022) and SCIP (Bes uzhe a
e al. 2021), which p o ide in e aces o communica e decomposi ion in o ma ion,
e.g., as o a Bende s decomposi ion. We oo will pu sue he dynamic app oach in his
a icle.
One impo an componen o e icien algo i hms o sol ing mixed-in ege linea
p oblems is inding easible solu ions quickly o imp o ing al eady exis ing solu ions,
o which heu is ics play a cen al ole (Be hold 2014). Acco dingly, heu is ics a e
subdi ided in o wo ca ego ies: cons uc ion heu is ics which a emp o de e mine
a easible solu ion om sc a ch, and imp o emen heu is ics which y o imp o e a
gi en easible solu ion. We p esen h ee heu is ics, whe eby wo o he heu is ics a e
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 3 o 38 36
cons uc ion heu is ics and one heu is ic can be used bo h as a cons uc ion heu is ic
and as an imp o emen heu is ic.
In he p esen wo k we wan o deal wi h he ex en o which he p o ision o a so
called decomposi ion in o ma ion o o sho decomposi ion can be used p o i ably in
he solu ion p ocess. In p ac ice, a decomposi ion may be p o ided by he use . Such
an app oach has wo ad an ages: Fi s , he ime-consuming compu a ion o decompo-
si ion in o ma ion is omi ed and, second, he use ypically has a e y p ecise idea o
he unde lying s uc u e o he p oblem and can communica e i app op ia ely on he
basis o a decomposi ion o a pa icula heu is ic. We ocus on p o iding decomposi-
ions o heu is ics in SCIP (Bes uzhe a e al. 2021,2023) o ind solu ions as e o o
imp o e known solu ions. In addi ion o he heu is ics ha a e he ocus o his wo k,
he au ho s a e only awa e o one heu is ic named g aph induced neighbo hood sea ch
(GINS), which was ex ended in Gam a h e al. (2020) o wo k wi h a decomposi ion.
Ou con ibu ions in his publica ion consis o he de elopmen o h ee heu is-
ics ha explici ly exploi decomposi ion in o ma ion o sol e mixed-in ege linea
p oblems, he p o ision o high-pe o mance open-sou ce C implemen a ions, he
aceabili y o pa o he compu a ional esul s h ough he a ailabili y o es ins ances
and decomposi ions, and esul s om a igh in eg a ion wi h he non-comme cial
sol e SCIP.
In he nex sec ion, we begin wi h an in oduc ion o he de ini ions and no a ion used
in he emainde o he a icle. Th ee sec ions ollow, each wi h a heu is ic exploi ing
decomposi ion in o ma ion. In Sec ion 3and Sec ion 4we desc ibe wo cons uc ion
heu is ics, whe eby he i s is p esen ed o he i s ime and he second is closely
ela ed o Lag angian decomposi ion in he way i wo ks. A e ha we desc ibe in
Sec ion 5an ex ension o he ke nel sea ch amewo k, whe e he aim is o ind a subse
o a iables, he so-called ke nel, which can be le e aged o ind a p ope solu ion. This
app oach can be used bo h as a cons uc ion heu is ic and as an imp o emen heu is ic.
Nume ical esul s on all h ee heu is ics a e p esen ed and discussed in Sec ion 6.A
b ie summa y o he esul s and a sho discussion o open esea ch ques ions o
u u e wo k in Sec ion 7conclude he a icle.
2 De ini ions and no a ion o decomposi ions
Mixed-in ege p og ams (MIP) a e commonly o mula ed as op imiza ion p oblem
min cx:Ax ≥b,≤x≤u,xj∈Z o j∈I(1)
wi h a iables x∈Rn, lowe and uppe bounds , u∈(R∪{±∞})n, cons ain ma ix
A=(aij)i,j∈Rm×nand ec o b∈Rm, and objec i e di ec ion c∈Rn. Fu he ,
he e exis in eg ali y es ic ions o all a iables xjwi h j∈I⊆[n],I=∅, whe e
[n]:={1,...,n} o n∈N.
123
36 Page 4 o 38 K. Halbig e al.
Fo a numbe k≥0 we call a pa i ion D:=(D ow,Dcol)o he ows and columns
o Ain o k+1 pieces each,
D ow:=(D ow
1,...,D ow
k,L ow), Dcol:=(Dcol
1,...,Dcol
k,Lcol),
adecomposi ion o Ai D ow
q=∅,Dcol
q=∅ o q∈[k]and i i holds o all
i∈D ow
q1,j∈Dcol
q2 ha aij = 0 implies q1=q2. We call k he numbe o blocks
and each block q∈[k]is speci ied by (D ow
q,Dcol
q). Tha is, nonze o en ies a e only
allowed in a block o wi h ow/column index in L ow/Lcol. The special ows L ow and
columns Lcol, which may be emp y, a e called linking ows and linking columns o
linking cons ain s and linking a iables, espec i ely.
We use he sho cu A[I,J] o deno e he |I|-by-|J|subma ix ha a ises om he
dele ion o all en ies om Aexcep o ows Iand columns J, o nonemp y ow
and column subse s I⊆[m]and J⊆[n]. Then, we can de ine he subma ices
Aq:=A[D ow
q,Dcol
q],A ow
q:=A[L ow,Dcol
q],Acol
q:=A[D ow
q,Lcol], and A ow,col:=A[L ow,Lcol].
Respec i e es ic ions o he ec o s x,c,b,, and ua e de ined analogously.
Wi h his no a ion, he inequali y sys em Ax ≥bcan be ew i en wi h espec o
a decomposi ion Dby a sui able pe mu a ion o he ows and columns as
⎛
⎜
⎜
⎜
⎜
⎜
⎝
A10··· 0Acol
1
0A200 Acol
2
.
.
.0...0.
.
.
0··· 0AkAcol
k
A ow
1A ow
2··· A ow
kA ow,col
⎞
⎟
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎜
⎝
x1
x2
.
.
.
xk
xcol
⎞
⎟
⎟
⎟
⎟
⎟
⎠
≥⎛
⎜
⎜
⎜
⎜
⎜
⎝
b1
b2
.
.
.
bk
b ow
⎞
⎟
⎟
⎟
⎟
⎟
⎠
.
This ep esen a ion o a ma ix is also called bo de ed block diagonal o m (Bo ndö e
e al. 1998).
An example o a cons ain ma ix and i s ea anged ep esen a ion is shown in
Figu e 1. Nonze o en ies a e isualized as black do s and a e sca e ed wildly in he
o iginal a angemen , whe eas he ea anged ep esen a ion based on a decomposi ion
shows a block diagonal wi h linking ows and linking columns.
We no e ha e e y ma ix admi s a i ial decomposi ion by se ing L ow =[m]
and Lcol =[n], in which case k=0. The o he ex eme occu s i Lcol =L ow =∅,in
which case p oblem (1) b eaks down o kdecoupled subp oblems. On he one hand,
in easibili y o one such subp oblem di ec ly implies he in easibili y o (1), whe eas
on he o he hand, co esponding subsolu ions can be me ged o one o (1).
3 Dynamic pa i ion sea ch
In he ollowing we in oduce a cons uc ion heu is ic called Dynamic Pa i ion Sea ch
(DPS). Wi hou loss o gene ali y, he absence o linking a iables is assumed in his
sec ion. This is possible, because one could conside all linking a iables as a sepa a e
block and a e wa ds ecompu e he pa i ion o he cons ain s. Then, acco ding o
a decomposi ion, DPS spli s a p oblem like (1) in o independen subp oblems, one
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 5 o 38 36
Fig. 1 O iginal and ea anged ma ix o MIPLIB 2017 ins ance im ab1
o each block. Simul aneously, he linking cons ain s a e also spli acco ding o
he a iables o each block. In an i e a i e scheme, DPS ixes he minimal sha e o
hese linking cons ain s in each subp oblem o he o e all igh -hand side. In eal-
wo ld applica ions, he igh -hand side can ep esen , o example, he demands o
di e en p oduc s ha need o be supplied by se e al p oduc ion plan s (i.e., blocks)
in o al. A e sol ing he esul ing subp oblems, ei he a solu ion can be e u ned o he
pa i ion o sha es is dynamically upda ed, which led o he naming. This heu is ic is
inspi ed by an app oach p oposed by Yıldız e al. (2022) which sea ches o a pa i ion
ha belongs o an op imal solu ion.
3.1 De ini ions and e o mula ion
We s a wi h de ini ions speci ic o DPS and necessa y e o mula ions. Conside he
mixed-in ege p oblem (1) and a co esponding decomposi ion D. To simpli y he
no a ion, o each block q∈[k]we summa ize all cons ain s, bounds and in eg ali y
condi ions in
Sq:= xq:Aqxq≥bq,
q≤xq≤uq,xj∈Z o j∈I∩Dcol
q.
Thus, we can ew i e p oblem (1) based on he decomposi ion Das
min
q∈[k]
c
qxq(2a)
s. . xq∈Sq,∀q∈[k],(2b)
q∈[k]
A ow
qxq≥b ow.(2c)
No e ha p oblem (2) spli s in o kindependen subp oblems i we omi he linking
cons ain s (2c).
123
36 Page 6 o 38 K. Halbig e al.
In o de o di ide his p oblem in o independen subp oblems, a sha e o he igh -
hand side is equi ed. Thus, we de ine a ma ix P=(p1,...,pk)∈R|L ow|×k, called
pa i ion, wi h a sha e o pq∈R|L ow| o each block q∈[k] ul illing q∈[k]pq=
b ow. Hence, we can e o mula e (2) wi h espec o a pa i ion Pand ecei e
min
q∈[k]
c
qxq(3a)
s. . xq∈Sq,∀q∈[k],(3b)
A ow
qxq≥pq,∀q∈[k],(3c)
q∈[k]
pq=b ow.(3d)
No e ha he pqdesc ibe he pa i ioning o he igh -hand side b ow be ween he
single blocks. Tha is, he igh -hand side is spli be ween he blocks in o de o ul ill
cons ain (3d).
We also poin ou ha in p ac ical scena ios ypically no e e y linking cons ain
con ains a iables om e e y block. In o de o keep he no a ion simple, we do
no di e en ia e he e, as one would elimina e he emp y ows in (3c) and ix he
co esponding en y in he pa i ion o ze o.
Assuming we know a pa i ion P eas =(p eas
1,...,p eas
k)such ha p oblem (3)is
easible, we can de e mine a co esponding solu ion, which is as well a solu ion o he
o iginal p oblem (1), by sol ing he kindependen subp oblems
min c
qxq:xq∈Sq,A ow
qxq≥p eas
q.(4)
As we will explain in he nex subsec ion, DPS aims o ind such a pa i ion by dynam-
ically upda ing an ini ial guess.
3.2 Algo i hm
Le =0 deno e he i e a ion index o s a wi h and P a chosen ini ial pa i ion.
The e a e no ha d es ic ions on he pa i ion, bu he maximal ac i i y o each block
qin each linking ow i, ha is, piq ≤sup{(A ow
q)i·xq:q≤xq≤uq}should be
espec ed, in o de o ensu e possible easibili y. Ne e heless, one should keep in mind
ha he choice o he ini ial pa i ion has a huge in luence on he la e solu ion. An
ini ial pa i ion can be chosen, o example, by spli ing he igh -hand side uni o mly
o , i a ailable, based on an LP solu ion.
Then DPS checks whe he P will lead o a easible solu ion by sol ing kindepen-
den subp oblems (4) un il o each ei he a easible solu ion is ound o in easibili y
is de ec ed. I all o he ksubp oblems a e easible, a solu ion o p oblem (1) is con-
s uc ed by he conca ena ion o he ksubsolu ions. O he wise, P will no lead o a
easible solu ion o (1) and is he e o e upda ed.
In o de o ecei e a no ion on how o pe o m such an upda e, modi ied subp oblems
a e sol ed. In pa icula , slack a iables zq∈R|L ow|
≥0a e in oduced o each block
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 7 o 38 36
q∈[k], which a e summa ized in ma ix Z=(z1,...,zk). These a iables ensu e
easibili y o he cons ain s A ow
qxq≥p
q. The o iginal objec i e unc ion is eplaced
by a sum o he slack a iables zqweigh ed by a penal y pa ame e λ ∈R|L ow|
>0.This
leads o e e y block q o he subp oblem
min (λ )zq(5a)
s. . xq∈Sq,(5b)
A ow
qxq+zq≥p
q,(5c)
zq∈R|L ow|
≥0.(5d)
No e ha he penal y pa ame e λis independen o q. When we la e inc ease
i , his will e ec an in o ma ion exchange be ween he blocks. I in some blocks a
linking cons ain is iola ed, i.e., ziq >0, all blocks will a oid he iola ion o his
cons ain in he nex i e a ion.
Gi enablockq, we no e ha subp oblem (4) is easible i and only i subp oblem (5)
has an op imal solu ion wi h op imal objec i e alue ze o. Hence, i (5) has a posi i e
objec i e alue o one block q, he pa i ion and he penal y pa ame e a e upda ed.
Fo each single linking cons ain io (3d), we inspec he alue o he slack a iable
ziq in e e y block q∈[k]and dis inguish he ollowing cases:
1. I a leas one slack a iable is posi i e and a leas one is ze o, we upda e in he
ollowing way: The alue ec o ¯z
i·o he slack a iables is sub ac ed om he
subpa i ion p
i·and— o keep cons ain (3d) sa is ied— he same amoun is added
o all p
iq wi h ¯z
iq =0, i.e., o q∈[k],
p +1
iq =p
iq −¯z
iq,i ¯z
iq = 0,
p
iq +1
β∈[k]¯z
iβ,i ¯z
iq =0,(6)
whe e is he numbe o blocks wi h ¯z
iq =0. Fu he mo e, he co esponding
penal y pa ame e λ
iis inc eased o a oid he epe i i e iola ion o linking con-
s ain i, see Sec ion 3.3 o de ails.
2. I all slack a iable alues ¯z
i·a e g ea e han ze o, only he penal y pa ame e λ
i
is inc eased.
3. I all slack a iable alues ¯z
i·a e ze o, no upda e o cons ain iis necessa y.
I all coe icien s o one ow (A ow
q)i·and a iables xqa e in eg al, he co esponding
pa i ion alue p +1
iq can be ounded o an in eg al alue. Howe e , i mus be ensu ed
ha cons ain (3d) is s ill sa is ied.
A e upda ing, he i e a ion index is inc emen ed and he subp oblems (5)a e
sol ed again. This p ocess is epea ed un il p oblem (3) has a easible solu ion o
he cu en pa i ion, and hus a easible solu ion o (1) is ound, o un il a maximum
numbe To i e a ions is eached. DPS is o mally desc ibed in Algo i hm 1.
We no e ha in he special case o wo blocks and only one linking cons ain ,
a mos one upda e is necessa y. This esul s om he simple o m o he occu -
ing objec i e in subp oblem (5). In his special case he o iginal p oblem can be
123
36 Page 8 o 38 K. Halbig e al.
Algo i hm 1: Dynamic Pa i ion Sea ch
Inpu : Ini ial pa i ion P0 ul illing (3d), penal y pa ame e s λ0∈R|L ow|
>0,andT∈N.
Ou pu : A easible solu ion o p oblem (1) i one has been ound.
1 o =0,1,...,Tdo
2Fo each q∈[k], sol e subp oblem (5).
3i all subp oblems ha e an op imal objec i e alue o ze o hen
4Feasible solu ion o p oblem (1) ound. S op.
5else
6Upda e pa i ion P and penal y pa ame e s λ .
7end
8end
di ec ly decla ed as in easible i bo h slack a iables a e posi i e, bu no e ha in
he gene al case he p oblem is no necessa ily in easible i all slack a iables a e
posi i e.
When se ing up he subp oblems (5), he o iginal objec i e unc ion is comple ely
eplaced by he weigh ed sum o he slack a iables. This is necessa y o push he slack
a iables o ze o and hus ha e a p oo o he easibili y o he o iginal subp oblems (4).
Howe e , he omission o he o iginal objec i e unc ion has he e ec ha o en
in e io solu ions o (1) a e ound. To compensa e his d awback we p opose he
ollowing: I Algo i hm 1 e u ned a easible solu ion in s ep 4, we ix he pa i ion in
each subp oblem (5) o he cu en alue and he slack a iables o ze o. A e wa ds,
we eop imize he subp oblems wi h he o iginal objec i e unc ion c
qxq.
3.3 Implemen a ion de ails
In his sec ion we discuss a ew key de ails o he implemen a ion o Algo i hm 1.
DPS as p esen ed abo e sol es he subp oblems o op imali y. As his may be ime
consuming and e en subop imal solu ions su ice o an upda e o he pa i ion, we
p opose o s op he solu ion p ocess o each subp oblem as soon as we know ha i s
solu ion alue will be s ic ly posi i e. Then, a leas one addi ional upda e is needed.
This ea u e is implemen ed as a so called e en handle in SCIP, which acks he
dual bound.
In o de o simpli y he p esen a ion, we ha e assumed ha all linking cons ain s
a e o ype ‘≥’. In p ac ice, cons ain s a e o en gi en as anged ones, i.e., he e
is a le and a igh hand side. Fo his case, we ha e implemen ed wo pa i ions
Pand P and calcula e one common upda e ec o o bo h sides o no lose any
in o ma ion.
Besides upda ing he pa i ions, we also ha e o upda e he penal y pa ame e λ
i
o each linking cons ain i∈L ow. They a e ini ialized wi h alue 1 and upda ed
i wo imes in succession a leas one o he co esponding slack a iables is s ic ly
posi i e. In his case, λ
iis inc eased by he numbe o iola ed blocks mul iplied wi h
100. This upda e ule canno lead o nume ical p oblems, since in ou implemen a ion
he numbe o i e a ions is limi ed o 50 and he numbe o blocks is usually small
enough.
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 15 o 38 36
Algo i hm 4: Decomposi ion Ke nel Sea ch
Inpu : P oblem (1) wi h decomposi ion Dand zinc ∈R∪{+∞}.
Ou pu : Solu ion xnew wi h znew ≤zinc o p oblem (1) i one has been ound.
1Take he bes solu ion x∗ o (a elaxa ion o ) p oblem (1).
2Use x∗ o de e mine sub-ke nels Kτ
qand uni e hem o a ke nel K.
3Cons uc he mul i-le el bucke s Bi o i=1,...,Nb.
4 o i=1,...,Nbdo
5Add he objec i e cu o and (9) w. . . Bi o MIP(K∪Bi).
6Sol e MIP(K∪Bi) o ob ain ˜xo message “MIP(K∪Bi)is in easible”.
7i MIP(K∪Bi)is in easible hen
8Con inue wi h nex i e a ion.
9end
10 Se xnew ←˜xand znew ←c˜x.
11 Add elemen s om Biwi h non- i ial alue in ˜x o K.
12 Dele e elemen s om Kwi h i ial alue in ˜x.
13 end
implemen a ion o DKS. We conside his jus i ied o a oid he heu is ic consuming
he en i e un ime i sol ing he i s / oo node o a subp oblem is al eady p oblema ic.
A he same ime, we assume ha his limi is su icien ly la ge o e lec any po en ial
nega i e impac o DKS on he o e all solu ion p ocess.
Finally, we would like o poin ou wo ex ensions o he p ocedu e p esen ed. The
i s ex ension is based on an obse a ion on he alues o he educed cos s and he
second ex ension ies o ealize a balance be ween solu ion ime and solu ion quali y
by an adap i e MIP-gap con ol.
Loga i hmic educed cos s g ouping
An analysis o se e al es ins ances e ealed an in e es ing pa e n in he educed
cos s. Fo each a iable ype, he a iables could be di ided in o g oups wi h educed
cos s in di e en o de s o magni ude. In Figu e 3we isualize he si ua ion o he
pu e in ege and con inuous a iables o an ins ance om he SCM es se . We no e
ha almos all bina y a iables o his ins ance belonged o he ini ial ke nel, whe eas
he es showed educed cos s o ze o. To simpli y he p esen a ion on he loga i hmic
scale, alues be ween 0 and 1 a e p esen ed as 1.
Fo a maximiza ion p oblem, i is conside ed ha he highe he educed cos o a
a iable he g ea e a no ion o impo ance in he op imal solu ion, see, e.g., Angelelli
e al. (2010). In ou case, his can be applied analogously wi h low educed cos s due
o he minimiza ion p oblem. I may imply ha a iables o one g oup se e simila
pu poses and, hus, should be in es iga ed simul aneously in o de o choose he “bes ”
one.
We algo i hmically implemen ed he obse a ion on he educed cos s as ollows.
Fo each a iable ype τand block q, we compu e he maximal educed cos s max
q,τ .
The i h sub-bucke Bτ
i,q hen con ains he indices o a iables wi h educed cos s in
he in e al (( max
q,τ )(i−1)/Nb,( max
q,τ )i/Nb]. The inal mul i-le el bucke s Biagain esul
om uni ing. No e ha such a p ocedu e eplaces he bucke cons uc ion desc ibed
abo e, bu p obably leads o he ac ha he sizes o he bucke s di e g ea ly. Though,
i is no ewo hy ha he amoun o bucke s Nbcompu ed be o e s ays he same.
123
36 Page 16 o 38 K. Halbig e al.
Fig. 3 Reduced cos s o he a iables o an ins ance om SCM es se
MIP-gap con ol
We ied o igu e ou how o keep he solu ion ime o he es ic ed p oblems in
s ep (6) o DKS (Algo i hm 4) low, while main aining an imp o ing esul . An o e all
ime limi o DKS (speci ied below) is dis ibu ed uni o mly on he es ic ed p oblems
o in es iga e. I one p oblem equi es less ime, he sa ed ime is dis ibu ed among
he subsequen p oblems. In he e en ha he ime limi o a es ic ed p oblem is
eached, an adap i e adjus men o he MIP-gap is made.
Technically, we ha e implemen ed he adap i e MIP-gap con ol as ollows. As
in oduced in Sec ion 5.1, conside he numbe o bucke s Nb. We s a by de ining a
cu en gap =0, a maximal gap max ≥0, and a ac o o δ=1. I a p oblem
eaches he ime limi , we inc ease o he consecu i e p oblems by δmax/(Nb−1).
The e o e, i all p oblems hi he ime limi , he las bucke is sol ed o he maximal
gap max. Bu , i a p oblem hi s he gap limi and, hus, inishes ea lie han he ime
limi , we wan o gi e mo e ime in o de o ind a be e solu ion. He e, he ac o δ
comes in o play. We di ide δby wo e e y ime he hi limi changes om gap o ime
and ice e sa. In o he e ms, we y o ind a gap which balances he alloca ed ime
and a desi ed high solu ion quali y ia bina y sea ch.
6 Compu a ional esul s
In his sec ion we p esen compu a ional esul s o he decomposi ion heu is ics in o-
duced in Sec ion 3, Sec ion 4, and Sec ion 5. All heu is ics we e implemen ed in C
and in eg a ed as heu is ic plugin in SCIP. The code is a ailable a h ps://gi hub.com/
khalbig/decomposi ion-heu is ics (Halbig 2023).
Compu a ional se up
All p esen ed compu a ional esul s we e gene a ed on a compu e clus e using
compu e nodes wi h Xeon E3-1240 6 p ocesso s wi h 3.7 GHz and 32 GB RAM;
see E langen Na ional High Pe o mance Compu ing Cen e (NHR@FAU) (2023) o
mo e de ails. The op imiza ion p oblems a e sol ed by using SCIP 8.0.0 (Bes uzhe a
e al. 2021) linked wi h SoPlex 6.0.0 (Bes uzhe a e al. 2021)asLPsol e .
We used a ime limi o 20 minu es. To a oid in e ac ions be ween he p esen ed
algo i hms, in uns co esponding o one heu is ic he o he wo heu is ics we e deac-
i a ed. Fu he mo e, we ha e deac i a ed he only o he decomposi ion heu is ic in
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 17 o 38 36
Fig. 4 Example o .dec- o ma wi h ea anged cons ain ma ix o he MIPLIB 2017 ins ance
binka 10_1 wi h decomposi ion om Zuse Ins i u e Be lin (2023)
SCIP, namely GINS (Gam a h e al. 2020), which, howe e , is no wi hin he scope o
his a icle. Apa om ha , all pa ame e s o SCIP ha do no belong o one o he
p esen ed heu is ics ha e been le a hei de aul se ings.
P o iding Decomposi ions
Decomposi ions o p oblem ins ances can be c ea ed inside a sol e i sel .
Widesp ead and e icien me hods o his a e, o example, specialized g aph (Ba -
is a and Tamassia 1989; Bo ndö e e al. 1998; Gu wenge and Mu zel 2001; Ha a y
and P ins 1966; Hopc o and Ta jan 1973; Tu e 1966) o hype g aph pa i ioning
me hods (Ka ypis and Kuma 1998a,b). In p ac ice, howe e , he use o op imiza-
ion so wa e is ypically awa e o de ails abou he model and he unde lying p oblem
s uc u e which can gene a e an app op ia e decomposi ion. Na u ally, such a decom-
posi ion may be much mo e use ul in e ms o sa ed sol ing ime han a sol e -c ea ed
one. E en u he , one sa es compu a ion ime when i comes o he c ea ion o he
decomposi ion.
SCIP 7.0 (Gam a h e al. 2020) has been ex ended by he necessa y capabili ies o
ead decomposi ions in o a cen al s o age, so heu is ics and o he plugins can que y
hem. Classical o ma s o s o e MIPs such as .mps,.lp,o SCIP’s own .cip
o ma do no con ey decomposi ion in o ma ion o he sol e . A decomposi ion can
be en e ed o SCIP, o example, as a sepa a e .dec- ile. An example o he .dec-
o ma wi h associa ed ea anged cons ain ma ix Ais shown in Figu e 4. Such a ile
s a s wi h a sec ion abou he numbe o blocks and con inues wi h one sec ion o each
block lis ing he associa ed ow names. Finally, he special sec ion MASTERCONSS
con ains all ows belonging o he linking cons ain s L ow. A e scanning h ough
he ow labels, he column labels Dcol a e au oma ically de e mined by means o he
ow labels o comple e he decomposi ion in o ma ion.
123
36 Page 18 o 38 K. Halbig e al.
Du ing he solu ion p ocess he o iginal p oblem (1) may be changed, o example,
by dele ing ows o ixing columns in p esol e (Ach e be g e al. 2020; Gam a h e al.
2015; Gemande e al. 2020). Such model changes hen also lead o an app op ia e
adjus men o he decomposi ion in o ma ion. Mo e de ails abou he managemen o
decomposi ions in SCIP can be ound in Gam a h e al. (2020).
Tes se s
We conside h ee se s o ins ances. The i s se o ins ances is based on he
MIPLIB 2017 (Gleixne e al. 2021; Zuse Ins i u e Be lin 2023) benchma k se . This
se o iginally con ains 240 ins ances, bu we emo ed he 8 in easible ins ances since
ou heu is ics a e no designed o de ec in easibili y. Each ins ance has up o ou
decomposi ions. The i s ype o decomposi ion is gi en by he publicly a ailable
decomposi ions a Zuse Ins i u e Be lin (2023) (deno ed by “miplib2017”). The o he
h ee ypes a e gene a ed by GCG (Gam a h and Lübbecke 2010) e sion 3.0.2 using
di e en pa ame e s and a e accessible a Halbig (2023). Fo ype “plain_miplib”
de aul pa ame e s o he MIPLIB 2017 we e used, o ype “deac i a e_nonze o” he
nonze o classi ie was deac i a ed in addi ion, and o ype “h cgpa i ion” he hype -
g aph me hod was ac i a ed in addi ion. T i ial decomposi ions wi h only one block
and decomposi ions ha we e immedia ely ecognized as duplica es we e emo ed,
as well as ins ances o which only i ial decomposi ions could be de ec ed. The inal
es se con ains 216 unique ins ances wi h up o ou decomposi ions each, esul ing
in a es se wi h 694 ins ance-decomposi ion combina ions.
The second se is based on 41 eal-wo ld supply chain managemen (SCM) ins ances
supplied by ou indus y pa ne SAP SE (2023). The mos impo an componen s a e
s ock keeping, capaci y es ic ions, anspo , p oduc ion and demand ul illmen . A
mo e de ailed desc ip ion can be ound in Gam a h e al. (2019). Since hese ins ances
con ain many independen componen s (see Gam a h e al. (2015)), we selec ed only
non- i ial in ege and mixed-in ege componen s. In ou case, a componen is classi-
ied as non- i ial i i has a leas 100 a iables, including a leas one in ege a iable,
and i i canno be sol ed o op imali y wi hin 10 seconds wi h SCIP 8.0.0. To a oid
ha some o iginal ins ances a e o e ep esen ed we emo ed some o he componen s,
which belong o he same o iginal ins ances and ha e a simila size. The emaining
componen s o m ou es se o 33 SCM ins ances.
The SCM ins ances we e decomposed acco ding o ou di e en economic aspec s.
These a e ime bucke s (B), o ganiza ional uni s o he supply ne wo k (loca ions, L),
p oduc s (P) which can be aw ma e ials as well as end p oduc s, and p oduc ion
p ocess models (S) which ans o m one o mo e p oduc s in o one o mo e o he
p oduc s. The numbe o blocks is equi alen o he numbe o di e en ime bucke s,
loca ions and so on (deno ed by “max”). Since his numbe can be e y la ge, which
is no always an ad an age, we ha e also eme ged he blocks in o 2 and 4 blocks
espec i ely. So each ins ance can ha e up o 12 di e en decomposi ions, gi en by
{B,L,P,S}×{0,2,4}. A e emo ing ob ious duplica es and decomposi ions wi h
only one block we ge a es se o 322 ins ance-decomposi ion combina ions.
The hi d se con ains a i icially gene a ed supply chain managemen ins ances
based on eal-wo ld supply chain managemen models. They ep esen a ic i e com-
pany p ocu ing componen s, p oducing cellphones o di e en ypes, anspo ing o
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 19 o 38 36
Table 1 P imal-dual gap. I
ins ances a e sol ed o
op imali y, SGM’s o sol ing
ime wi h a shi o 1 a e gi en in
b acke s
#ins ances wi h p imal-dual gap
Tes se >10 % ≤10 % =0.0%
Miplib (#694) 272 177 245 (74.2s)
SCM (#322) 163 130 29 (148.0s)
Cellphone (#504) 441 63 0
dis ibu ion cen e s, and sa is ying cos ume s demand. This se con ains 56 ins ances
wi h di e en numbe o ime bucke s and cus ome s. Analogously o he SCM es
se i is decomposed in ime bucke s (B), loca ions (L) and p oduc s (P). Also he
numbe o blocks is de e mined in he same way. This es se is p o ided by SAP SE
(2023) and is publicly a ailable a SAP SE o an SAP a ilia e company (2023). We
ha e selec ed all 56 ins ances wi h disc e e ime bucke s only and wi h lo size ac o
3, and all co esponding nine ypes o decomposi ions. This esul s in a es se o 504
ins ance-decomposi ion combina ions and we e e o i he eina e as Cellphone.
Despi e he absence o use -supplied decomposi ions o MIPLIB, which pa ly
con adic s he i le o his a icle, we conside es ing on i o be aluable o wo
easons. Fi s , i p o ides an insigh in o he pe o mance o ou heu is ics beyond
he ield o supply chain managemen . Second, he ins ances and he co esponding
decomposi ions a e publicly a ailable—unlike he SCM es se —such ha o he s can
d aw compa isons wi h espec o ou esul s.
Table 1p o ides measu emen s o he di icul y o sol ing he ins ances g ouped
by es se . We conside he compa ison un wi hou p esen ed heu is ics and examine
he p imal-dual gap a he end o he sol ing p ocess (maximal 20 minu es). While
none o he ins ances in Cellphone can be sol ed o op imali y wi hin he ime limi ,
es se Miplib in pa icula also con ains ins ances ha can be sol ed, namely 245
ins ances wi h an a e age solu ion ime o 74.2 seconds.
Measu emen
In o de o e alua e algo i hmic pe o mance o he p esen ed heu is ics, we com-
pa e shi ed geome ic means o p imal in eg als, bo h o he es se as a whole
and also o insigh ul subg oups. The p imal in eg al is an absolu e measu e o he
pe o mance o heu is ics. I akes he e olu ion o he incumben solu ion o e ime
in o accoun , hus a o ing algo i hms ha ind good solu ions ea ly. Fo a de ailed
desc ip ion o he p imal in eg al see Be hold (2013). The bes known solu ion o
an ins ance as base alue o de e mine a p imal in eg al is gi en by publicly a ailable
solu ions (see Zuse Ins i u e Be lin (2023)) and/o by esul s o p e ious and o his
a icle used uns.
Fo compa ing pe o mance on se s, we compu e he shi ed geome ic mean (SGM)
o hese alues wi h a shi alue o 1. In con as o he a i hme ic mean, he shi ed
geome ic mean has he ad an age ha ex eme alues do no ha e such a s ong
in luence on he a e age. Fo u he discussion on e alua ing compu a ional esul s
wi h SGM see o example (Ach e be g 2007). Fo a b oade analysis, he agg ega ion
ope a o s max (“wo s ”), min (“bes ”), and SGM a e applied on ins ance le el, i.e.,
ac oss all a ailable decomposi ions, be o e summa izing hose again wi h he SGM.
123
36 Page 20 o 38 K. Halbig e al.
Fo e e y un ea u ing a heu is ic and se ing, he SGM o he p imal in eg als is
di ided by he one co esponding o he compa ison un. This educes he compa ison
o a single a io, whe e a alue o less han 1 indica es an imp o emen in pe o mance.
Fu he , i allows o quan i y such an imp o emen in pe cen .
To ge mo e meaning ul esul s and no dilu e hem, we clean ou da a i s . Fo
each heu is ic sepa a ely, we emo e an ins ance-decomposi ion combina ion o all
se ings used o ha heu is ic i any o he ollowing occu s: (i) SCIP has encoun e ed
p oblems ha a e beyond he con ol o he heu is ic o one se ing; (ii) he heu is ic
was no called a leas o one se ing; (iii) he p imal in eg al is less han 10−4 o
all se ings. On ins ance-decomposi ion combina ions wi h p ope y (ii) we would no
measu e he pe o mance o he heu is ic bu a he he pe o mance a iabili y o he
used compu e nodes. Ins ance-decomposi ion combina ions wi h p ope y (iii) would
lead o ex eme a ios, which do no gi e a eliable s a emen o he pe o mance.
6.1 Dynamic pa i ion sea ch
In he ollowing we analyze he pe o mance o DPS. We in es iga e wo di e en
imes a which o call he heu is ic— igh a e he p esol ing p ocess, i.e., p e- oo
(de aul ) and igh a e oo node compu a ion (lp). In he i s case, he ini ial
pa i ion is compu ed by a uni o m spli o he igh -hand side, in he second case, he
LP solu ion is a ailable and hus he ini ial pa i ion bases on i . We un each case wi h
( eop o lp_ eop ) and wi hou eop imiza ion. Thus we conside ou di e en
se ings.
Fi s , we examine he numbe o imes DPS was called on he h ee di e en es
se s, and he numbe o imes DPS success ully ound a easible solu ion. These
esul s a e gi en in Table 2. An ins ance-decomposi ion combina ion is coun ed in
column “Called” i he heu is ic was called a leas once on i . No e ha DPS can ge
called se e al imes on one ins ance-decomposi ion combina ion, as SCIP pe o ms
es a s, which abo he solu ion p ocess and s a i comple ely om sc a ch, eusing
in o ma ion om he p e ious pass. In column “Found” all ins ance-decomposi ion
combina ions a e coun ed on which DPS success ully ound a leas one easible
solu ion.
Ha ing a close look on Table 2, unning p e- oo DPS ge s called mo e o en han
a e oo . Fo example, on Miplib unning p e- oo DPS could ge called on 338 ou
o 694 ins ance-decomposi ion combina ions and a e oo on 76 ou o 694. Due o
gene al es ic ions i is no possible o call DPS in e e y case. Fo ins ance, he o iginal
p oblem is ans o med du ing he sol ing p ocess o SCIP and new cons ain s may
be added ha a e no ep esen able as a single linea cons ain (such as o bi ope
cons ain s). I such cons ain s a e linking ones, DPS canno execu e app op ia ely.
Ano he es ic ion is a high es ima ed memo y usage ha could exceed he memo y
limi due o a high numbe o blocks. He e, i is no ewo hy ha on Cellphone unning
p e- oo DPS could ge called in e e y case and also in almos all cases an accep ed
solu ion was ound. Compa ing p e- o a e - oo uns, he sol ing p ocess o he la e
migh simply no ha e eached he calling poin .
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 21 o 38 36
Table 2 Numbe o ins ances on
which DPS was called o ound
an accep ed easible solu ion
Tes se Se ing #Called #Found
Miplib (#694) de aul 338 76
eop 338 98
lp 76 24
lp_ eop 76 32
SCM (#322) de aul 182 93
eop 182 104
lp 143 71
lp_ eop 143 73
Cellphone (#504) de aul 504 482
eop 504 482
lp 430 60
lp_ eop 430 60
In 76 ou o hese 338 cases on Miplib DPS success ully ound a easible solu ion.
Ac i a ing he eop imiza ion s ep he e a e an addi ional 22 ins ance-decomposi ion
combina ions. As o he igu es in he “Found” column, we no e ha he eop imiza ion
s ep can only ind a solu ion i DPS i sel has al eady ound one be o e. Howe e ,
he i s solu ion may occasionally no be accep ed by SCIP because i s objec i e is
conside ed in ini e o he same solu ion has al eady been ound by ano he heu is ic.
In he ollowing, we e alua e he pe o mance o he heu is ic. Besides cleaning he
da a as desc ibed in he in oduc ion o his sec ion, we ocus on subse s o ins ances
o which all decomposi ion ypes o all numbe s o blocks a e a ailable. This allows
o an in-dep h analysis ega ding he sui able choice o a decomposi ion when using
DPS.
On es se Miplib, a e cleanup 46 ins ances ha ha e all ou decomposi ions a e
le . Un o una ely, in gene al no pe o mance imp o emen can be measu ed, e en i
he bes decomposi ion is selec ed. An imp o emen can be obse ed only on some
pa icula ins ances. Fo he sake o comple eness, he speci ic alues can be ound in
Table 10 in Appendix A.1. The e, a simila pa e n shows in Table 11.
Tu ning o SCM, we no e ha a e cleanup, 182 ou o 322 ins ance-decomposi ion
combina ions a e le , belonging o 21 indi idual ins ances. In Table 3, we display
he co esponding esul s by decomposi ion ype, compa ing be ween block coun s.
In gene al, all se ings seem o ha e a nega i e in luence on he solu ion p ocess when
conside ing decomposi ion ypes B o S, compa e Table 3a and Table 3d. The si ua ion
changes when ocusing on se ing de aul wi h decomposi ion ype L (Table 3b) o
on lp wi h decomposi ion ype P (Table 3c). He e, imp o emen s o up o 12% can
be obse ed, which inc eases o up o 18% when implying he bes decomposi ion as
known. We also highligh he a o owa ds ewe blocks. The mino wo sening caused
by he eop imiza ion s ep is po en ially dedica ed o he addi ional ime equi ed o
i . The high-le el analysis gi en in Tables 12 and 13 in Appendix A.1 canno con i m
his e ec , as i lacks he dis inc ion by block coun .
123
36 Page 22 o 38 K. Halbig e al.
Table 3 Resul s o DPS on
SCM, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding all
h ee block coun s: 2, 4, and
max
24maxbes
(a) decomposi ion ype B, #19 ins ances
de aul 1.29 1.61 1.67 1.24
eop 1.31 1.65 1.67 1.26
lp 1.02 1.08 1.19 1.01
lp_ eop 1.03 1.08 1.20 1.01
(b) decomposi ion ype L, #10 ins ances
de aul 0.88 0.96 0.98 0.82
eop 0.91 0.99 1.00 0.84
lp 1.00 1.02 1.28 1.00
lp_ eop 1.02 1.03 1.28 1.02
(c) decomposi ion ype P, #13 ins ances
de aul 1.54 1.48 1.52 1.47
eop 1.56 1.44 1.44 1.34
lp 0.95 0.93 1.24 0.93
lp_ eop 0.96 0.96 1.24 0.95
(d) decomposi ion ype S, #11 ins ances
de aul 2.07 1.70 1.86 1.62
eop 1.85 1.70 1.87 1.63
lp 1.29 1.19 1.33 1.19
lp_ eop 1.30 1.20 1.33 1.19
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 4 Resul s o DPS on
Cellphone, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding all
h ee block coun s: 2, 4, and
max
2 4 max bes
(a) decomposi ion ype B, #56 ins ances
de aul 1.93 1.99 1.89 1.85
eop 2.00 2.05 0.99 0.97
lp 1.06 1.05 1.03 1.03
lp_ eop 1.07 1.05 1.03 1.03
(b) decomposi ion ype L, #56 ins ances
de aul 1.95 2.01 1.86 1.84
eop 1.36 1.40 0.82 0.80
lp 1.08 1.07 1.02 1.00
lp_ eop 1.08 1.05 1.02 0.99
(c) decomposi ion ype P, #56 ins ances
de aul 2.02 2.13 1.91 1.72
eop 2.01 1.81 0.82 0.75
lp 1.39 1.64 1.03 1.01
lp_ eop 1.41 1.64 1.03 1.01
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 23 o 38 36
Table 5 Numbe o ins ances on
which PADM was called o
ound an accep ed easible
solu ion
Tes se Se ing #Called #Found
Miplib (#694) de aul 126 63
eop 126 68
lp 30 15
lp_ eop 30 16
SCM (#322) de aul 136 95
eop 136 95
lp 100 56
lp_ eop 100 56
Cellphone (#504) de aul 247 247
eop 247 247
lp 00
lp_ eop 00
Finally, we in es iga e he pe o mance on Cellphone. A e cleanup, s ill all 504
ins ance-decomposi ion combina ions a e le , belonging o 56 indi idual ins ances.
The esul s in Table 4indica e ha unning DPS a e - oo (lp and lp_ eop ) is no
bene icial. This is e en in ensi ied when unning p e- oo (de aul ). In e es ingly,
howe e , he eop imiza ion s ep in his case en o ces a la ge imp o emen o up o
18% when combined wi h he decomposi ion in he maximal numbe o blocks. In
combina ion, we deduce ha inding solu ions o max-block decomposi ions p e- oo
wi h DPS is hinde ing he solu ion p ocess o SCIP unless a eop imiza ion s ep is
in oked. This is con i med in Tables 14 and 15 in Appendix A.1.
In summa y o all es se s, he pe o mance o DPS depends s ongly on he s uc-
u e and ype o he used decomposi ion. Whe eas DPS is ine ec i e on Miplib, i can
show signi ican pe o mance imp o emen on he supply chain managemen p ob-
lems in SCM and Cellphone when combined wi h he igh block coun . Especially,
unning DPS p e- oo wi h he eop imiza ion s ep combined wi h decomposi ions
showing a na u ally maximal numbe o blocks is expec ed o suppo he solu ion
p ocess.
6.2 Penal y al e na ing di ec ion me hod
Fo he ollowing pe o mance analysis, we in es iga e wo di e en imes o calling
PADM—di ec ly a e he p esol ing p ocess, i.e., p e- oo (de aul ), and di ec ly
a e oo node compu a ion (lp). In he i s case, we ini ialize o each linking
a iable j∈Lcol he igh -hand side ξβ,θ
jwi h ze o; see Figu e 2. In he second case,
he LP solu ion is a ailable and hus ξβ,θ
jis ini ialized wi h he LP solu ion alue o he
co esponding linking a iable. Fu he mo e, we un each es case wi h ( eop o
lp_ eop ) and wi hou eop imiza ion. Thus we in es iga e ou di e en se ings.
In Table 5we obse e how o en PADM was called and ound a solu ion. This
able is s uc u ed in he same way as Table 2 o he esul s o DPS. Fo Miplib and
123
36 Page 24 o 38 K. Halbig e al.
Table 6 Resul s o PADM on
SCM, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding all
h ee block coun s: 2, 4, and max
24maxbes
(a) decomposi ion ype B, #7 ins ances
de aul 0.89 0.90 5.01 0.88
eop 0.95 0.93 5.04 0.91
lp 1.00 1.00 2.26 1.00
lp_ eop 1.03 1.01 2.25 1.00
(b) decomposi ion ype L, #9 ins ances
de aul 0.87 0.88 0.89 0.86
eop 0.89 0.90 0.90 0.87
lp 1.14 1.06 0.93 0.93
lp_ eop 1.16 1.08 0.94 0.94
(c) decomposi ion ype P, #9 ins ances
de aul 0.99 1.00 0.99 0.98
eop 1.00 1.01 1.00 0.98
lp 1.01 1.01 1.22 1.00
lp_ eop 1.01 0.98 1.23 0.97
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
SCM ou heu is ic is able o ind a easible, accep ed solu ion in 50 o 70 pe cen
o all ins ances i i was called. Fo he Cellphone es se i is no iceable ha o
decomposi ions wi h a block numbe gi en by he numbe o ime bucke s, loca ions
o p oduc s in he model (“max”), and o all decomposi ions unning a e - oo , he
heu is ic could no ge called a all. He e, he eassignmen o linking cons ain s o
one block ailed. In p inciple, his issue can be o e come by ailo ing PADM o hese
ins ances. Bu , as ou implemen a ion is supposed o be applicable o MIPs in gene al,
his is ou o scope o he p esen wo k.
Now, we e alua e he pe o mance o PADM. The esul s a e s uc u ed in he
same way as o he e alua ion o DPS in Sec ion 6.1 and he da a is also cleaned up
be o ehand.
On Miplib 124 ins ance-decomposi ion combina ions belonging o 52 indi idual
ins ances a e le a e cleanup. Un o una ely, no signi ican pe o mance imp o e-
men can be measu ed, e en i he bes decomposi ion is selec ed. Wi h se ing lp o
lp_ eop he a ios a e nea ly neu al, bu his is also due o he ac ha PADM
could ge called less o en. See Tables 16,17 in A.2 o he conc e e igu es.
The esul s o es se SCM ega ding ins ances wi h all h ee block coun s and
g ouped by decomposi ion ype a e gi en in Table 6. No e ha he e exis no such
ins ances wi h espec o decomposi ion ype S.
S a ing wi h Table 6c, PADM seems o ha e a neu al o sligh ly posi i e impac
when called wi h decomposi ions o ype P. Fo PADM unning p e- oo , we obse e
a pe o mance boos o up o 13% independen o he numbe o blocks in a decom-
posi ion o ype L, see Table 6b. Howe e , unning i a e he oo , only he na u al
maximal block decomposi ion (max) seems o allow o imp o emen . This is in con-
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 31 o 38 36
Table 14 Resul s o DPS on
Cellphone, g ouped by
decomposi ion ype. Including
all ins ances wi h a leas one
decomposi ion o he gi en ype
se ing wo s sgm bes
(a) decomposi ion ype B, #56 ins ances
de aul 2.04 1.94 1.85
eop 2.13 1.59 0.98
lp 1.06 1.05 1.03
lp_ eop 1.07 1.05 1.03
(b) decomposi ion ype L, #56 ins ances
de aul 2.07 1.94 1.84
eop 1.64 1.16 0.80
lp 1.11 1.05 1.00
lp_ eop 1.11 1.05 0.99
(c) decomposi ion ype P, #56 ins ances
de aul 2.34 2.02 1.72
eop 2.38 1.44 0.75
lp 1.64 1.33 1.01
lp_ eop 1.64 1.33 1.01
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 15 Resul s o DPS on
Cellphone. Including all
ins ances (#56) wi h a leas one
decomposi ion ype
se ing wo s sgm bes
de aul 2.38 1.96 1.68
eop 2.51 1.39 0.65
lp 1.64 1.14 0.98
lp_ eop 1.65 1.14 0.97
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 16 Resul s o PADM on Miplib, g ouped by decomposi ion ype. Including only ins ances (#13)
wi h all ou decomposi ion ypes
deac i a e_nonze os h cgpa i ion miplib2017 plain_miplib bes
de aul 1.43 1.22 1.01 1.29 1.00
eop 1.45 1.23 1.03 1.31 1.01
lp 1.00 0.99 1.00 1.00 0.99
lp_ eop 1.00 1.00 1.00 1.00 0.99
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1, by he in es iga ed me hod.
i s is p esen ed in Table 17.OnSCM, dis inguishing by decomposi ion ype and
agg ega ing di e en block coun s on ins ance le el gi es he igu es in Table 18.This
is also compu ed ac oss all decomposi ion ypes, gi ing Table 19.
Omi ing he esul s a e oo , as PADM has no been called he e, he pe o mance
spli by block coun on Cellphone is gi en in Table 20. He e, we canno obse e
123
36 Page 32 o 38 K. Halbig e al.
Table 17 Resul s o PADM on
Miplib. Including all ins ances
(#214) wi h a leas one
decomposi ion ype
se ing wo s sgm bes
de aul 1.11 1.04 0.99
eop 1.11 1.04 0.98
lp 1.02 1.01 1.01
lp_ eop 1.02 1.01 1.00
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 18 Resul s o PADM on
SCM, g ouped by
decomposi ion ype. Including
all ins ances wi h a leas one
decomposi ion o he gi en ype
se ing wo s sgm bes
(a) decomposi ion ype B, #33 ins ances
de aul 1.95 1.33 0.97
eop 1.96 1.32 0.97
lp 1.23 1.08 1.00
lp_ eop 1.24 1.08 1.00
(b) decomposi ion ype L, #25 ins ances
de aul 1.24 1.23 1.21
eop 1.06 1.04 1.02
lp 1.20 1.16 1.11
lp_ eop 1.19 1.15 1.10
(c) decomposi ion ype P, #28 ins ances
de aul 1.23 1.11 0.93
eop 1.25 1.13 0.94
lp 1.16 1.07 1.00
lp_ eop 1.17 1.08 1.00
(d) decomposi ion ype S, #28 ins ances
de aul 1.00 1.00 0.99
eop 1.00 1.00 1.00
lp 1.00 1.00 0.99
lp_ eop 1.01 1.00 0.99
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 19 Resul s o PADM on
SCM. Including all ins ances
(#33) wi h a leas one
decomposi ion ype
se ing wo s sgm bes
de aul 1.96 1.17 0.93
eop 1.96 1.16 0.92
lp 1.39 1.06 0.97
lp_ eop 1.39 1.07 0.96
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 33 o 38 36
Table 20 Resul s o PADM on
Cellphone, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding he wo
block coun s: 2 and 4
24bes
(a) decomposi ion ype B, #40 ins ances
de aul 2.34 2.40 2.31
eop 2.34 2.36 2.28
(b) decomposi ion ype L, #49 ins ances
de aul 2.25 2.27 2.23
eop 2.26 2.28 2.24
(c) decomposi ion ype P, #18 ins ances
de aul 2.20 2.21 2.19
eop 2.21 2.21 2.20
Table 21 Resul s o PADM on
Cellphone, g ouped by
decomposi ion ype. Including
all ins ances wi h a leas one
decomposi ion o he gi en ype
se ing wo s sgm bes
decomposi ion ype B, #56 ins ances
de aul 2.03 1.53 0.97
eop 2.03 1.54 0.99
decomposi ion ype L, #56 ins ances
de aul 2.13 1.61 0.97
eop 2.14 1.62 0.97
decomposi ion ype P, #56 ins ances
de aul 1.83 1.33 0.99
eop 1.83 1.33 0.99
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
Table 22 Resul s o PADM on
Cellphone. Including all
ins ances (#56) wi h a leas one
decomposi ion ype.
se ing wo s sgm bes
de aul 2.18 1.48 0.97
eop 2.19 1.49 0.97
Bold igu es indica e a pe omance inc ease, i.e., a alue less han 1,
by he in es iga ed me hod.
an imp o emen in pe o mance o one o he conside ed (sub-)se s and i is also
no ewo hy ha he a ios all all wi hin he same ange. In es iga ing he esul s in
mo e de ail, we we e able o ind a possible explana ion o his beha io : The p e-
oo heu is ic Shi -and-P opaga e (Be hold and Hendel 2015) seems o be a powe ul
ool o his kind o ins ances, since in he compa ison un wi hou ou decomposi ion
heu is ics he i s solu ion was mos ly ound by i . Compa ing he solu ion quali y,
one can see ha Shi -and-P opaga e ou sco ed PADM in all cases. E en enabling
he eop imiza ion s ep does no imp o e he si ua ion, as i was success ul in only
wo cases and o he wise he solu ion limi s ha e been eached. I migh appea ha
his is jus was ing compu a ion ime o a useless solu ion om PADM, bu he ac
is ha Shi -and-P opaga e is no longe called i a easible solu ion al eady exis s,
123
36 Page 34 o 38 K. Halbig e al.
such as ed in by PADM. Thus, he pe o mance deg ada ion comes mainly om dis-
abling Shi -and-P opaga e, which also explains he consis en deg ada ion ac oss he
ypes o decomposi ions, since Shi -and-P opaga e is independen o decomposi ion
in o ma ion.
Again, Table 21 and Table 22 p o ide a concise e sion o he esul s ac oss decom-
posi ion ype and o e all.
A.3 Compu a ional esul s on DKS spli by decomposi ion
Following he de aul o de o Miplib,SCM, hen Cellphone, he esul s o all h ee
es se s g ouped by decomposi ion ype and analyzed o ins ances showing all such
a e gi en in Tables 23,25 and 28. When conside ing all ins ances on bo h supply chain
es se s, he igu es a e gi en in Tables 26 and 29. Summa ies a e p o ided in Tables
24,27 and 30, espec i ely.
Table 23 Resul s o DKS on Miplib, g ouped by decomposi ion ype. Including only ins ances (#60) wi h
all ou decomposi ion ypes
deac i a e_nonze os h cgpa i ion miplib2017 plain_miplib bes
dks 1.17 1.17 1.14 1.17 1.12
ks 1.04 1.04 1.04 1.04 1.03
Table 24 Resul s o DKS on
Miplib. Including all ins ances
(#215) wi h a leas one
decomposi ion ype.
se ing wo s sgm bes
dks 1.10 1.07 1.04
ks 1.03 1.02 1.02
Table 25 Resul s o DKS on
SCM, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding all
h ee block coun s: 2, 4, and
max
24maxbes
(a) decomposi ion ype B, #14 ins ances
dks 1.01 1.00 1.01 1.00
ks 1.54 1.54 1.54 1.54
(b) decomposi ion ype L, #5 ins ances
dks 1.02 1.03 1.02 1.02
ks 1.06 1.07 1.07 1.06
(c) decomposi ion ype P, #9 ins ances
dks 1.02 1.01 1.02 1.00
ks 1.02 1.02 1.02 1.02
(d) decomposi ion ype S, #9 ins ances
dks 1.01 1.01 1.02 1.00
ks 1.03 1.02 1.02 1.02
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 35 o 38 36
Table 26 Resul s o DKS on
SCM g ouped by decomposi ion
ype. Respec ing all ins ances
ha ing a leas 2, 4, o max
blocks
se ing wo s sgm bes
(a) decomposi ion ype B, #33 ins ances
dks 1.01 1.00 1.00
ks 1.20 1.20 1.20
(b) decomposi ion ype L, #25 ins ances
dks 1.01 1.00 1.00
ks 1.27 1.27 1.26
(c) decomposi ion ype P, #28 ins ances
dks 1.02 1.01 1.00
ks 1.01 1.01 1.01
(d) decomposi ion ype S, #28 ins ances
dks 1.01 1.00 1.00
ks 1.01 1.01 1.01
Table 27 Resul s o DKS on
SCM. Including all ins ances
(#33) wi h a leas one
decomposi ion ype
se ing wo s sgm bes
dks 1.02 1.00 1.00
ks 1.20 1.20 1.19
Table 28 Resul s o DKS on
Cellphone, g ouped by
decomposi ion ype. Including
only ins ances wi h
decomposi ions yielding all
h ee block coun s: 2, 4, and
max
24maxbes
(a) decomposi ion ype B, #40 ins ances
dks 1.01 1.01 1.01 1.01
ks 1.20 1.20 1.20 1.20
(b) decomposi ion ype L, #40 ins ances
dks 1.01 1.01 1.01 1.01
ks 1.20 1.20 1.20 1.20
(c) decomposi ion ype P, #39 ins ances
dks 1.01 1.01 1.01 1.01
ks 1.21 1.21 1.21 1.21
Table 29 Resul s o DKS on
Cellphone g ouped by
decomposi ion ype. Respec ing
all ins ances ha ing a leas 2, 4,
o max blocks
se ing wo s sgm bes
(a) decomposi ion ype B, #56 ins ances
dks 1.01 1.01 1.00
ks 1.14 1.14 1.14
(b) decomposi ion ype L, #56 ins ances
dks 1.01 1.01 1.01
ks 1.14 1.14 1.14
(c) decomposi ion ype P, #56 ins ances
dks 1.01 1.01 1.00
ks 1.14 1.14 1.14
123
36 Page 36 o 38 K. Halbig e al.
Table 30 Resul s o DKS on
Cellphone. Including all
ins ances (#56) wi h a leas one
decomposi ion ype
se ing wo s sgm bes
dks 1.01 1.01 1.00
ks 1.14 1.14 1.14
Acknowledgemen s The au ho s would like o hank SAP o i s long- e m suppo and o p o iding es
ins ances. They also hank G ego Hendel o implemen ing he managemen o decomposi ions in SCIP
and gene a ing decomposi ions o MIPLIB ins ances. Finally, he au ho s hank Alexande Ma in and
G ego Hendel o e iewing a i s d a .
Funding Open Access unding enabled and o ganized by P ojek DEAL. No unding was ecei ed o assis
wi h he p epa a ion o his a icle.
Decla a ions
Compe ing in e es s 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 icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included
in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I
ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed
by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he
copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
Ach e be g, T.: Cons ain In ege P og amming. PhD hesis. Technische Uni e si ä , Be lin (2007)
Ach e be g, T., Bixby, R.E., Gu, Z., Ro hbe g, E., Weninge , D.: P esol e educ ions in mixed in ege
p og amming. INFORMS J. Compu . 32(2), 473–506 (2020). h ps://doi.o g/10.1287/ijoc.2018.0857
Alie , I., Loe a, J.A.D., Eisenb and, F., Oe el, T., Weisman el, R.: The suppo o in ege op imal solu ions.
SIAM J. Op im. 28(3), 2152–2157 (2018). h ps://doi.o g/10.1137/17M1162792
Angelelli, E., Mansini, R., Spe anza, M.G.: Ke nel sea ch: A gene al heu is ic o he mul i-dimensional
knapsack p oblem. Compu e s & Ope a ions Resea ch, 37(11): 2017–2026, (2010). ISSN 0305-
0548. h ps://doi.o g/10.1016/j.co .2010.02.002.h ps://www.sciencedi ec .com/science/a icle/pii/
S0305054810000328
Angelelli, E., Mansini, R., Spe anza, M.G.: Ke nel sea ch: A new heu is ic amewo k o po olio selec ion.
Compu . Op im. Appl. 51(1), 345–361 (2012). h ps://doi.o g/10.1007/s10589-010-9326-6
Ba is a, G.D., Tamassia, R.: Inc emen al Plana i y Tes ing (Ex ended Abs ac ). In 30 h Annual Symposium
on Founda ions o Compu e Science, Resea ch T iangle Pa k, No h Ca olina, USA, 30 Oc obe - 1
No embe 1989, pages 436–441, (1989). h ps://doi.o g/10.1109/SFCS.1989.63515
Bende s, J.: Pa i ioning p ocedu es o sol ing mixed- a iables p og amming p oblems. Nume ische Ma h-
ema ik, 4:238–252, (1962/63). h p://eudml.o g/doc/131533
Be hold, T.: Measu ing he impac o p imal heu is ics. Ope a ions Resea ch Le e s, 41(6): 611–614,
(2013). ISSN 0167-6377. h ps://doi.o g/10.1016/j.o l.2013.08.007.h ps://www.sciencedi ec .com/
science/a icle/pii/S0167637713001181
Be hold, T.: Heu is ic algo i hms in global MINLP sol e s. PhD hesis, (2014). h p://www.zib.de/be hold/
Be hold2014.pd
123
Exploi ing use -supplied Decomposi ions inside Heu is ics Page 37 o 38 36
Be hold, T., Hendel, G.: Shi -and-p opaga e. Jou nal o Heu is ics 21(1), 73–106 (2015). h ps://doi.o g/
10.1007/s10732-014-9271-0
Bes uzhe a, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., an Doo nmalen, J., Ei le , L.,
Gaul, O., Gam a h, G., Gleixne , A., Go wald, L., G aczyk, C., Halbig, K., Hoen, A., Hojny, C., an de
Huls , R., Koch, T., Lübbecke, M., Mahe , S.J., Ma e , F., Mühme , E., Mülle , B., P e sch, M.E.,
Reh eld , D., Schlein, S., Schlösse , F., Se ano, F., Shinano, Y., So anac, B., Tu ne , M., Vige ske,
S., Wegscheide , F., Wellne , P., Weninge , D., Wi zig. J.: The SCIP Op imiza ion Sui e 8.0. Technical
epo , Op imiza ion Online, Decembe 2021. h p://www.op imiza ion-online.o g/DB_HTML/2021/
12/8728.h ml
Bes uzhe a, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., an Doo nmalen, J., Ei le , L.,
Gaul, O., Gam a h, G., Gleixne , A., Go wald, L., G aczyk, C., Halbig, K., Hoen, A., Hojny, C.,
an de Huls , R., Koch, T., Lübbecke, M., Mahe , S.J., Ma e , F., Mühme , E., Mülle , B., P e sch,
M.E., Reh eld , D., Schlein, S., Schlösse , F., Se ano, F., Shinano, Y., So anac, B., Tu ne , M.,
Vige ske, S., Wegscheide , F., Wellne , P., Weninge , D., Wi zig. J.: Enabling Resea ch h ough he
SCIP Op imiza ion Sui e 8.0. ACM T ans. Ma h. So w., 49(2), jun (2023). ISSN 0098-3500. h ps://
doi.o g/10.1145/3585516
Bo ndö e , R., Fe ei a, C.E., Ma in, A.: Decomposing Ma ices in o Blocks. SIAM J. Op im. 9(1), 236–
269 (1998)
Boyd, S., Pa ikh, N., Chu, E., Pelea o, B., Ecks ein, J.: Dis ibu ed op imiza ion and s a is ical lea ning
ia he al e na ing di ec ion me hod o mul iplie s. Found. T ends Mach. Lea n. 3(1), 1–122 (2011).
h ps://doi.o g/10.1561/2200000016. (ISSN 1935-8237)
Ch á al, V.: Linea p og amming. A Se ies o books in he ma hema ical sciences. F eeman, New Yo k (N.
Y.), (1983). ISBN 0-7167-1195-8. h p://opac.in ia. / eco d=b1104676. Réimp essions : 1999, 2000,
2002
CPLEX. IBM ILOG CPLEX Op imiza ion S udio CPLEX Use ’s Manual, (2022). h ps://www.ibm.com/
docs/en/icos/22.1.1? opic=op imize s-use s-manual-cplex
Dan zig, G.B., Wol e, P.: Decomposi ion P inciple o Linea P og ams. Ope . Res. 8(1), 101–111 (1960).
h ps://doi.o g/10.1287/op e.8.1.101. (ISSN 0030-364X)
E langen Na ional High Pe o mance Compu ing Cen e (NHR@FAU) . Woody h oughpu clus-
e (Tie 3), las accessed on 2023-06-20. h ps://hpc. au.de/sys ems-se ices/documen a ion-
ins uc ions/clus e s/woody-clus e /
Fische i, M., Ljubi´c, I., Sinnl, M.: Bende s decomposi ion wi hou sepa abili y: A compu a ional s udy o
capaci a ed acili y loca ion p oblems. Eu opean Jou nal o Ope a ional Resea ch, 253 (3):557 – 569
(2016). ISSN 0377-2217. h ps://doi.o g/10.1016/j.ejo .2016.03.002.h p://www.sciencedi ec .com/
science/a icle/pii/S0377221716301126
Gam a h, G., Lübbecke, M.E.: Expe imen s wi h a gene ic Dan zig-Wol e decomposi ion o in ege p o-
g ams. In P. Fes a, edi o , Expe imen al Algo i hms, pages 239–252, Be lin, Heidelbe g, (2010).
Sp inge Be lin Heidelbe g
Gam a h, G., Koch, T., Ma in, A., Mil enbe ge , M., Weninge , D.: P og ess in p esol ing o mixed
in ege p og amming. Ma hema ical P og amming Compu a ion 7(4), 367–398 (2015). h ps://doi.
o g/10.1007/s12532-015-0083-5. (ISSN 1867-2957)
Gam a h, G., Gleixne , A., Koch, T., Mil enbe ge , M., Kniasew, D., Schlögel, D., Ma in, A., Weninge ,
D.: Tackling indus ial-scale supply chain p oblems by mixed-in ege p og amming. J. Compu . Ma h.
37, 866–888 (2019). h ps://doi.o g/10.4208/jcm.1905-m2019-0055
Gam a h, G., Ande son, D., Bes uzhe a, K., Chen, W.-K., Ei le , L., Gasse, M., Gemande , P., Gleixne ,
A., Go wald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Mahe , S.J., Ma e ,
F., Mil enbe ge , M., Mühme , E., Mülle , B., P e sch, M.E., Schlösse , F., Se ano, F., Shinano, Y.,
Taw ik, C., Vige ske, S., Wegscheide , F., Weninge , D., Wi zig, J.: The SCIP Op imiza ion Sui e
7.0. Technical epo , Op imiza ion Online, Ma ch (2020). h p://www.op imiza ion-online.o g/DB_
HTML/2020/03/7705.h ml
Geißle , B., Mo si, A., Schewe, L., Schmid , M.: Penal y al e na ing di ec ion me hods o mixed-in ege
op imiza ion: A new iew on easibili y pumps. SIAM J. Op im. 27(3), 1611–1636 (2017). h ps://
doi.o g/10.1137/16M1069687. (ISSN 2192-4414)
Gemande , P., Chen, W.-K., Weninge , D., Go wald, L., Gleixne , A., Ma in, A.: Two- ow and wo-column
mixed-in ege p esol e using hashing-based pai ing me hods. EURO Jou nal on Compu a ional Op i-
miza ion 8(3), 205–240 (2020). h ps://doi.o g/10.1007/s13675-020-00129-6. (ISSN 2192-4414)
123
36 Page 38 o 38 K. Halbig e al.
Geo ion, A.M.: App oaches o In ege P og amming, chap e Lag angean elaxa ion o in ege p og am-
ming, pages 82–114. Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, (1974). ISBN 978-3-642-00740-
8. h ps://doi.o g/10.1007/BFb0120690
Gleixne , A., Hendel, G., Gam a h, G., Ach e be g, T., Bas ubbe, M., Be hold, T., Ch is ophel, P.M., Ja ck,
K., Koch, T., Linde o h, J., Lübbecke, M., Mi elmann, H.D., Ozyu , D., Ralphs, T.K., Sal agnin,
D., Shinano, Y., MIPLIB.: Da a-D i en Compila ion o he 6 h Mixed-In ege P og amming Lib a y.
Ma h. P og am. Compu . 2021,(2017). h ps://doi.o g/10.1007/s12532-020-00194-3
Guas a oba, G., Sa elsbe gh, M., Spe anza, M.G.: Adap i e ke nel sea ch: A heu is ic o sol ing
mixed in ege linea p og ams. Eu opean Jou nal o Ope a ional Resea ch, 263 (3):789–804, (2017).
ISSN 0377-2217. h ps://doi.o g/10.1016/j.ejo .2017.06.005.h ps://www.sciencedi ec .com/science/
a icle/pii/S0377221717305234
Guigna d, M., Kim, S.: Lag angean decomposi ion: A model yielding s onge Lag angean bounds.
Ma hema ical P og amming 39(2), 215–228 (1987). h ps://doi.o g/10.1007/BF02592954. (ISSN
1436-4646)
Gu wenge , C., Mu zel, P.: G aph D awing: 8 h In e na ional Symposium, GD 2000 Colonial Williamsbu g,
VA, USA, Sep embe 20–23, 2000 P oceedings, chap e A Linea Time Implemen a ion o SPQR-
T ees, pages 77–90. Sp inge Be lin Heidelbe g, Be lin, Heidelbe g, (2001). ISBN 978-3-540-44541-8.
h ps://doi.o g/10.1007/3-540-44541-2_8
Ha a y, F., P ins, G.: The block-cu poin - ee o a g aph. Publica iones Ma hema icae Deb ecen 13, 103–107
(1966)
Hopc o , J.E., Ta jan, R.E.: Di iding a g aph in o iconnec ed componen s. SIAM J. Compu . 2(3), 135–
158 (1973). h ps://doi.o g/10.1137/0202012
Halbig, K.: Decomposi ion Heu is ics, June (2023). h ps://gi hub.com/khalbig/decomposi ion-heu is ics.
[da ase , so wa e]
Ka ypis, G., Kuma , V.: Mul ile el k-way Hype g aph Pa i ioning. In In P oceedings o he Design and
Au oma ion Con e ence, pages 343–348, (1998a)
Ka ypis, G., Kuma , V.: hMe is: A Hype g aph Pa i ioning Package, Ve sion 1.5.3, (1998b)
Ralphs, T.K., Gala i, M.V.: Decomposi ion in in ege linea p og amming. In J. Ka lo , edi o , In ege
P og amming: Theo y and P ac ice, pages 57–110. CRC P ess, (2005). h ps://co al.ie.lehigh.edu/
~ ed/ iles/pape s/DECOMP04.pd
SAP SE. SAP So wa e Solu ions | Business Applica ions and Technology, las accessed on 2023-06-20.
h ps://www.sap.com
SAP SE o an SAP a ilia e company. MILP Benchma ks CellphoneCo., Jan. (2023). h ps://gi hub.com/
SAP-samples/ibp-sop-benchma ks-milp-cellphoneco. [da ase ]
Schewe, L., Schmid , M., Weninge , D.: A Decomposi ion Heu is ic o Mixed-In ege Supply Chain P ob-
lems. Ope a ions Resea ch Le e s, 48(3): 225–232, (2020). ISSN 0167-6377. h ps://doi.o g/10.1016/
j.o l.2020.02.006.h ps://www.sciencedi ec .com/science/a icle/pii/S0167637720300249
Soumis, F.: Decomposi ion and Column Gene a ion. In Anno a ed Bibliog aphies in Combina o ial Op i-
miza ion. Chap e 8. A Wiley-in e science publica ion. Wiley, (1997). ISBN 9780471965749. h ps://
books.google.de/books?id=jz4ZAQAAIAAJ
Tu e, W.T.: Connec i i y in g aphs. Ma hema ical Exposi ions, 15, (1966)
Vande beck, F., Wolsey, L.A.: Re o mula ion and Decomposi ion o In ege P og ams. Sp inge , Be lin
Heidelbe g, Be lin, Heidelbe g (2010). h ps://doi.o g/10.1007/978-3-540-68279-0_13 . (ISBN 978-
3-540-68279-0)
Weninge , D., Wolsey, L.A.: Bende s- ype b anch-and-cu algo i hms o capaci a ed acili y loca ion wi h
single-sou cing. Eu opean Jou nal o Ope a ional Resea ch, (2023). ISSN 0377-2217. h ps://doi.o g/
10.1016/j.ejo .2023.02.042.h ps://www.sciencedi ec .com/science/a icle/pii/S0377221723001935
Wolsey, L.A.: In ege P og amming. John Wiley and Sons, L d, (2020). ISBN 9781119606475. h ps://doi.
o g/10.1002/9781119606475.h ps://onlinelib a y.wiley.com/doi/book/10.1002/9781119606475
Yıldız, B., Boland, N., Sa elsbe gh, M.: Decomposi ion b anching o mixed in ege p og amming. Ope .
Res. 70(3), 1854–1872 (2022). h ps://doi.o g/10.1287/op e.2021.2210
Zuse Ins i u e Be lin. MIPLIB 2017 – The Mixed In ege P og amming Lib a y, las accessed on 2023-06-
20. h ps://miplib.zib.de/. [da ase ]
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
