A Compa a i e S udy o Fo mula ions and Solu ion Me hods o he
Disc e e O de ed p-Median P oblem
Ma ine Labb´ea, Diego Ponceb,c, Jus o Pue ob,c
aCompu e Science Depa men , Uni e si ´e Lib e de B uxelles
bIMUS, Ins i u o de Ma em´a icas, Uni e sidad de Se illa
cDepa amen o de Es ad´ıs ica e In es igaci´on Ope a i a, Uni e sidad de Se illa
Abs ac
This pape p esen s se e al new o mula ions o he Disc e e O de ed Median P oblem (DOMP) based
on i s simila i y wi h some scheduling p oblems. Some o he new o mula ions p esen a conside ably
smalle numbe o cons ain s o de ine he p oblem wi h espec o some p e iously known o mula ions.
Fu he mo e, he lowe bounds p o ided by hei linea elaxa ions imp o e he ones ob ained wi h p e ious
o mula ions in he li e a u e e en when s eng hening is no applied. We also p esen a polyhed al s udy
o he assignmen poly ope o ou igh es o mula ion showing i s p oximi y o he con ex hull o he
in ege solu ions o he p oblem. Se e al esolu ion app oaches, among which we men ion a b anch and cu
algo i hm, a e compa ed. Ex ensi e compu a ional esul s on wo amilies o ins ances, namely andomly
gene a ed and aken om Beasley’s OR-lib a y, show he powe o ou me hods o sol ing DOMP.
Keywo ds: disc e e mul i acili y loca ion, MIP o mula ions, o de ed median p oblem
1. In oduc ion
Recognizing he need o mo e lexible logis ic models, Nickel [13] p oposed he Disc e e O de ed Median
Loca ion P oblem (DOMP) which could be used o model di e en loca ions p oblems, as he p-median o
he p-cen e . I is a lexible o mula ion based on applying an o de ed weigh ed a e aging ope a o o he
cos s as hey appea in he solu ion and aking hem in o accoun wi h a sui able n- ec o λ.
Gi en a ec o o weigh s, he o de ed weigh ed a e age o n eal numbe s is ob ained by i s anking
hose numbe s by nondec easing o de and hen compu ing he scala p oduc o he anked alloca ion cos
ec o and he weigh ec o , see e.g. Nickel and Pue o [14].
Conside a se o clien s and a se o candida e loca ions whe e some acili y can be es ablished. Fu he
we a e gi en he cos s o alloca ing clien s o acili ies. DOMP consis s in choosing p acili y loca ions
and assigning each clien o a acili y wi h smalles alloca ion cos in o de o minimize a special objec i e
unc ion he so called o de ed median unc ion. Gi en a ec o o weigh s, his unc ion consis s in an
o de ed weigh ed a e age o he alloca ion cos s, namely i so s hese cos s in non-dec easing sequence and
hen i pe o ms he scala p oduc o his so ob ained so ed cos ec o wi h he gi en ec o o weigh s.
This objec i e unc ion has been widely applied in he ield o loca ion analysis and dis ibu ion models
(Ma ´ın e al. [10], Kalcsics e al. [9] and Pue o e al. [17]). In addi ion, i has he po en ial o yield new
models o o de s a is ics embedded wi hin ma hema ical p og amming o mula ions; hus enla ging he
applica ions o op imiza ion ools o he esolu ion o s a is ical p oblems in da a analysis.
DOMP is known o be NP-ha d, see Nickel and Pue o [14].
The i s o mula ion o DOMP, p oposed by Nickel [13] consis s in an in ege nonlinea p oblem. Then,
Boland e al. [3] p opose se e al linea iza ion o Nickel’s model.
Email add esses: [email p o ec ed] (Ma ine Labb´e), [email p o ec ed] (Diego Ponce), [email p o ec ed] (Jus o Pue o)
P ep in submi ed o Else ie May 18, 2016
Ins ances wi h up o 30 clien s could be sol ed o op imali y by Boland e al. [3]. Fu he , i clien s and
acili y loca ions coincide and i he alloca ion cos o a clien o i sel is equal o ze o ( he so-called ee sel
se ice), hen ins ances wi h up o 100 clien s could be sol ed by Ma ´ın e al. [10, 11]. We obse e ha in
all p e iously conside ed o mula ions he gaps wi h espec o he linea p og amming elaxa ions o hose
models a e a he la ge, as men ioned in all hose pape s.
In his pape , we p opose new o mula ions o DOMP and we de elop a heo e ical compa ison o he
lowe bounds ob ained om hei LP- elaxa ions and show ha ou new o mula ions a e a he igh . Ou
heo e ical esul s also a emp o shed some ligh on he polyhed al s uc u e o he new o mula ion based
on scheduling cons ain s. We conclude wi h ex ensi e compu a ional expe imen s o compa e he espec i e
e iciency o hese o mula ions.
Fo he ease o p esen a ion, we assume in some cases in his pape ha he clien and acili y loca ion
se s coincide. Howe e , i is impo an o ema k ha all he models and esul s p esen ed ca y ou o he
gene al case in which clien and acili y loca ion may di e since we do no impose ha he cos o alloca ing
a clien o i sel is equal o ze o.
The emaining pape is o ganized as ollows: in Sec ion 2 we de ine he p oblem and some p e ious
o mula ions. Nex , we p esen new o mula ions o he DOMP. In addi ion, we analyze he ela ionship
be ween he poly opes o he p e iously known o mula ions o his p oblem and we iden i y ace s o he
ela ed assignmen poly ope in Sec ion 3. Finally, some compu a ional expe imen s a e epo ed in Sec ion
4.
2. The p oblem and some o mula ions
Le Ibe a se o npoin s which a he same ime ep esen clien s and po en ial acili y loca ions.
The cos o se ing clien i’s demand om acili y jis deno ed by Cij and a acili y can se e as many
clien s as possible, i.e. acili ies a e uncapaci a ed.
The Disc e e O de ed Median P oblem (DOMP ) consis s in
(i) de e mining a subse Jo p acili y loca ions, J⊂I, o open and
(ii) assigning clien s o closes open acili ies in o de o minimize he o de ed median objec i e unc ion
de ined as ollows.
Gi en he se Jo popen acili ies, le ci(J) ep esen s he cos o alloca ing clien i o some acili y in J
such ha ci(J) = min
j∈JCij.
Now le us ank he cos s ci(J), i∈Iby non-dec easing o de o hei alues. These o de ed cos s a e
deno ed by ck
≤(J) and e i y
c1
≤(J)≤ · · · ≤ cn
≤(J).
Then, gi en a ec o λ= (λk)n
k=1 sa is ying λk≥0, k = 1, . . . , n, he DOMP objec i e unc ion, also
called o de ed median unc ion, is de ined as
n
X
k=1
λkck
≤(J).(1)
No e ha his objec i e unc ion p o ides a e y gene al pa adigm o encompass s anda d and new
loca ion models. Fo ins ance, i λ1=· · · =λn= 1 we ob ain he median objec i e, i λ1=λ2=· · · =
λn−1= 0, λn= 1 we ob ain he cen e objec i e, i λ1=λ2=· · · =λn−1=α, λn= 1 we ob ain a con ex
combina ion o median and cen e objec i es (cen dian), e ce e a.
We de ine he p- acili y Disc e e O de ed Median P oblem as de e mining he subse J, o p acili ies o
open in o de o minimize he o de ed median unc ion:
min
J⊂I:|J|=p
n
X
k=1
λkck
≤(J).(DOMP)
2
2.1. Th ee-index o mula ion
The o mula ion ha we p esen below, deno ed by (DOMP1), was in oduced by Boland e al. [3]. I
uses h ee-index a iables xk
ij such ha xk
ij = 1, i clien iis se ed by acili y jand cos ck(J) = Cij is he
k- h smalles in he o de ed sequence c≤(J) and xk
ij = 0 o he wise. Fu he , i also uses loca ion a iables
yjsuch ha yj= 1 i j∈Jand yj= 0 o he wise.
I xk
ij = 1, we say ha alloca ion o clien i o acili y jis in posi ion k, o ha couple ij is in posi ion k.
(DOMP1) min
n
X
i=1
n
X
j=1
n
X
k=1
λkCijxk
ij (2)
s. .
n
X
j=1
n
X
k=1
xk
ij = 1 i= 1, . . . , n (3)
n
X
i=1
n
X
j=1
xk
ij = 1 k= 1, . . . , n (4)
n
X
k=1
xk
ij ≤yji, j = 1, . . . , n (5)
n
X
j=1
yj=p(6)
n
X
i=1
n
X
j=1
Cijxk−1
ij ≤
n
X
i=1
n
X
j=1
Cijxk
ij k= 2,· · · , n (7)
xk
ij ∈ {0,1}i, j, k = 1, . . . , n (8)
yj∈ {0,1}j= 1, . . . , n (9)
By means o (3) we ensu e ha each loca ion is se ed by exac ly one acili y. In he same way, in each
posi ion he e mus be exac ly one alloca ion (4). We know ha a clien can be alloca ed o a acili y only
i his acili y is open, i.e. xk
ij ≤yj o all i, j, k. Fu he mo e, each alloca ion o clien o acili y can be
placed in a mos one posi ion. Hence, xk
ij ≤yjcan be s eng hened yielding cons ain (5). The equali y
cons ain (6) implies ha he e a e exac ly popen acili ies. Inequali y (7) imposes ha he alloca ion cos
in posi ion k−1 canno be g ea e han he one in posi ion k. Finally, he a iables a e bina y, see (8) and
(9).
2.2. Two-index o mula ion
This o mula ion(DOMP2) was desc ibed o he i s ime in Pue o [16] and Ma ´ın e al. [10] and la e
applied o a hub p oblem in Pue o e al. [17]. I conside s a ec o ha con ains all he di e en alues in
he cos ma ix C, augmen ed wi h ze o i i is no p esen in ma ix C, as i is explained below.
Le Cbe a ma ix and assume ha i con ains Gdi e en alues such ha cij >0. Then, he (G+ 1)-
ec o c(.)is cons uc ed as ollows
c(0) = 0 < c(1) < c(2) <· · · < c(G−1) < c(G)= max{Cij :i, j = 1, . . . , n}
To o mula e he p oblem we need o de ine he ollowing bina y a iables. Va iable xij = 1 i clien
iis se ed by acili y jand 0 o he wise, a iable yj= 1 i j∈Jand 0 o he wise and a iable ukh = 1
i he k- h smalles alloca ion cos is g ea e han c(h−1) and 0 o he wise. Fu he , we se uk0= 1 and
ukG+1 = 0, k = 1, . . . , n.
3
The p oblem o sol e is
(DOMP2) min
n
X
k=1
G
X
h=1
λk(c(h)−c(h−1))ukh (10)
s. .
n
X
j=1
yj=p(11)
n
X
j=1
xij = 1 i= 1, . . . , n (12)
xij ≤yji, j = 1, . . . , n (13)
ukh ≥ukh+1 k= 1, . . . , n, h = 1, . . . , G −1 (14)
uk+1h≥ukh k= 1, . . . , n −1, h = 1, . . . , G (15)
n
X
i=1
n
X
j=1:
Cij >c(h−1)
xij =
n
X
k=1
ukh h= 1, . . . , G (16)
xij ∈ {0,1}i, j = 1, . . . , n (17)
ukh ∈ {0,1}k= 1, . . . , n, h = 1, . . . , G (18)
yj∈ {0,1}j= 1, . . . , n. (19)
The objec i e unc ion (10) is equi alen o (1). Assume ha he k- h smalles alloca ion cos is equal
o c(hk) o some hk hen by he de ini ion o he a iable ukhk
G
X
h=1
(c(h)−c(h−1))ukh =
hk
X
h=1
(c(h)−c(h−1)) = c(hk)−c(0) =c(hk)
p o ided ha ukhk= 1 and ukhk+1 = 0. Finally,
n
X
k=1
G
X
h=1
λk(c(h)−c(h−1))ukh =
n
X
k=1
λk
G
X
h=1
(c(h)−c(h−1))ukh =
n
X
k=1
λkc(hk)=
n
X
i=1
λici(J).
The equali y cons ain (11) ensu es ha he e a e exac ly p acili ies o be loca ed. Cons ain s (12)
and (13) s a e ha each clien is se ed by one open acili y. Equali y (16) ensu es a good de ini ion o he
a iable ukh and i ela es he so ing (ukh) and design a iables (xij). We need o impose some so ing
cons ain s on he ukh a iables (15). Cons ain (14) is edundan bu i is included because, acco ding o
Pue o [16], i signi ican ly s eng hen he o mula ion. Fu he mo e, all a iables a e bina y, (17), (18) and
(19).
No e ha wo mo e wo index o mula ions has been p oposed in Ma ´ın e al. [10, 11]. Howe e , hey
a e only alid i cii = 0 ∀i= 1, . . . , n ( ee sel -se ice).
2.3. A new o mula ion o DOMP
The e a e se e al o mula ions o DOMP bu hey all ha e la ge in eg ali y gap, as obse ed p e iously
in he li e a u e see Boland e al. [3], Ma ´ın e al. [10, 11] and Pue o [16]. The main mo i a ion o
add essing a new o mula ion o he DOMP elies on he a emp o educe his gap.
4
Fi s , we in oduce he ollowing no a ion.
ij ≺ˆıˆ ≡











Cij < Cˆıˆ
o
Cij =Cˆıˆ and i < ˆı
o
Cij =Cˆıˆ, i = ˆı and j < ˆ
ij ˆıˆ ≡











Cij > Cˆıˆ
o
Cij =Cˆıˆ and i > ˆı
o
Cij =Cˆıˆ, i = ˆı and j > ˆ
ij ˆıˆ ≡


ij ≺ˆıˆ
o
ij = ˆıˆ
ij ˆıˆ ≡


ij ˆıˆ
o
ij = ˆıˆ
(20)
2.3.1. New h ee index o mula ion.
Ou new o mula ion uses he same a iables and cons ain s as in he h ee-index o mula ion, DOMP1.
Excep ha (7) is eplaced by (21) ha a e called o de cons ain s.
The esul ing o mula ion is deno ed DOMP3.
(DOMP3) min
n
X
i=1
n
X
j=1
n
X
k=1
λkCijxk
ij
s. . (3),(4),(5),(6)
n
X
ˆı=1
n
X
ˆ=1:
ˆıˆij
xk−1
ˆıˆ +
n
X
ˆı=1
n
X
ˆ=1:
ˆıˆij
xk
ˆıˆ ≤1i, j = 1,· · · , n, k = 2,· · · , n (21)
xk
ij ∈ {0,1}i, j, k = 1, . . . , n
yj∈ {0,1}j= 1, . . . , n
The a ionale behind cons ain s (21) is illus a ed by he ollowing example.
Example 1. Conside he ollowing ma ix.
C=




0274
1055
3602
9410



(22)
The o de o couples ij by means o he abo e p e e ence o de is
11 ≺22 ≺33 ≺44 ≺21 ≺43 ≺12 ≺34 ≺31 ≺14 ≺42 ≺23 ≺24 ≺32 ≺13 ≺41.
The columns o Figu e 1 ep esen he n2possible assignmen s o clien s o acili ies whe eas i s ows
ep esen he nposi ions in DOMP objec i e unc ion. Each poin (bulle o ci cle) hus ep esen s a
a iable xk
ij and he bulle s co espond o a iables which canno ake alue 1 simul aneously because, in
any easible solu ion, he cos o couples assigned o consecu i e posi ions should be non-dec easing.
k=1
k=2
k=3
k=4
ij 11 22 33 44 21 43 12 34 31 14 42 23 24 32 13 41
Figu e 1: An o de cons ain o he case n=4
5

So, Figu e 1 co esponds o he ollowing inequali y:
n
X
i=1
n
X
j=1:
ˆıˆ43
x2
ˆıˆ +
n
X
i=1
n
X
j=1:
ˆıˆ43
x3
ˆıˆ ≤1,
o equi alen ly
x3
11 +x3
22 +x3
33 +x3
44 +x3
21 +x3
43 +x2
43 +x2
12 +x2
34 +x2
31 +x2
14 +x2
42 +x2
23 +x2
24 +x2
32 +x2
13 +x2
41 ≤1.
No e ha he numbe o o de cons ain s is O(n3). Fu he hey can be seen as cliques o a con lic
g aph induced by he incopa ibili y among xk
ij a iables on h ee index o mula ions (Nemhause and T o e
[12], Fe n´andez, Pue o, Rod ´ıguez-Ch´ıa [7]).
In a simila way, we can choose se e al alloca ions which a e so ed and iden i y a new ype o cons ain s.
Le sbe a posi i e in ege wi h s≤n−1 and le (i1j1),(i2j2),...,(isjs) be scouples o clien s and acili ies
such ha i j i +1j +1 o all = 1, . . . , s −1. Then he ollowing amily o inequali ies, called s ai case
inequali ies is alid o k=s, . . . , n:
n
X
i=1
n
X
j=1:
iji1j1
xk
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
n
X
i=1
n
X
j=1:
ijisjs
xk−s
ij ≤1.(23)
Figu e 2 p o ides an example o s ai case inequali y when n= 5.
k=1
k=2
k=3
k=4
i1j1
k=5
i2j2
i3j3i4j4
Figu e 2: A s ai case cons ain o he case n=5
No ice ha he e exis s an exponen ial numbe o addi ional s ai case cons ain s. Bu he ques ion is
whe he hese new cons ain s ac ually s eng hen ou o mula ion. The answe is p o ided by he ollowing
esul ha s a es ha all o hem a e implied by hose wi h a single s ep, i.e. he o de cons ain s.
P oposi ion 1. S ai case inequali ies (23) wi h i j i +1j +1 a e all domina ed by (21) and (4).
P oo . Le sbe a posi i e in ege such ha s≤n−1, hen by (21) we ob ain ha also he ollowing s
inequali ies hold: n
X
i=1
n
X
j=1:
iji j
xk−( −1)
ij +
n
X
i=1
n
X
j=1:
iji j
xk−
ij ≤1 = 1, . . . , s. (24)
Now, since i j i +1j +1 using (4), we ob ain he ollowing s−1 equa ions:
n
X
i=1
n
X
j=1
xk−
ij = 1 = 1, . . . , s −1.(25)
6
Adding all inequali ies (24) we ob ain a new inequali y:
n
X
i=1
n
X
j=1:
iji1j1
xk
ij +
n
X
i=1
n
X
j=1:
iji1j1
xk−1
ij +· · · +
n
X
i=1
n
X
j=1:
ijisjs
xk−(s−1)
ij +
n
X
i=1
n
X
j=1:
ijisjs
xk−s
ij ≤s.
A e ea anging, we ge
n
X
i=1
n
X
j=1:
iji1j1
xk
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
xk−
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji +1j +1
xk−
ij +
n
X
i=1
n
X
j=1:
ijisjs
xk−s
ij ≤s.
Nex , we con enien ly spli some e ms o he abo e inequali y o ge :
n
X
i=1
n
X
j=1:
iji1j1
xk
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji +1j +1
xk−
ij
+
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
xk−
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
n
X
i=1
n
X
j=1:
ijisjs
xk−s
ij ≤1+(s−1).
(26)
On he o he hand, using equali y (25) we can w i e
n
X
i=1
n
X
j=1:
iji j
xk−
ij +
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
n
X
i=1
n
X
j=1:
iji +1j +1
xk−
ij = 1 = 1, . . . , s −1.
Adding he abo e equa ions o all = 1, . . . , s −1, we ob ain
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
xk−
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji +1j +1
xk−
ij =s−1.
Finally, using he abo e equa ion in (26) esul s in
n
X
i=1
n
X
j=1:
iji1j1
xk
ij +
s−1
X
=1
n
X
i=1
n
X
j=1:
iji j
iji +1j +1
xk−
ij +
n
X
i=1
n
X
j=1:
ijisjs
xk−s
ij ≤1,
which is a s ai case inequali y.
2.3.2. A wo index o mula ion wi h scheduling cons ain s.
Fo mula ion DOMP3is a he e icien and igh whene e he e a e ew ies in he s uc u e o he
alloca ion cos s. This is o ins ance he case o p oblems wi h assignmen cos s based on la cos s ( o
ins ance andomly gene a ed). Howe e , i he numbe o ies in he alloca ion cos s is la ge he numbe
o bina y a iables and cons ain s is ela i ely la ge, as compa ed wi h simila numbe s in o mula ion
DOMP2. In o de o exploi his ad an age wi hou losing he usage o scheduling cons ain s, ha ela e
he o mula ion wi h he s able se p oblem, we will de elop in he ollowing ano he o mula ion.
The new o mula ion, called DOMP3C, is an ex ension o DOMP3using he a ionale o DOMP2.
Mo eo e , i p o ides a compac o m o ep esen ing ies in he alloca ion cos s.
7
Conside a new se o bina y a iables, kh such ha kh = 1 i he k- h smalles alloca ion cos is c(h)
and 0 o he wise. Nex , DOMP3Cis a new alid o mula ion o DOMP :
(DOMP3C) min
n
X
k=1
G
X
h=0
λkc(h) kh (27)
s. . (11),(12),(13)
G
X
h=0
kh = 1 k= 1, . . . , n (28)
n
X
i=1
n
X
j=1:
Cij =c(h)
xij =
n
X
k=1
kh h= 0, . . . , G (29)
X
h0<h
k+1h0+X
h0≥h
kh0≤1k= 1, . . . , n −1
h= 1, . . . , G (30)
xij, yj, kh ∈ {0,1}i, j, k = 1, . . . , n
h= 0, . . . , G. (31)
Clea ly, he objec i e unc ion (27) accoun s o he o de ed weigh ed sum o he alloca ion cos s. Con-
s ain s (29) s a e ha he numbe o alloca ions ha a e a ained a he alue c(h) ega dless o he le el
k ha hey occupy ( kh a iables) mus be equal o he numbe o alloca ions o clien s i o acili y jwi h
ij such ha Cij is equal o c(h)(see Figu e 3). Finally, cons ain s (30) a e scheduling cons ain s based on
cos s alues a he han in couples ij o clien - acili y (see Figu e 4).
k=1
k=2
k=3
k=4
ij 11 22 33 44 21 43 12 34 31 14 42 23 24 32 13 41
0
cij 0 0 0 1 1 2 2 3 4 4 5 5 6 7 9
c(h) 0 1 2 3 4 5 6 7 9
12+ 22+ 32+ 42 = x12+x34
Figu e 3: The a ionale o Cons ain s (29)
k=1
k=2
k=3
k=4
h 0 2 3 4 5 6 7 81
30+ 31+ 32+ 23+ 24+ 25+ 26+ 27+ 28 ≤ 1
Figu e 4: The a ionale o Cons ain s (30)
2.4. An agg ega ed o mula ion
He e, we in oduce ano he o mula ion (DOMP4) based on he agg ega ion o o de cons ain s om
DOMP3co esponding o he same posi ion. I he e o e equi es a smalle numbe o cons ain s.
(DOMP4) min
n
X
i=1
n
X
j=1
n
X
k=1
λkCijxk
ij
s. . (3),(4),(5),(6)
n
X
i
n
X
j




n
X
i0=1
n
X
j0=1:
i0j0ij
xk
i0j0+
n
X
i0=1
n
X
j0=1:
i0j0ij
xk−1
i0j0



≤n2k= 2,· · · , n (32)
xk
ij ∈ {0,1}i, j, k = 1, . . . , n
yj∈ {0,1}j= 1, . . . , n
8
The new cons ain s (32), ha we call weak o de cons ain s, ensu e ha i a couple ij occupies he k- h
posi ion hen in (k−1)- h posi ion he e mus be a mo e p e e ed alloca ion. I is due o he coe icien s
o each a iable in he inequali y. In each cons ain he e a e wo di e en posi ions, kand k−1, so ha ,
by (4), wo a iables mus ake alue one and all he o he s will be equal o ze o. I we do no ake in o
accoun he a iables aking he alue ze o and we assume ha he a iables wi h alue one o posi ions k
and k−1 a e in posi ion sand , espec i ely, we ha e he ollowing:
(n2−(s−1))xk
isjs+ xk−1
i j ≤n2,
which is alid i and only i <s.
Agg ega ing he scheduling cons ain s in DOMP3C o he di e en alues o he cos s, namely in
h= 1, . . . , G, esul s in a new alid model. This model is he agg ega ed e sion o DOMP3C ha we
deno e as DOMP4C:
(DOMP4C) min
n
X
k=1
G
X
h=0
λkc(h) kh
s. . (11),(12),(13),(28),(29)
G
X
h=1 
X
h0<h
kh0+X
h0≥h
k−1h0
≤G k = 2, . . . , n (33)
xij, kh ∈ {0,1}k= 1, . . . , n
h= 0, . . . , G.
Using he a ionale o (7), since he e is only one bina y a iable kh in each posi ion kby (28), he
ollowing cons ain s a e alid inequali ies o bo h o mula ions DOMP3Cand DOMP4C:
G
X
h=1
c(h) k−1h−
G
X
h=1
c(h) kh ≤0k= 2, . . . , n. (34)
In ac , hese cons ain s can also de ine ano he alid o mula ion o DOMP eplacing (33) by (34) in he
abo e o mula ion. In ou expe imen s, we will no use his las possibili y and ins ead, we shall use (34) as
alid inequali ies o s eng hen DOMP3Cand DOMP4C.
3. Theo e ical esul s
In his sec ion, we p o ide a heo e ical compa ison o he ou o mula ions p esen ed in Sec ion 2 and
some polyhed al esul s ega ding ou o mula ion DOMP3. Ou goal is o s a e he o mal ela ionships
be ween he lowe bounds p o ided by he linea elaxa ions o he conside ed o mula ions. In addi ion,
we also gi e some amilies o igh alid inequali ies which a e p o en o be ace o he poly ope de ined by
assignmen cons ain s (see Sec ion 3.2.)
3.1. Compa ison o o mula ions
We deno e by zl(·) he alue o he objec i e unc ion o DOMPle alua ed a he poin (·), by Pl he
poly ope de ining he easible se o he linea elaxa ion o o mula ion DOMPl, and by PI
l he con ex hull
o he in ege solu ions wi hin ha poly ope.
Conside he ollowing mapping
: [0,1]n3×[0,1]n−→ [0,1]n2×[0,1]n×[0,1]nG
(xk
ij, yj)7−→ (xij, yj, ukh)
9
(b) PI
3⊂g(PI
2)
To p o e he con e se, we obse e by ha e e y in ege solu ion in PI
3p o ides a p ojec ed in ege
solu ion and we ha e seen in Theo em 2 ha his poin sa is ies he inequali ies de ining P2.
2. PI
1=g(PI
2)
(a) g(PI
2)⊂PI
1
E e y in ege solu ion in P2is p ojec ed in o an in ege solu ion and, om Theo em 1 his poin
sa is ies he inequali ies de ining P1.
(b) PI
1⊂g(PI
2)
Con e sely, le (xk
ij, yj)∈PI
1and i s p ojec ion (xij , yj, ukh) by means o (35) and (36).
I is easy o see ha (3), (5) and (6) a e equi alen o (12), (13) and (11), espec i ely.
Since all he a iables a e posi i e he poin (xk
ij, yj) sa is ies
n
X
Cij ≥c(h)
xk
ij ≥
n
X
Cij ≥c(h+1)
xk
ij,
and (14) holds.
Fu he mo e, (16) holds by he change o a iable de ined in (35) and (36).
In inequali ies (7), we can o de he cos wi hou loss o gene ali y. Nex by (4), he e will be an
unique a iable wi h alue one in each posi ion. The e o e we ob ain he ollowing cons ain o
each di e en cos ,
n
X
Cij ≥c(h)
xk+1
ij ≥
n
X
Cij ≥c(h)
xk
ij h= 1, . . . , G, k = 1, . . . , n −1
and poin (xij, yj, ukh) sa is ies (15). Fu he mo e, his poin is in ege .
3. PI
3=PI
4
(a) PI
4⊂PI
3
Le (xk
ij, yj)∈PI
4. In pa icula , he weak o de cons ain is sa is ied. By (4) we ha e
n
X
i0=1
:i0j0
n
X
j0=1
ij
xk
i0j0≤1
and n
X
i0=1
:i0j0
n
X
j0=1
ij
xk−1
i0j0≤1,
whe e bo h inequali ies a e a sum o bina y a iables. So he e a e wo possibili ies:
n
X
i0=1
n
X
j0=1:
i0j0ij
xk
i0j0+
n
X
i0=1
n
X
j0=1:
i0j0ij
xk−1
i0j0≤1,o (43)
n
X
i0=1
n
X
j0=1:
i0j0ij
xk
i0j0+
n
X
i0=1
n
X
j0=1:
i0j0ij
xk−1
i0j0= 2.(44)
In case (44), he e will be wo di e en cos s ˆıˆ ≺˜
i˜
j(no e ha ˆıˆ = ˜
i˜
jis no possible by (6))
such ha xk
ˆıˆ = 1 and xk−1
˜
i˜
j= 1. This ac con adic s he o de ing ela ionship. Thus, he only
possibili y is ha case (43) holds and, in consequence, cons ain (21) is sa is ied.
16

(b) PI
3⊂PI
4
Le (xk
ij, yj) be an in ege poin sa is ying PI
3. This in ege poin belongs o PI
4because i o all
kwe add cons ain s (21) o all iand jwe ob ain (32).
Co olla y 3. PI
1=PI
3=PI
4=g(PI
2).
3.2. On he poly ope de ined by he assignmen cons ain s
The goal o his sec ion is o p o ide some esul s abou he acial s uc u e o he poly ope co esponding
o he assignmen cons ain s o o mula ion DOMP3. We es ic ou sel es o he analysis o o mula ion
DOMP3since, acco ding o Co olla y 2, i gi es he igh es o mula ion o DOMP. Simila s udies o
(simple ) poly opes ela ed o loca ion p oblem ha e been ca ied ou by e.g. A bib e al. [1], Guigna d [8],
Co nu´ejols and Thizy [4], de Fa ias J . [5] and Vasilye e al. [18].
Fo a gi en se J o popen acili ies, we de ine he assignmen poly ope P3(J) o DOMP3as ollows:
X
j∈J
n
X
k=1
xk
ij ≤1i= 1, . . . , n (45)
n
X
i=1 X
j∈J
xk
ij ≤1k= 1, . . . , n (46)
n
X
k=1
xk
ij ≤1i= 1, . . . , n, j ∈J(47)
X
i0j0ij
xk−1
i0j0+X
i0j0ij
xk
i0j0≤1i= 1, . . . , n, j ∈J, k = 2, . . . , n (48)
xk
ij ≥0i, k = 1, . . . , n, j ∈J(49)
We show which o he cons ain s ha desc ibe his poly ope a e ace inducing. Clea ly, his con ibu es
o he good quali y o he LP elaxa ion o DOMP3, since his assignmen poly ope ep esen s he unde lying
s uc u e o he p oblem once he se o open acili ies is de e mined.
We summa ize he polyhed al p ope ies o , PI
3(J), he con ex hull o P3(J)∩{0,1}n2×pin he ollowing
esul .
P oposi ion 2.
1. dim(P3(J)) = n2p.
2. Cons ain s (45) and (49) induce ace s o PI
3(J).
P oo . Cons ain s (45)-(49) de ine a pa icula packing poly ope which has been s udied by Padbe g [15]
among o he s. The esul s a e consequences o his obse a ion and he ac ha a iables appea ing in (45)
de ine maximal cliques in he con lic g aph associa ed o he p oblem, see Padbe g [15].
Obse e ha cons ain s (47) do no induce ace s o P3(J) since hey a e domina ed by cons ain s (45).
Le us deno e by (ij)s, s = 1, . . . , n2 he couple clien i acili y jwhe e Cij is he s- h lowe cos o e he
cos ma ix C. Fo ins ance, (ij)1and (ij)n2a e, espec i ely, he mos and he leas p e e ed couples in
he so ed lis o cos s o he cos ma ix C.
De ini ion 1. We call a pai ij gene ic i o some easible se Jsuch ha j∈J, i sa is ies
1. Le ˆıˆ be he couple clien ˆı acili y ˆ ∈Jsuch ha i does no exis any o he couple clien i0 acili y
j0∈Jsa is ying ˆıˆ ≺i0j0≺ij, i.e. ˆıˆ is he couple immedia ely be o e ij. Then, ˆı 6=i.
17
2. Le ˜ı˜ be he couple clien ˜ı acili y ˜ ∈Jsuch ha i does no exis any o he couple clien i0 acili y
j0∈Jsa is ying ij ≺i0j0≺˜ı˜, i.e. ˆıˆ is he couple immedia ely a e ij. Then, ˜ı 6=i.
In ui i ely, a pai ij is gene ic wi h espec o a easible solu ion se Ji he emaining easible alloca ion
cos s a e well dis ibu ed a ound i . Tha is, he e a e cos s o di e en clien s su ounding he ij cos (Cij)
in he so ed lis o cos s.
P oposi ion 3. I ij is gene ic o he easible se J hen
X
i0j0ij
xk−1
i0j0+X
i0j0ij
xk
i0j0+
n
X
l=k+1
xl
(ij)1+
k−2
X
l=1
xl
(ij)n2≤1k= 2,· · · , n (50)
is ace de ining o he assignmen poly ope PI
3(J).
ijîĵ ĩǰ
3 4
2
1
(ij) (ij)
1 n2
Figu e 5: Cons ain s (50)’s scheme.
P oo . Acco ding o De ini ion 1, le us deno e by ˆıˆ and ˜ı˜ he couples immedia ely be o e and a e he
couple ij in he so ed lis o cos s (see Figu e 5).
Le us p o e ha his amily o cons ain s a e ace de ining inequali ies showing ha hey a e maximal
cliques, i.e. i does no exis any a iable which does no belong o he clique and ha i is incompa ible
wi h all o hose ha appea in i .
Nex , we show ha o each a iable ha does no belong o he conside ed clique, he e is one in he
clique compa ible wi h i .
1. Fo all i0j0≺ij,l≤k−1 i i06=i, a iables xl
i0j0and xk
ij a e compa ible. O he wise, a iables xl
i0j0
and xk
ˆıˆ a e compa ible. (Case 1 in Figu e 5.)
2. Fo all i0j0ij,l < k −1 and i0j06= (ij)n2i i06=i a iables xl
i0j0and xk
ij a e compa ible. O he wise,
a iables xl
i0j0and xk
ˆıˆ a e compa ible. (Case 2 in Figu e 5.)
3. Fo all i0j0ij,l=k+ 1, .., .n and i0j06= (ij)1i i06=i, a iables xl
i0j0and xk−1
ij a e compa ible.
O he wise, a iables xl
i0j0and xk−1
˜ı˜ a e compa ible. (Case 3 in Figu e 5.)
4. Fo all i0j0ij,l=k, ..., n i i06=i a iables xl
i0j0and xk−1
ij a e compa ible. O he wise, a iables xl
i0j0
and xk−1
˜ı˜ a e compa ible. (Case 4 in Figu e 5.)
Rema k ha in ou compu a ional expe imen s, we did no ein o ce cons ain s (48) because ou p ep o-
cessing p ocedu e (see Sec ion 4) se s o ze o all he a iables appea ing in hese ein o cemen s associa ed
wi h he cos s o couples (ij)1and (ij)n2. Thus, in mos cases in ou o mula ion DOMP3, a e p ep o-
cessing hose cons ain s a e al eady ace inducing.
18
No a ion λ- ec o Name
T1 (1,1,...,1,1) p-median
T2 (0,0,...,0,1) p-cen e
T3 (0,0,...,0,0,1,1,...,1,1
| {z }
k
)k-cen um
T4 (0,0,...,0,0
| {z }
k1
,1,1,...,1,1,0,0,...,0,0
| {z }
k2
) (k1+k2)- immed mean
T5 (0,1,0,1,0,1,0,1, . . . ) –
T6 (. . . , 0,0,1,0,0,1) –
T7 λ andom Random
T8 (α, α, . . . , α, α, 1) Cen dian
Table 3: Types o λ- ec o s used in expe imen s
4. Compu a ional s udy
In o de o es he pe o mance o ou new o mula ions o DOMP, we ha e pe o med in ensi e
compu a ional es s compa ing esul s wi h espec o p e ious a ailable o mula ions o DOMP (see Boland
e al. [3], Dom´ınguez-Ma ´ın [6], Nickel [13], Nickel and Pue o [14]) and Ma ´ın e al. [11]).
4.1. Desc ip ion o he es ins ances
We use wo di e en ypes o ins ances. Fi s , we conside andom ins ances in which he elemen s o he
cos ma ix a e in ege numbe s andomly gene a ed be ween 10000 and 100000. The second se o ins ances
consis s in p-median ins ances om OR Lib, Beasley [2].
Rega ding he andom ins ances; we a y he numbe o clien s nin {10,20,30,40,50}and o each n,
we conside h ee possible alues o he numbe o acili ies o be open: p=n
4,n
3,n
2.
As o he p−median ins ances om Beasley’s lib a y, we ha e selec ed g aphs co esponding o p−
med1, . . . , p−med20 wi h up o 400 nodes om he o iginal da a. Each se o nodes is di ided in wo disjoin
subse s con aining, espec i ely, he se o clien s and he se o acili ies. (The eade may obse e ha in
hese ins ances we o ce hese wo se s o be disjoin ). Nex , each cos Cij is compu ed as he sho es pa h
be ween clien iand acili y jin he esul ing comple e g aph induced by he abo e desc ibed se o nodes.
Eigh di e en ypes o λ- ec o s a e es ed. Thei desc ip ion is p o ided in Table 3. We conside ,
among o he s, p-median, p-cen e , p-k-cen um, p- immed mean, andom and p-α-cen dian p oblems. In
he k-cen um case, k=n
2. In he (k1+k2)- immed mean, k1 = k2 = n
10 . When λis aken as a
andom ec o we gene a e 5 ins ances which con ain alues andomly d awn be ween 1 and 100. Finally,
we use α= 0.5 in he cen dian case.
Fo each ype o da a and each possible alues o pa ame e s n,pand ec o λ, he esul s p esen ed
consis in a e age alue o e i e ins ances. This esul s in an o e all numbe o 900 es ed ins ances.
4.2. P ep ocessing
We use wo di e en p ep ocessings o se some assignmen a iables o ze o, he i s one is based on
easibili y and he second on op imali y.
Claim 1. (Feasibili y based p ep ocessing)
1. Le l(h) = |{i:Cij ≤c(h), i, j = 1, . . . , n}| and u(h) = |{i:Cij ≥c(h), i, j = 1, . . . , n}|.
Then,
(a) kh = 0 and ukh = 1 k=l(h)+1, . . . , n, h = 1 . . . , G.; and
(b) kh = 0 and ukh = 0 k= 1, . . . , n −u(h), h = 1 . . . , G.
2. Le l(ij) = |{i0: minˆ i0ˆ ≺ij, i06=i}| and u(ij) = |{i0: maxˆ i0ˆ ij, i06=i}|. Then,
(a) xk
ij = 0 o all i, j = 1, . . . , n, k =l(ij)+2, . . . , n; and
19
(b) xk
ij = 0 o all i, j = 1, . . . , n, k = 1, . . . , n −u(ij)−1.
This claim o malizes he ac ha a gi en cos Cij can appea in posi ion k easible solu ion only i
he e a e a leas k−1 alloca ions cos s lowe han o equal o and n−kg ea e han o equal o Cij.
Claim 2. Le ij be a couple clien acili y. I |{j0:Cij > Cij0}| > n −p, hen xij = 0 and xk
ij = 0 o
k= 1, . . . , n.
This second claim emo es some easible solu ions o he p oblems which canno be op imal because hey
a e domina ed o o he easible solu ions wi h smalle objec i e alue.
Table 4 shows he pe cen age o a iables kh,ukh,xij and xk
ij ixed by ou p ep ocessing based on
Claim 1 and 2. No ice ha he pe cen age o wo o h ee index a iables ixed o ze o in andom ins ances
is almos equal because assignmen cos s in andom ins ances a e almos all di e en . Fu he mo e, we
obse e ha he pe cen age o ixed a iables sligh ly dec eases wi h n. Obse e ha Beasley ins ances ha e
a la ge numbe o ies in he dis ances (alloca ion cos s). Fo his eason, hese ins ances a e sol ed using
ou compac o mula ions DOMP3Cand DOMP4C, whe eas hose wi h andom da a a e sol ed wi h he
o mula ions ha do no ake ad en age o ies, namely DOMP3and DOMP4. Hence, Beasley ins ances
a e p ep ocessed wi h Claim 1.1 ( o a iables) and Random ins ances wi h Claim 1.2 ( o xk
ij a iables).
n (Random ins ances) 10 20 30 40 50 A e age
Claim 1.2 16.40% 9.17% 6.21% 4.67% 3.93% 8.07%
Claim 2 20.00% 25.00% 30.00% 29.99% 29.99% 27.00%
To al 29.68% 29.61% 30.43% 32.28% 31.97% 31.40%
n (Beasley ins ances) 50 100 150 200 A e age
Claim 1.1 27.03% 31.86% 33.42% 31.01% 30.83%
Claim 2 28.91% 26.85% 25.87% 25.26% 26.72%
To al 27.38% 30.33% 29.67% 27.12% 28.62%
Table 4: Numbe o a iables ixed by p ep ocessing
4.3. Compu a ional esul s
All ou expe imen s ha e been ca ied ou on a PC wi h wo In el Xeon p ocesso s wi h 3.46 GHz and 48
GB o RAM. The models we e w i en in Mosel and sol ed using Xp ess IVE 7.3, To ha e a clean compa ison
o ou solu ion app oaches, all au oma ic cu s om Xp ess ha e been disabled. We now epo a summa y o
ou compu a ional expe imen s. De ailed in o ma ion can be ound in he Supplemen a y ma e ial included
in he Appendix o his pape . In pa icula , we epo esul s o he di e en ypes o lambda ec o s om
Table 3.
4.3.1. Random alloca ion cos s da a se s.
Table 5 p o ides a compa ison o he LP- elaxa ions o models DOMP1,DOMP2,DOMP3,DOMP4
and DOMP4∩1, a e aging o n= 20 and n= 40 and all possible alues o pand λ. The las model
DOMP4∩1consis s in DOMP4 o which cons ain s (7) o DOMP1ha e been appended. Speci ically, we
epo he in eg ali y gap de ined as GAP =z∗−zLP
l
z∗, whe e z∗and zLP
l ep esen he op imal alue o
DOMPland i s LP- elaxa ion, espec i ely. We poin ou ha he epo ed GAP in all o mula ions is
compu ed a e he applica ion o he p ep ocessing esul s de eloped in his pape . We obse e ha he
alues o he in eg ali y gap a y be ween 2.29% and 7.34%, ob ained in o mula ions DOMP3 he bes and
DOMP2o DOMP1 he wo s . In all cases, he LP gaps a e good bu specially in o mula ion DOMP3
which seems o be a he igh . We ema k also he small di e ence ha is ob ained adding cons ain s
(7) o he o mula ion DOMP4in e ms o in eg ali y gap. Mo eo e , we poin ou ha we ha e ob ained
20
he same LP gap wi h o mula ions DOMP1and DOMP2 o all he es ed ins ances. (I is s ill an open
ques ion whe he his is also heo e ically ue.) Thus, om Table 5 one could conclude ha he bes
o mula ion is DOMP3. In spi e o ha , he la ge numbe o inequali ies (O(n3)) used in he model makes
i a he slow whene e he numbe o clien s nis o mode a e size (n > 50).
In o de o de ine a solu ion app oach which p esen s he bes pe o mance, we ha e conduc ed a p elimi-
na y compu a ional es wi h ins ance sizes n= 10,20,30. Ou i s s a egy consis s in sol ing DOMP3wi h
a pu e b anch-and-bound. Ou second s a egy, DOMP4∩1(B&B), sol es DOMP4∩1wi h a pu e b anch-
and-bound. The hi d app oach, DOMP4∩1(B&C−3), s a s by sol ing he LP- elaxa ion o DOMP4
and hen adds inequali ies (7) a he oo node and o de cons ain s (21) as long as hey a e iola ed by
he cu en solu ion o he LP. The eade may obse e ha bo h amilies o inequali ies a e cliques in he
con lic g aph induced by he h ee index a iables o ou o mula ion. The e o e, o de cons ain s could in
p inciple be added by s anda d clique cu s gene a ion echniques implemen ed in Xp ess. Ne e heless, ou
own implemen a ion is mo e e icien since he sepa a ion o he en i e amily o alid inequali ies (21) can
be pe o med in O(n3) by sequen ially upda ing he L.H.S. alue o he o de cons ain s when swi ching
om a couple ij o he adjacen one in he same posi ion k. The ou h and las s a egy DOMP4(B&C−3)
is a b anch and cu algo i hm based upon DOMP4adding only alid inequali ies om (21).
Fo mula ion GAP
DOMP17,34%
DOMP27,34%
DOMP32,29%
DOMP46,27%
DOMP4∩16,06%
Table 5: A e age in eg ali y gaps
Solu ion app oach Time (s) #nodes
DOMP3(B&B) 463.24(8) 46.20
DOMP4∩1(B&B) 18.64 1389.51
DOMP4∩1(B&C−3) 52.25 24.94
DOMP4(B&C−3) 39.39 29.37
Table 6: CPU-Time and Numbe o nodes o he di e en o -
mula ions o n= 10,20,30.
Ou esul s a e epo ed in Table 6. The e we ha e included he CPU- imes and he numbe o nodes
in he B&B ee o sol ing ins ances o op imali y wi hin 2 hou s o CPU- ime. The numbe s be ween
pa en heses indica e he numbe o unsol ed ins ances wi hin he ime limi . We obse e ha on a e age
DOMP4∩1(B&B) is he s a egy ha sol es p oblems as e e en hough i has o isi he la ges numbe
o nodes in he B&B ee. This is explained by he ac ha i is he mos compac o mula ion (wi h he
smalles numbe o inequali ies) and he e o e, i can be easily sol ed a each node. On he o he hand,
DOMP3(B&B) is he hea ies one (in e ms o LP ep esen a ion) gi ing ise o wo se CPU- imes al hough
i isi s ew nodes in he sea ching phase. In be ween, we ound he wo b anch-and-cu p ocedu es ha
we ha e es ed DOMP4∩1(B&C−3) and DOMP4(B&C−3). In he implemen a ion o his wo B&C
app oaches we ha e es ed o sepa a e maximal clique inequali ies o e he con lic g aph as an al e na i e
o ou own sepa a ion p ocedu e. Ne e heless, ou sepa a ion algo i hm applied on inequali ies (7) and
(21) gi es be e esul s. F om he abo e wo ables, we can conclude ha he bes s a egies o be es ed
in he in ensi e compu a ional es s a e DOMP4∩1(B&B) and, a imes, DOMP4(B&C−3).
To inish, Table 7 allows us o compa e ou bes s a egy, i.e. DOMP4∩1(B&B), wi h a b anch-and-
bound app oach based on DOMP2, as well as o de e mine he size o ins ances ha can be sol ed wi hin
a easonable ime limi o wo hou s. This able is o ganized in ou columns. The i s wo columns show
he size nand po he ins ances. The las wo columns show he a e age CPU- ime in seconds necessa y o
sol ing hose ins ances applying o mula ion DOMP2(B&B) and DOMP4∩1(B&B). The numbe s be ween
pa en heses indica e he numbe o unsol ed ins ances wi hin he ime limi o 2 hou s.
F om Table 7 we ema k ha DOMP4∩1(B&B) pe o ms simila ly as DOMP2(B&B) (i imp o es he
beha io o DOMP2(B&B) only o some ins ance sizes). I is be e o da a ins ances wi h n < 40 in all
combina ions o p. In addi ion, o la ge n, i.e. n= 40,50, i is also be e excep i pis ela i ely small as
compa ed wi h n. Fu he mo e, we also obse e ha o n= 50 bo h models ail o sol e some ins ances o
he smalles es ed alue o p= 12. Finally, Table 8 allows us o conclude ha h ee index wi h agg ega ed
21

scheduling cons ain s pe o ms he bes whene e he numbe o acili ies o be loca ed is no oo small
compa ed o he numbe o possible loca ions.
n p Time (# unsol ed)
DOMP2(B&B)DOMP4∩1(B&B)
10 2 1.12 0.42
10 3 0.54 0.25
10 5 0.18 0.09
20 5 22.21 5.80
20 6 9.05 4.09
20 10 3.33 1.54
30 7 161.32 121.04
30 10 66.85 22.70
30 15 33.15 11.87
40 10 449.11 625.68
40 13 232.79 174.62
40 20 116.99 49.13
50 12 1870.80(2) 3184.54(6)
50 16 988.08 804.36
50 25 771.51(2) 157.44
A e age 315.14 344.24
Table 7: Summa y o esul s wi h andom ma ices
pDOMP2(B&B)DOMP4∩1(B&B)
n
4500.91(2) 787.49(6)
n
3259.46 201.20
n
2185.03(2) 44.01
Table 8: CPU-Time o he di e en o mula ions o di e en alues o p.
4.3.2. Beasley’s da a se .
The la ge numbe o ies wi hin he cos ma ices o his da a se sugges s ha on his second pa o
he s udy DOMP4Cis he app op ia e o mula ion o sol e he p oblems. Fo each cos ma ix we sol e
each ins ance wi h DOMP2(B&B) and DOMP4C(B&C−3), i.e. o mula ion DOMP4Cwi hin a b anch
and cu scheme sepa a ing inequali ies (30). Fo each alue o nwe sol e hose p oblems o he numbe o
open acili ies p, sugges ed in he o iginal da a om Beasley’s lib a y, and o all he conside ed ec o s o
λshown in Table 3.
Table 9 shows he a e age esul s o hese ins ances. De ailed in o ma ion o each λcan be ound in
he elec onic appendix. This able is o ganized in i e columns. The i s h ee columns show he name
o he ins ance p oblem and i s size nand p. The las wo columns show he CPU- ime o sol ing hose
ins ances applying s a egies DOMP2(B&B) and DOMP4C(B&C−3). The numbe s be ween pa en heses
indica e he numbe o ins ances ha could no be sol ed o op imali y wi hin he ime limi o 2 hou s. We
can see ha in 11 ou o 20 ins ances DOMP4C(B&C−3) is as e han DOMP2(B&B). This beha io
con i ms ha bo h o mula ions ha e a a he simila pe o mance. In spi e o ha , we obse e ha he
use o ou new o mula ion ou pe o ms DOMP2p o ided ha nis o mode a e size n < 50 o whene e
he size o p ela i e o nis no oo small, namely p/n ≥0.2. This beha io allows us o conclude ha
DOMP4C(B&C−3) is ad isable o be used, a leas , in hose cases.
22
P oblem n p Time (#unsol ed)
DOMP2(B&B)DOMP4C(B&C−3)
pmed1 50 5 94.65 94.66
pmed2 50 10 79.24 40.58
pmed3 50 10 103.84 37.58
pmed4 50 20 34.94 8.57
pmed5 50 33 20.44 3.90
pmed6 100 5 805.02 4757.27(5)
pmed7 100 10 617.60 2708.85(2)
pmed8 100 20 848.95(1) 543.26
pmed9 100 40 130.28 45.87
pmed10 100 67 45.84 22.01
pmed11 150 5 1353.85(1) 3702.40(2)
pmed12 150 10 1667.06(1) 4235.25(4)
pmed13 150 30 2030.82(1) 3808.45(3)
pmed14 150 60 509.60 302.93
pmed15 150 100 88.48 52.17
pmed16 200 5 2760.99(1) 5940.66(6)
pmed17 200 10 2940.22(1) 5670.05(6)
pmed18 200 40 1830.27(1) 4129.70(3)
pmed19 200 80 358.11 264.35
pmed20 200 133 256.21 150.76
Table 9: Summa y o esul s using Beasley’s da a se
5. Concluding ema ks
This pape p esen s new o mula ions o he Disc e e O de ed Median P oblem based on o de con-
s ain s (21) ha a e alid o he gene al non ee sel -se ice case. Fu he mo e, we p o e heo e ical
ela ionships, in e ms o hei LP-gap, o di e en o mula ions o DOMP. Acco ding o he heo e ical
and compu a ional esul s ob ained in his pape , he main quali y o he new o mula ions is ha hey
p o ide subs an ial imp o emen o he in eg ali y gap wi h espec o p e iously known ones.
We ha e obse ed ha he LP-gap o DOMP1and DOMP2is always equal. I is cu en ly an open
ques ion whe he his p ope y holds in gene al. This ques ion will be a subjec o ou u u e esea ch.
This pape has also opened ano he in e es ing line o esea ch ha consis s in inding ex ensions o
some o he exis ing o mula ions o exploi special s uc u es o he lambda coe icien s, as o ins ance
he one in Ma ´ın e al. [11]. Ex ensions based on he esul s in [11] seem o equi e addi ional a iables o
handle he non ee sel -se ice case. A simila a ionale can be also applied o he new o mula ions in his
pape . Fu he heo e ical and compu a ional compa isons o he abo e men ioned new app oach will be
he subjec o a ollow up pape .
Acknowledgemen
The esea ch o he i s au ho was pa ially suppo ed by he In e uni e si y A ac ion Poles P o-
g amme ini ia ed by he Belgian Science Policy O ice and Spanish MTM2012-36163-C06-04 . The e-
sea ch o he second and hi d au ho s was pa ially suppo ed by he p ojec FQM-5849 (Jun a de An-
daluc´ıa FEDER) and MTM2010-19576-C02-01 (MICINN, Spain).
[1] C. A bib, M. Labb´e, and M. Se ilio. Scheduling wo chains o uni jobs on one machine: A polyhed al s udy. Ne wo ks,
58-2:103–113, 2011.
[2] J.E. Beasley. OR-Lib a y, 2012. people.b unel.ac.uk/~mas jjb/jeb/in o.h ml.
[3] N. Boland, P. Dom´ınguez-Ma ´ın, S. Nickel, and J. Pue o. Exac p ocedu es o sol ing he disc e e o de ed median
p oblem. Compu e s & Ope a ions Resea ch, 33(11):3270–3300, 2006. ISSN 0305-0548.
[4] G. Co nu´ejols and J.M. Thizy. Some ace s o he simple plan loca ion poly ope. Ma hema ical P og amming, (23):50–74,
1982.
23
[5] I. R. de Fa ias J . A amily o ace s o he uncapaci a ed p-median poly ope. Ope a ions Resea ch Le e s, 28(4):161–167,
2001.
[6] P. Dom´ınguez-Ma ´ın. The Disc e e O de ed Median P oblem: Models and Solu ion Me hods. Kluwe , 2003.
[7] E. Fe n´andez, J. Pue o, A.M. Rod ´ıguez-Ch´ıa. On Disc e e Op imiza ion wi h O de ing. Annals o Ope a ions Resea ch,
207(1):83–96, 2013.
[8] M. Guigna d. F ac ional e ices cu s and ace s o he simple plan loca ion p oblem. Ma hema ical P og amming S udy,
(12):152–160, 1980.
[9] J. Kalcsics, S. Nickel, J. Pue o, A. M. Rod ´ıguez-Ch´ıa, Dis ibu ion Sys ems Design Wi h Role Dependen Objec i es
EJOR, 202 (2010) 491-501.
[10] A. Ma ´ın, S. Nickel, J. Pue o, and S. Vel en. A lexible model and e icien solu ion s a egies o disc e e loca ion
p oblems. Disc e e Applied Ma hema ics, 157(5):1128–1145, 2009. ISSN 0166-218X.
[11] A. Ma ´ın, S. Nickel, and S. Vel en. An ex ended co e ing model o lexible disc e e and equi y loca ion p oblems.
Ma hema ical Me hods o Ope a ions Resea ch, 71 (1): 125–163, 2010.
[12] G.L. Nemhause and L.E. T o e . Ve ex packings: S uc u al p ope ies and algo i hms. Ma hema ical P og amming,
8:232–248, 1975.
[13] S. Nickel. Disc e e o de ed webe p oblems. In Ope a ions Resea ch P oceedings 2000, pages 71–76. Sp inge Ve lag, 2001.
[14] S. Nickel and J. Pue o. Loca ion Theo y: A Uni ied App oach. Sp inge Ve lag, 2005.
[15] M. W. Padbe g. On he Facial S uc u e o Se Packing Polyhed a. Ma hema ical P og amming, 5:199–215, 1973.
[16] J. Pue o. A new o mula ion o he capaci a ed disc e e o de ed median p oblem wi h {0,1}-assignmen . In Ope a ions
Resea ch P oceedings 2007, olume 1, pages 165–170. Sp inge , 2008. ISBN 978-3-540-77902-5.
[17] J. Pue o, A. B. Ramos, and A. M. Rod ´ıguez-Ch´ıa. Single-alloca ion o de ed median hub loca ion p oblems. Compu .
Ope . Res., 38(2):559–570, Feb ua y 2011. ISSN 0305-0548.
[18] I. Vasilye , X. Klimen o a, and M. Boccia. Polyhed al s udy o simple plan loca ion p oblem wi h o de . Ope a ions
Resea ch Le e s, (2):153–158, 2013.
24
AppendixA. Supplemen a y ma e ial o he pape “A Compa a i e S udy o Fo mula ions
and Solu ion Me hods o he Disc e e O de ed p-Median P oblem”
This elec onic supplemen epo s de ailed in eg ali y GAP and CPU imes o each o he eigh ype o
λ- ec o ha ha e been conside ed in he compu a ional esul s o he pape . We ollow he same no a ion so
ha T1, ..., T8, e e espec i ely o p-median, p-cen e , p-k-cen um, (k1+k2)- immed mean, he sequence
o 0,1,0,1..., he sequence o . . . , 0,0,1,0,0,1, andom elemen s and p-α-cen dian (see Table 3 in he pape ).
AppendixA.1. GAP
In his sec ion, we de ail he esul o Table 5 in he pape compa ing he a e age in eg ali y gap o he
o mula ions in he pape o he di e en ypes o λ- ec o s T1, . . . ,T8.
Table A.10: A e age in eg ali y GAP
Fo mula ion
λ- ec o DOMP1DOMP2DOMP3DOMP4DOMP4∩1
T1 0,14% 0,14% 0,14% 0,14% 0,14%
T2 36,04% 36,04% 18,81% 31,59% 31,57%
T3 16,38% 16,38% 4,53% 13,07% 13,07%
T4 5,53% 5,53% 0,14% 3,29% 3,29%
T5 2,16% 2,16% 0,91% 3,42% 2,16%
T6 4,01% 4,01% 1,78% 5,38% 3,99%
T7 3,32% 3,32% 0,77% 3,26% 3,00%
T8 3,69% 3,69% 1,02% 3,30% 3,30%
25