INFORMS JOURNAL ON COMPUTING
A icles in Ad ance, pp. 1–18
h p://pubsonline.in o ms.o g/jou nal/ijoc ISSN 1091-9856 (p in ), ISSN 1526-5528 (online)
A B anch-P ice-and-Cu P ocedu e o he Disc e e O de ed
Median P oblem
Samuel Deleplanque,
a
Ma ine Labbé,
b
Diego Ponce,
c,d,e
Jus o Pue o
c
a
I s a , COSYS, ESTAS, Uni e si é Lille No d de F ance, 59000 Lille, F ance;
b
Dépa amen d’In o ma ique, Facul é des Sciences, Uni e si é
Lib e de B uxelles, 1050 B uxelles, Belgium;
c
Ins i u o de Ma em´
a icas de la Uni e sidad de Se illa (IMUS), 41012 Se illa, Spain;
d
Depa men o Mechanical, Indus ial and Ae ospace Enginee ing, Conco dia Uni e si y, Mon eal, Quebec H3G 1M8, Canada;
e
Cen e
in e uni e si ai e de eche che su les éseaux d’en e p ise, la logis ique e le anspo (CIRRELT), Mon eal, Quebec H3T 1J4, Canada
Con ac : [email p o ec ed],h p://o cid.o g/0000-0003-4119-6006 (SD); [email p o ec ed],
h p://o cid.o g/0000-0001-7471-2308 (ML); [email p o ec ed],h p://o cid.o g/0000-0003-3380-6601 (DP); [email p o ec ed],
h p://o cid.o g/0000-0003-4079-8419 (JP)
Recei ed: Feb ua y 9, 2018
Re ised: Decembe 7, 2018; Ma ch 11, 2019
Accep ed: June 2, 2019
Published Online in A icles in Ad ance:
Janua y 7, 2020
h ps://doi.o g/10.1287/ijoc.2019.0915
Copy igh : © 2020 INFORMS
Abs ac . The disc e e o de ed median p oblem (DOMP) is o mula ed as a se -pa i ioning
p oblem using an exponen ial numbe o a iables. Each a iable co esponds o a se o
demand poin s alloca ed o he same acili y wi h he in o ma ion o he so ing posi ion o
hei co esponding cos s. We de elop a column gene a ion app oach o sol e he con inuous
elaxa ion o his model. Then we apply a b anch-p ice-and-cu algo i hm o sol e small- o
la ge-sized ins ances o DOMP in compe i i e compu a ional ime.
Funding: This esea ch was suppo ed by Spanish/FEDER [G an MTM2016-74983-C02-01-R]. The
esea ch o he second and hi d au ho s was suppo ed by he In e uni e si y A ac ion Poles
P og amme ini ia ed by he Belgian Science Policy O fice.
His o y: Accep ed by And ea Lodi, A ea Edi o o Design & Analysis o Algo i hms—Disc e e.
Keywo ds: disc e e op imiza ion •loca ion heo y •b anch and p ice •o de ed median p oblems
1. In oduc ion
B oadly speaking, a acili y-loca ion p oblem consis s
o loca ing one o se e al acili ies o minimize an ob-
jec i e unc ion o he assignmen cos s o clien s o a-
cili ies. Median and cen e loca ion p oblems cons i u e
he mos popula ones. The o de ed median loca ion
p oblem is a flexible model ha p o ides a common
amewo k o cas mos popula loca ion p oblems. The
objec i e unc ion obeminimizedisaweigh ed unc ion
o he alloca ion cos s in which he weigh s a e assigned
o he o de ed alues o he cos s a he han o specific
cos s. O de ed median loca ion p oblems we e fi s in-
oduced in ne wo ks and con inuous spaces by Nickel
and Pue o (1999) and Pue o and Fe n´
andez (2000),
espec i ely. La e , hey we e ex ended o he disc e e
se ing by Nickel (2001)andBolande al.(2006).
Gi en a se o clien s and a se o candida e loca-
ions and assuming ha he alloca ion cos s o clien s
o acili ies a e known, he disc e e o de ed median
p oblem (DOMP) consis s o choosing p acili y loca-
ions and assigning each clien o a chosen acili y wi h
he smalles alloca ion cos o minimize he o de ed
weigh ed a e age o hese cos s. The o de ed weigh ed
a e age so s he alloca ion cos s in a nondec easing se-
quence and hen i pe o ms he scala p oduc o his so-
ob ained so ed cos ec o wi h a gi en ec o o weigh s.
DOMP has been widely s udied since he 1990s, and
he e a e a numbe o di e en o mula ions, solu ion
app oaches, and applica ions a ailable in he li e a u e.
To ci e a ew, DOMP has been applied o disc e e acili y
loca ion in Boland e al. (2006), Ma ´
ıne al.(2009,
2010), Nickel (2001), Pue o (2008), and Pue o e al.
(2009); o loca ion on ne wo ks in Nickel and Pue o
(1999); o hub ne wo k design p oblems in Pue o
e al. (2011,2013,2016); o de e mine alues in co-
ope a i e game heo y in Pe ea and Pue o (2013); o
combina o ial op imiza ion p oblems wi h o de ing
in Fe n´
andez e al. (2013,2014,2017); and o o ing
p oblems in Ponce e al. (2018), e c. The eade is e-
e ed o he monog aphs by Nickel and Pue o (2005)
and Pue o and Rod ´
ıguez-Ch´
ıa(2015) o someo he
applica ions.
The e exis se e al alid o mula ions o DOMP
ha exploi specific ea u es o he p oblem, o in-
s ance, ee sel -se ice, ies in he ma ix o cos s, o
null elemen s in he ec o o weigh s (see, e.g., Boland
e al. (2006), Ma ´
ıne al.(2009,2010), Pue o e al.
(2013), Labbé e al. (2017), and he e e ences he ein).
In Labbé e al. (2017), a new o mula ion o DOMP
has been p oposed based on a se -packing app oach ha
is alid o gene al cos coe ficien s. This o mula ion
gi es ise o a he igh in eg ali y gaps and was shown
o be easonably e ficien o sol e medium-sized in-
s ances when embedded in a b anch-and-cu (B&C)
scheme. Fo gene al cos coe ficien s (wi h no ies), all
hese o mula ions ha e a e y la ge (cubic) numbe o
1
bina y a iables, and he e o e, al eady o ins ances
wi h 100 clien s, hey ail o be loaded by he sol e s.
In his pape , we explo e a di e en pa adigm o
sol ing DOMP based on column gene a ion ha a oids
conside ing explici ly all he a iables o he p oblem.
Mo eo e , we in oduce a new ex ended o mula ion
using an exponen ial numbe o a iables ha co e-
sponds o a se -pa i ioning model and p o ides e en
be e linea elaxa ion lowe bounds. Each a iable
ep esen s a se o couples (clien , posi ion). In each
elemen o he pa i ion, i s clien s a e se ed by he
same acili y, and hei posi ions indica e he place
o hei alloca ion cos s in he so ed lis o alloca ion
cos s o heen i econside ed solu ion. To handle he
exponen ial numbe o a iables, we use a column-
gene a ion app oach ha is embedded in a b anch-
p ice-and-cu (B&P&C) algo i hm.
B anch-and-p ice algo i hms o sol e loca ion p ob-
lems ha e been p oposed by du Me le and Vial (2002),
Lo ena and Senne (2004), Senne e al. (2005), Ceselli
and Righini (2005), A ella e al. (2006), and Con e as
e al. (2011) o ci e a ew. In mos cases, he conside ed
p oblem is he p-median al hough he e a e some
excep ions, o ins ance,Con e ase al.(2011) o
capaci a ed hub loca ion o Doulabi e al. (2016) o a
di e en p oblem.
A b anch-and-p ice app oach has ne e been ap-
plied o DOMP, and e en mo e, ou app oach based
on a se pa i ion o couples is ully new. These wo
ac s open new a enues o esea ch in he field o
loca ion analysis. The e o e, he con ibu ions o his
pape a e wo old: (1) me hodological, o p opose a
new pe spec i e in he esolu ion o DOMP based on
o mula ions wi h an exponen ial numbe o a iables
and o de elop an e ficien B&P&C algo i hm o
handle hem, and (2) nume ical, o p o ide solu ions
o la ge ins ances o DOMP. Mo eo e , in hose cases
in which op imali y o a solu ion canno be ce ified,
ou app oach p o ides, a leas , alid lowe bounds
ha can be used o measu e he quali y o easible
solu ions o DOMP gi en ei he by heu is ic algo i hms
(Dom´
ınguez-Ma ´
ıne al.2005, S animi o ic e al.
2007, Pue o e al. 2014, Olende and Og yczak 2018).
The emainde o his pape is o ganized as ollows.
No a ion, models, and algo i hms a e p esen ed in
Sec ion 2.Sec ion2.2 in oduces a new se -pa i ioning
o mula ion o DOMP. This o mula ion uses an ex-
ponen ial numbe o a iables in which each elemen o
he pa i ion is a se o clien s ha a e assigned o he
same acili y oge he wi h hei so ed posi ions. This
o mula ion is heo e ically compa ed wi h ano he
alid o mula ion desc ibed in Sec ion 2.1 and bo -
owed om Labbé e al. (2017). Sec ion 2.3 desc ibes
he column gene a ion algo i hm ha we ha e de-
signed o o e come he la ge numbe o a iables in
hemodel.Wep o e ha hep icingsubp oblemis
sol able e ficien ly in polynomial ime by using an
ad hoc dynamic p og amming algo i hm. We de o e
Sec ion 3 o he implemen a ion de ails o ou B&P&C
algo i hm. We de elop a GRASP heu is ic in Sec ion 3.1
ha is used o gene a e bo h a p omising ini ial so-
lu ion and a pool o a iables o ini ialize he column-
gene a ion ou ine. We also de elop a s abiliza ion
ou ine based on Pessoa e al. (2010) ha educes
conside ably he numbe o i e a ions o he column-
gene a ion app oach in Sec ion 3.2.Inaddi ion,Sec-
ion 3.3 is de o ed o an addi ional imp o emen ,
namely a p ep ocessing. The nex wo sec ions, 3.4
and 3.5, p esen ou b anching s a egies and some
amilies o alid inequali ies ha a e added o he
b anch-and-p ice algo i hm. In he las sec ion, namely
Sec ion 4,we epo on hefinal compu a ional ex-
pe imen s. We e alua e he pe o mance o he B&P&C
algo i hm and compa e i o he compac o mula ion
in Sec ion 2.1. The pape ends wi h some concluding
ema ks.
2. P oblem Defini ion and Fo mula ions
Le Ibe a se o npoin s ha , a he same ime, ep-
esen clien s and po en ial uncapaci a ed acili y
loca ions, and le cij deno e he cos o se ing clien
i’s demand om acili y j.
Gi en a se Jo popen acili ies, le ci(J) ep esen
hecheapes cos o alloca ingclien i o a acili y in
J, ha is,ci(J):minj∈Jcij.
Now le us so he cos s ci(J),i∈Iby nondec easing
o de o hei alues. The elemen s o he esul ing
ec o o o de ed cos s a e deno ed by c(k)(J)and
sa is y c(1)(J)≤···≤c(n)(J).We deno e he se o all
possible posi ions 1,...,nin his o de ed ec o by K.
Gi en he ec o λ(λk)k∈Ksa is ying λk≥0,k∈K,
he objec i e unc ion o DOMP is defined as
z(J):∑
k∈K
λkc(k)(J).(1)
Recall 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, whe e α[0,1],weob ain
a con ex combina ion o median and cen e objec-
i es (cen dian), e c.
The p- acili y disc e e o de ed median p oblem
looks o he subse Jo p acili ies o open o minimize
he o de ed median unc ion:
min
J⊆I:|J|pz(J).(DOMP)
Se e al o mula ions o DOMP ha e been p oposed in
he li e a u e using di e en ypes o a iables. Among
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
2INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS
hem, we men ion hose based on a combina ion o he
p-median and pe mu a ion poly opes (Boland e al.
2006) o on co e ing app oaches by using adius a i-
ables (Pue o 2008;Ma
´
ıne al.2009,2010).
2.1. An Explici Fo mula ion o DOMP: The Weak
O de Cons ain s
In he ollowing, we ecall he weak o de cons ain s
o mula ion, WOC,in oducedinLabbée al.(2017),
and ha is he s a ing poin o he de elopmen s p e-
sen ed in his pape . This o mula ion uses wo ypes o
bina y a iables. Va iable yjassumes alue one i a-
cili y j∈Iis open (i.e., j∈J) and ze o o he wise.
Va iable xk
ij is equal o one i clien i∈Iis alloca ed o
acili y j∈Iand he co esponding cos occupies
posi ion k∈Kin he alloca ion cos anking (i.e., c(k)(J)
cij). The choice o his o mula ion is mo i a ed by i s
good pe o mance in e ms o in eg ali y gap (see
Labbé e al. (2017)). Howe e , i eques s impo an
memo y space because i needs O(n3)bina y a iables,
which may become p ohibi i e o mode a e n.
We deno e he ank o he alloca ion cos cij by ij,
ha is, ij i cij is he  h elemen in he lis o
he cos s cij o all i,j∈I, so ed by o de o non-
dec easing alues and o which ies a e b oken a -
bi a ily. Fo he sake o eadabili y, he eade is e-
e ed o Example 1in Sec ion 2.3.The o mula ionis
as ollows:
(WOC)min ∑
i∈I∑
j∈I∑
k∈K
λkcijxk
ij (2)
s. . ∑
j∈I∑
k∈K
xk
ij 1i∈I(3)
∑
i∈I∑
j∈I
xk
ij 1k∈K(4)
∑
k∈K
xk
ij ≤yji,j∈I(5)
∑
j∈I
yjp(6)
∑
i∈I∑
j∈I∑
i∈I∑
j∈I:
ij≤ ij
xk
ij+∑
i∈I∑
j∈I:
ij≥ ij
xk−1
ij
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠≤n2
k∈K,k 1(7)
xk
ij,yj∈{0,1}i,j∈I,k∈K.(8)
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 po-
si ion he e mus be exac ly one alloca ion cos (4).
Cons ain s (5) ansla e he ac ha a clien can
be alloca ed o a acili y only i his acili y is open
and ha he alloca ion cos o a clien o a acili y can be
placed in a mos one posi ion. The equali y cons ain
(6) implies ha he e a e exac ly popen acili ies.
Cons ain s (7), called weak o de cons ain s,ensu e
ha , i clien iis alloca ed o acili y jand he co e-
sponding cos s cij occupy he k h posi ion in he cos
anking o he solu ion, hen, in he (k−1) h posi ion,
he e mus be a smalle alloca ion cos . This p ope y
is en o ced by he coe ficien 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−1so ha ,by(4), only wo a iables
mus ake alue one, and all he o he s a e equal o
ze o. I we do no ake in o accoun he a iables as-
suming he alue ze o and we assume ha he a iables
wi h alue one o posi ions kand k−1 co espond o
alloca ion pai s in so ed posi ion sand , espec-
i ely, he inequali y educes o he ollowing exp es-
sion: (n2−(s−1))xk
isjs+ xk−1
i j ≤n2,which is alid i and
only i <s. Finally, he a iables a e bina y, see (8).
WOC can be ein o ced by adding he ollowing
alid inequali ies:
∑
i∈I∑
j∈I:
ij≤ ij
xk
ij+∑
i∈I∑
j∈I:
ij≥ ij
xk−1
ij≤1,i,j∈I,k∈K,k 1.(9)
Obse e ha cons ain s (7) a e he agg ega ion o e
i,j∈Io inequali ies (9). These inequali ies a e he so-
called s ong o de cons ain s;seeLabbée al.(2017)
o a de ailed explana ion.
2.2. A Se -Pa i ioning Fo mula ion
F om a linea p og amming elaxa ion poin o iew,
he p eceding o mula ion is no he s onges one, bu
i p o ides a good comp omise be ween he numbe o
equi ed cons ain s and he quali y o i s linea e-
laxa ion bound; see Labbé e al. (2017). Fu he , i al-
lows sol ing o op imali y p oblems o mode a e size.
Oneo i sd awbacksis heuseo acubicnumbe o
a iables, which can be p ohibi i e o la ge n.A
second impo an p oblem o mos known o mula-
ions o DOMP is hei high deg ee o symme y in
case o alloca ion cos s cij o weigh s (λk)wi hmany
ies.
These easons mo i a e he in oduc ion o a new
o mula ion based on a di e en a ionale. We ob-
se e ha a solu ion o DOMP is a pa i ion o he
clien s oge he wi h hei posi ions in he so ed ec o
o cos sso ha eachsubse o clien sin hepa i ionis
alloca ed o he same acili y.
Le us conside se s o couples (i,k),whe e hefi s
componen e e s o a clien iand he second o a po-
si ion k,namelyS{(i,k): o some i∈I,k∈K}.Fu -
he , we deno e by 3(I×K) he amily o all se s S o
which all fi s ( espec i ely, second) coo dina es o i s
couples a e di e en .
Associa ed wi h each se Sand acili y j,wedefine a
a iable yj
Sequal o one i he se Sis pa o a easible
solu ion ((i,k)∈Si xk
ij 1) and ze o o he wise.
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS 3
Le Sbe he se o couples whose fi s coo dina e
co esponds o he clien s alloca ed o a gi en acili y j
o a easible solu ion. The posi ions o hese clien s in
he solu ion, ha is, he second coo dina es o couples
in Smus be compa ible wi h he anking o all he
alloca ion cos s in ol ed in he solu ion. Hence, hey
mus , in pa icula , be compa ible wi h he anking o
he cos s cij o he clien s ialloca ed o j. This implies
ha , o acili y j∈J, we only need o conside subse s
o couples Sbelonging o 6(j){S∈3(I×K):cij ≤cij
o all (i,k),(i,k)∈S,andk<k}.
Because, in any easible solu ion, each clien imus
be alloca ed o a unique acili y jand i s alloca ion cos
mus occupy a unique posi ion kin he so ed lis , he
ollowing ela ionship holds:
xk
ij ∑
S∈6(j):(i,k)∈S
yj
S,i,j∈I,k∈K.(10)
Nex , we can e alua e he cos cj
Sinduced by he se S
p o ided ha i s clien s a e assigned o acili y jin a
easible solu ion:
cj
S∑
(i,k)∈S
λkcij.(11)
To simpli y he p esen a ion in he ollowing we de-
no e by (i,·) any couple whose fi s en y is i ega dless
o he alue o he second en y. Analogously, (·,k)
deno es any couple whose second en y is k ega dless
o he alue o he fi s en y.
The ollowing alid o mula ion uses a iables yj
S
and cons i u es ou mas e p oblem (MP):
(MP)min ∑
j∈I∑
S∈6(j)
cj
Syj
S(12)
s. .∑
j∈I∑
S∈6(j):
(i,·)∈S
yj
S1i∈I(13)
∑
j∈I∑
S∈6(j):
(·,k)∈S
yj
S1k∈K(14)
∑
S∈6(j)
yj
S≤1j∈I(15)
∑
j∈I∑
S∈6(j)
yj
S≤p(16)
∑
n
i1∑
n
j1∑
S∈6(j):
(i,k)∈S
ij≤ ij
yj
S+∑
S∈6(j):
(i,k−1)∈S
ij≥ ij
yj
S
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
≤n2k∈K,k 1(17)
yj
S∈{0,1}S∈6(j),j∈I.
(18)
The objec i e unc ion (12) accoun s o he so ed
weigh ed cos o any easible solu ion. Cons ain s (13)
ensu e ha each clien appea s in exac ly one se S.
Cons ain s (14) ensu e ha each posi ion is aken
by exac ly one clien appea ing in one se S.Con-
s ain s (15) gua an ees ha each acili y jse es a
mos one se So clien s. Inequali y (16) s a es ha a
mos p acili ies will be opened. By he ollowing amily
o inequali ies (17), we en o ce he co ec so ing o
he cos s in any easible solu ion. Finally, he a iables
a e bina y.
One can ela e MP and WOC. Fi s , ema k ha , o
a gi en acili y j, he e is a mos one cos cij ha
occupies a gi en posi ion k. Hence, he ollowing
cons ain s a e alid o WOC:
∑
i∈I
xk
ij ≤yj,j∈I,k∈K.(19)
Le WOC+deno e he o mula ion gi en by (2)–(8)
and (19) and conside he Dan zig–Wol e e o mu-
la ion o WOC+in which cons ain s (5), (19), and (8)
cons i u e he subp oblem. The subp oblem can be
decomposed by acili y.
On he one hand, he easible poin s o he sub-
p oblem o a acili y jco espond one o one o he se s
S∈3(I×K).Hence, hisDan zig–Wol e e o mula-
ion o WOC+is gi en by he mas e p oblem in
which we conside a iables yj
S o all S∈3(I×K)
(ins ead o only S∈6(j)). Mo e p ecisely, he a i-
ables o WOC+a e ela ed o he a iables yj
S h ough
he ollowing wo equa ions:
xk
ij ∑
S∈3(I×K):(i,k)∈S
yj
Si,j∈I,k∈K
and
yj∑
S∈3(I×K)
yj
Sj∈I.
Mo eo e , cons ain s (13) co espond o cons ain s
(3), cons ain s (14) o(4), cons ain s (16) o(6), and
cons ain s (17) o(7). Finally, cons ain s (15)cons i-
u e he “con exi y”cons ain s o he subp oblems.
On he o he hand, i is easy o see ha he poly-
hed on o each subp oblem, defined by cons ain s (5)
and (19) oge he wi h xk
ij ≥0andyj≤1, is in ege .
This implies ha he linea elaxa ions o WOC+and
MP in which all se s S∈3(I×K)a e conside ed
p o ide he same bound. By es ic ing he subse s
S o be conside ed o each acili y j o belong o 6(j),
ou o mula ion MP p o ides, hus, a s onge model.
The compu a ional expe imen s p esen ed in Sec ion 4.3
show ha he e exis ins ances o which he linea
elaxa ion o MP p o ides a s ic ly be e (highe )
lowe bound han he linea elaxa ion o WOC.
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
4INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS
Fo mula ion MP can be s eng hened by adding alid
inequali ies bo owed om WOC. Indeed, one can
ansla e alid inequali ies (9)in e mso heyj
S a i-
ables so ha hey can be used in he se pa i ion
o mula ion o DOMP. The ansla ion o (9) esul sin
∑
S∈6(j):
(i,k)∈S
ij≤ ij
yj
S+∑
S∈6(j):
(i,k−1)∈S
ij≥ ij
yj
S≤1,i,j∈I,k∈K,k 1.
(20)
2.3. Column Gene a ion o Sol e he Linea
Relaxa ion o MP (LRMP)
Because he numbe o a iables in MP is oo la ge o
be handled di ec ly, in his sec ion, we desc ibe a
column gene a ion app oach o sol e i .
Le (α, β, γ, δ, ) be he dual a iables associa ed,
espec i ely, o cons ain s (13)–(17). The dual p oblem
DP o LRMP is
(DP)max ∑
i∈I
αi+∑
k∈K
βk−∑
j∈I
γj−pδ−∑
k∈K:
k1
n2k
(21)
s. .∑
i∈I:
(i,·)∈S
αi+∑
k∈K:
(·,k)∈S
βk−γj−δ
−∑
i∈I∑
j∈I∑
(i,k)∈S:
ij≥ ij
k1
k+∑
(i,k)∈S:
ij≤ ij
kn
k+1
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
≤cj
S
j∈I,S∈6(j)
(22)
δ, γj,
k≥0j∈I,k∈K,k 1.(23)
To apply he column gene a ion p ocedu e, le us
assume ha we a e gi ena se o columns ha definea
es ic ed mas e p oblem and deno e i s linea e-
laxa ion by ReLRMP. This p oblem is sol ed o op-
imali y, and (α∗,β
∗,γ
∗,δ
∗,
∗) ep esen s i s op imal
dual solu ion. See Example 1.The educedcos ,cj
S,o
column yj
S,namelycj
Scj
S−zj
S,isgi enby
cj
Scj
S+γ∗
j+δ∗+∑
i∈I∑
j∈I∑
(i,k)∈S:
ij≥ ij
k1
∗
k+∑
(i,k)∈S:
ij≤ ij
kn
∗
k+1
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
−∑
i∈I:
(i,·)∈S
α∗
i−∑
k∈K:
(·,k)∈S
β∗
k.(24)
I cj
S≥0 o allj,S∈6(j), hecu en solu iono ReLRMP
is also op imal o he LRMP, and he column gene a ion
p ocedu e s ops.
O he wise, one has iden ified one (some) new col-
umn(s) o be added o he cu en educed mas e
p oblem o p oceed u he . In each i e a ion, ReLRMP
and i s educed cos s p o ide lowe and uppe bounds
o he LRMP. Indeed i holds ha (Des osie s and
Lübecke 2005)
zReLRMP +p·min
j∈I,S∈6(j)cj
S≤zLRMP ≤zReLRMP,(25)
zReLRMP +∑
j∈I
min
S∈6(j)cj
S≤zLRMP ≤zReLRMP,(26)
whe e zReLRMP and zLRMP deno e he op imal alue o
ReLRMP and LRMP, espec i ely.
Example 1. Conside he ollowing ec o λ(4,2,1),
cos ma ix C, and p ecedence ma ix R:
C
136
318
681
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠,R
146
528
793
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠.
Fo n3, he e a e 33 di e en se s o couples (i,k)
in 6.
S1{(1,1)}
S2{(1,2)}
S3{(1,3)}
S4{(2,1)}
S5{(2,2)}
S6{(2,3)}
S7{(3,1)}
S8{(3,2)}
S9{(3,3)}
S10 {(1,1),(2,2)}
S11 {(1,1),(2,3)}
S12 {(1,1),(3,2)}
S13 {(1,1),(3,3)}
S14 {(1,2),(2,1)}
S15 {(1,2),(2,3)}
S16 {(1,2),(3,1)}
S17 {(1,2),(3,3)}
S18 {(1,3),(2,1)}
S19 {(1,3),(2,2)}
S20 {(1,3),(3,1)}
S21 {(1,3),(3,2)}
S22 {(2,1),(3,2)}
S23 {(2,1),(3,3)}
S24 {(2,2),(3,1)}
S25 {(2,2),(3,3)}
S26 {(2,3),(3,1)}
S27 {(2,3),(3,2)}
S28 {(1,1),(2,2),(3,3)}
S29 {(1,1),(2,3),(3,2)}
S30 {(1,2),(2,1),(3,3)}
S31 {(1,2),(2,3),(3,1)}
S32 {(1,3),(2,1),(3,2)}
S33 {(1,3),(2,1),(3,2)}.
The se s 6(j)a e he ollowing:
6(1){S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,
S13,S15,S17,S22,S23,S25,S28},
6(2){S1,S2,S3,S4,S5,S6,S7,S8,S9,S12,S13,S14,
S17,S18,S19,S22,S23,S25,S30},
6(3){S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S15,
S16,S20,S21,S24,S26,S27,S31}.
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS 5

We conside as ini ial pool o columns he a iables
y1
18 and y3
8. Wi h his se o a iables, he ReLRMP is
(
ReLRMP
)
min+2y2
5+10y1
13
s. +y1
13 ≥1i1
+y2
5≥1i2
+y1
13 ≥1i3
+y1
13 ≥1k1
+y2
5≥1k2
+y1
13 ≥1k3
−y1
13 ≥−1j1
−y2
5≥−1j2
≥−1j3
−y2
5−y1
13 ≥−2
−8y2
5−y1
13 ≥−9k2
−2y2
5−3y1
13 ≥−9k3
y≥0.
Ac ually, we a e in e es ed in i s dual p oblem:
(
DP
)
max +α1+α2+α3+β1+β2+β3−γ1−γ2−γ3
−2δ−92−93
s. .+α2+β2−γ2−δ−82−23≤2y2
5
()
+α1+α3+β1+β3−γ1−δ−2−33≤10
y1
13
()
α, β, γ, δ,  ≥0.
Sol ing (DP), he solu ion is α22,β
310,α
1α3
β1β2δ230 and he alue o he objec i e
unc ion is 12.
2.4. Sol ing he P icing Subp oblem
Al hough any column yj
Swi h nega i e educed cos
may be added o ReLRMP, we ollow a s a egy ha
iden ifies he mos nega i e educed cos o each
acili y j. This app oach may gi e ise o se e al
candida e columns (mul iple p icing; see Ch ´
a al
1983), which is ad an ageous o his p ocedu e.
To do ha , o each acili y j∈I,wesol easub-
p oblem o find he column yj
S,S∈6(j), wi h mini-
mum educed cos . This se Smus be such ha he e
is a mos one couple (i,·) o each clien iand one
couple (·,k) o each posi ion k.Fu he mo e, hese S
mus enjoy ha he alloca ion cos s i i s couples a e
compa ible. We sol e his p oblem by he ollowing
dynamic p og amming algo i hm.
Le dk
ij be he con ibu ion o he pai (i,k) o he
educed cos o any column yj
Ssuch ha (i,k)∈S.
Depending on he alues o k,dk
ij is gi en by
dk
ij 
λkcij +∑
i∈I∑
j∈I:
ij≤ ij
k+1−αi−βki k1,
λkcij +∑
i∈I∑
n
j∈I:
ij≥ ij
k+∑
i∈I∑
j∈I:
ij≤ ij
k+1−αi−βk
i k2,...,n−1,
λkcij +∑
i∈I∑
j∈I:
ij≥ ij
k−αi−βk,i kn.
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩(27)
Then, o a acili y j, hep oblemo finding he a -
iable yk
Swi h minimum educed cos s can be o mu-
la ed as
min
S∈6(j)cj
Sγ∗
j+δ∗+∑
(i,k)∈S
dk
ij.(28)
Now, o each acili y j,wedefine a ma ix Djas
ollows:
Dj
d1
i1jd2
i1j··· dn
i1j
d1
i2j
.
.
...
.
d1
injdn
inj
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
,(29)
whe e i1,i2,...,inis a pe mu a ion o he indices i
1,...,nsuch ha ci1j≤ci2j≤···≤cinj.
Example 2 (Con inuing om Example 1).We illus a e
he p ocedu e ha compu es he elemen s dk
ij o all
i,k1,...,no he ma ix D1(j= 1).
d1
11 λ1c11 + 112−α1−β14
d2
11 λ2c11 +n2− 11 +1
()
2+ 113−α1−β22
d3
11 λ3c11 ++ n2− 11 +1
()
3−α1−β3−9
d1
21 λ1c21 + 212−α2−β110
d2
21 λ2c21 +n2− 21 +1
()
2+ 213−α2−β24
d3
21 λ3c21 ++ n2− 21 +1
()
3−α2−β3−9
d1
31 λ1c31 + 312−α3−β124
d2
31 λ2c31 +n2− 31 +1
()
2+ 213−α3−β212
d3
31 λ3c31 ++ n2− 31 +1
()
3−α3−β3−4
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
6INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS
Because 11 < 21 < 31, he alid pe mu a ion is (1,2,3).
This implies ha
D1
42−9
10 4 −9
24 12 −4
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
i1
i2
i3.
By using Dj,weob ain ha ase Sbelongs o 6(j)i and
only i e e y (i1,k1)and (i2,k2)∈Ssuch ha i1<i2:
k1<k2.
Ou dynamic p og amming algo i hm o ob ain he
minimum educed cos o each j∈Jbuilds upon his
obse a ion by cons uc ing a solu ion o a educed
e sion o (28)inwhichonly hefi s ilclien s and he
fi s kposi ions a e conside ed.
Fo each couple (il,k),wedefine a unc ion
gj(il,k)min {cj
S:S∈6j
()and o all
i
l,k
()
∈S:i
l≤iland k≤k}(30)
and we deno e an op imal solu ion o his es ic ed
op imiza ion p oblem by Sj(il,k).
Hence, he op imal alue o p oblem (28)isequal o
gj(in,n)+δ+γjand a co esponding op imal solu ion
by Sj(in,n).
Ou ecu si e p ocedu e compu es gj(il,k)and
Sj(il,k) o inc easing alues o land kand exploi s he
ollowing easibili y condi ions on S:
i. Fo each clien i(posi ion k), a mos one couple
con aining i(posi ion k)belongs oS.
ii. I (il1,k1)and (il2,k2)∈Sand k1<k2, hen il1j< il2j.
Mo e p ecisely, i (il,k)belongs o Sj(il,k), hen, om
(i), i ollows ha gj(il,k)gj(il−1,k−1)+dk
ilj.O he -
wise, Sj(il,k)may con ain a couple (il,k)wi hk≤k−1
o a couple (il,k)wi h l≤l−1 bu no bo h; o he -
wise, condi ion (ii) would be iola ed. Hence, in his
case, gj(il,k)min{gj(il−1,k−1),gj(il,k−1),gj(il−1,k)}.
Combining he wo cases, we ob ain he ollowing
ecu ence ela ion o l,k2,...,n:
gj(il,k)min{gj(il−1,k−1)+dk
ilj,gj(il−1,k−1),
gj(il,k−1),gj(il−1,k)}.(31)
Algo i hm 1 (P icing Subp oblem Algo i hm)
1: gj(i1,1)min{0,d1
i1j};
2: i gj(i1,1)d1
i1j<0, hen
3: Sj(i1,1){(i1,1)};
4: else
5: Sj(i1,1)∅;
6: end i
7: o k2,...,n,do
8: gj(i1,k)min{dk
i1j,gj(i1,k−1)};
9: i gj(i1,k)gj(i1,k−1), hen
10: Sj(i1,k)Sj(i1,k−1);
11: else
12: Sj(i1,k){(i1,k)};
13: end i
14: end o
15: o l2,...,n,do
16: gj(il,1)min{d1
ilj,gj(il−1,1)};
17: i gj(il,1)gj(il−1,1), hen
18: Sj(il,1)Sj(il−1,k);
19: else
20: Sj(il,1){(il,1)};
21: end i
22: end o
23: o k,l2,...,n,do
24: gj(il,k)min{gj(il−1,k−1)+dk
ilj,gj(il−1,k−1),
gj(il,k−1),gj(il−1,k)};
25: i gj(il,k)gj(il−1,k−1), hen
26: Sj(il,k)Sj(il−1,k−1);
27: else i gj(il,k)gj(il,k−1), hen
28: Sj(il,k)Sj(il,k−1);
29: else i gj(il,k)gj(il−1,k), hen
30: Sj(il,k)Sj(il−1,k);
31: else
32: Sj(il,k)Sj(il−1,k−1)∪{(il,k)};
33: end i
34: end o
Ob iously, i , a he end o he p ocedu e, gj(in,n)+
δ+γjis nega i e, he a iable yj
Sj(in,n)is a good can-
dida e o be chosen in he nex i e a ion o he column-
gene a ion scheme.
I we sol e his p oblem o all j,wege cj
RminScj
S,
and i cj
R<0, we can ac i a e (a leas ) yj
R.Nex ,we
sol e a new ReLRMP wi h his ( hese) new ac i a ed
a iable(s).
Rema k 1. Compu ing each ma ix Djcan be done in
O(n2). Nex , ob aining gj(in,n) equi es he e alua ion
o he unc ion gj(i,k) o all i∈Iand k∈K. Acco ding
o he algo i hm, he e alua ion o each gj(i,k)is done in
cons an ime. Sol ing he p icing subp oblem amoun s
o e alua ing gj(in,n) o all j∈I. The e o e, he en i e
p icing subp oblem can be sol ed in O(n3) ime.
Example 3 (Con inuing om Example 2).We show he
compu a ion o he gj(in,n)and Sj(in,n) o j1.
g1(i1,1)min{0,4}0,S1(i1,1)∅
g1(i1,2)min{2,0}0,S1(i1,2)∅
g1(i1,3)min{−9,0}−9,S1(i1,3){(1,3)}
g1(i2,1)min{10,0}0,S1(i2,1)∅
g1(i3,1)min{24,0}0,S1(i3,1)∅
g1(i2,2)min{0+4,0,0,0},S1(i2,2)∅
g1(i3,2)min{0+12,0,0,0},S1(i3,2)∅
g1(i2,3)min{0−9,0,−9,0},S1(i2,3){(1,3)}
g1(i3,3)min{0−4,0,−9,0},S1(i3,3){(1,3)}
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS 7
We ha e ob ained g1(i3,3)−9, and S1(i3,3)S3is he
po en ial se o be used because i s educed cos is neg-
a i e. The co esponding educed cos c1
3g1(i3,3)+
δ+γ1−9+0+0−9<0. Hence, we ac i e a iable y1
3.
Nex , he p ocess con inues wi h he ollowing
acili ies, ha is, j2,3. In his example, he op imal
solu ion can be ce ifieda e ou comple ei e a ions
o he p eceding p ocess.
2.5. Dealing wi h In easibili y
One impo an issue when implemen ing a column-
gene a ion p ocedu e o sol e a linea op imiza ion
p oblem is how o deal wi h in easibili y. This is es-
pecially c ucial i he p ocedu e is used wi hin a
b anch-and-bound scheme o sol e he linea elax-
a ion o he p oblem a e e y node o he b anching
ee. To handle his, we eso o he so-called Fa kas
p icing. This me hod was used p e iously, o he bes
o ou knowledge, in Günlük e al. (2005) and Ceselli
e al. (2008). The e m “Fa kas p icing”was coined in
Gam a h (2010).
Acco ding o Fa kas’lemma (Fa kas 1894), a e-
duced mas e p oblem is in easible i i s associa ed
dual p oblem is unbounded. Thus, o eco e easi-
bili y in he ReLRMP, we ha e o e oke he ce ifica e
o unboundedness in he dual p oblem. This can be
done by adding cons ain s o i . Because we a e only
in e es ed in eco e ing easibili y in ReLRMP, one
can p oceed in he same way as o he usual p icing
bu wi h null coe ficien s in he objec i e unc ion o
he p imal. In his way, he Fa kas dual p oblem is
max ∑
i∈I
αi+∑
k∈K
βk−∑
j∈I
γj−pδ−∑
k∈K:
k1
n2k(32)
s. .∑
i∈I:
(i,·)∈S
αi+∑
n
k∈K:
(·,k)∈S
βk−γj−δ
−∑
i∈I∑
j∈I∑
(i,k)∈S:
ij≥ ij
k1
k+∑
(i,k)∈S:
ij≤ ij
kn
k+1
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
≤0j∈I,S∈6(j)
(33)
δ, γjk≥0j∈I,k∈K,
k 1.(34)
To iden i y new a iables ha make he educed mas e
p oblem easible, we use ou dynamic p og amming ap-
p oach in which we eplace he column cos s cj
Sby ze os.
Fa kas p icing is an impo an elemen in ou ap-
p oach because i allows s a ing he column gene a ion
algo i hm wi h an emp y pool o columns al hough his
is no ad isable. Fu he mo e, Fa kas p icing is c ucial
in he b anching phase o eco e easibili y (whene e
possible) in hose nodes o he b anching ee whe e i
is los a e fixing a iables.
3. A B anch-P ice-and-Cu Implemen a ion
In his sec ion, we p ecise se e al componen s o he
implemen a ion o ou se -pa i ioning o mula ion
based on a column gene a ion app oach. B&P&C is a
b anch-and-cu scheme ha sol es he linea elax-
a ion a each node o he b anching ee wi h he
column gene a ion algo i hm p e iously desc ibed
and may apply cu s o imp o e he ob ained lowe
bound. (The eade is e e ed o Doulabi e al. (2016)
o ano he ecen implemen a ion o a B&P&C.)
Unless o he wise specified, o calib a e he bes
choice o he di e en pa ame e s used in ou B&P&C,
we ha e pe o med a p elimina y compu a ional s udy
based on a se o 60 ins ances wi h sizes n20,30 and
wi h a ime limi o 1,800 seconds. Those a e he small-
es ins ances ha we e en ually use in Sec ion 4.
3.1. Uppe Bound o he Mas e P oblem: A GRASP
Heu is ic and an Ini ializa ion S age
A heu is ic algo i hm ha gene a es a good easible
solu ion o MP p o ides a p omising pool o ini ial
columnsaswellasagooduppe bound.
GRASP (Feo and Resende 1989,1995) is a well-
known heu is ic echnique ha usually exhibi s good
pe o mance in sho compu ing ime. In ou case, i
consis s o a mul is a g eedy algo i hm o cons uc a
se o p acili ies om a andomly gene a ed se o
acili ies wi h smalle ca dinali y. Following Pue o
e al. (2014), we ha e chosen, in a g eedy manne , an
ini ial se o p/2 acili ies. Nex , we imp o e his
ini ial solu ion by pe o ming a fixed numbe o i -
e a ions o a local sea ch p ocedu e.
The g eedy algo i hm adds i e a i ely a new acili y
o he cu en se o open acili ies, choosing he one
wi h he maximum imp o emen o he objec i e alue.
The local sea ch consis s o an in e change heu is ic
be ween open and closed acili ies. The pseudocode o
he GRASP used o sol e he p oblem is desc ibed in
Algo i hm 2.
Algo i hm 2 (GRASP o DOMP)
1: Inpu (n,p,C,λ,n1,n2,q);
2: o n1 eplica ions, do
3: Pa ialSolu ion ←Cons uc RandomizedPa ial-
Solu ion(q);
4: Solu ion ←Cons uc G eedySolu ion(Pa ial-
Solu ion);
5: o n2i e a ions, do
6: Solu ion ←LocalSea ch(Solu ion);
7: Bes Solu ion ←Upda eSolu ion(Solu ion, Bes -
Solu ion);
8: end o
9: end o
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
8INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS
Fi s o all, we would like o poin ou he ema kable
beha io o he GRASP heu is ic o his p oblem.
To illus a e he app op ia eness o ou heu is ic, we
ha e sol ed o op imali y a numbe o ins ances o he
p oblem using he mixed in ege p og amming (MIP)
o mula ion o be compa ed wi h hose gi en by ou
GRASP. In all ins ances, up o a size o n400, he
solu ion p o ided by GRASP is always as good as he
one ob ained by he any o ou MIP o mula ions wi h
a CPU ime limi o 7,200 seconds; see Sec ion 4.
Mo eo e , i is no only ad isable o use he GRASP
heu is ic because i p o ides a e y good uppe bound,
hus, helping he explo a ion o he sea ching ee by
p uning many b anches o he b anch-and-bound ee,
bu in addi ion, he cons uc ion phase o he heu is ic
also p o ides a e y p omising pool o ini ial columns
o he B&P&C, in combina ion wi h he echnique
desc ibed in he ollowing.
Because we a e sol ing he LRMP wi hou gene -
a ingi sen i ese o a iables,using hep imalsim-
plex algo i hm, he goal o he ini ializa ion phase is o
find an ini ial se o columns ha allows sol ing he MP
by pe o ming a small numbe o i e a ions in he
column gene a ion ou ine. We c ea e a iables using
amodifica ion o he local sea ch ou ine o he GRASP
algo i hm. E e y ime ha we find a p omising ea-
sible solu ion in he heu is ic, we c ea e he a i-
ables ha define ha solu ion (C ea eSe Va iables(J)).
Algo i hm 3p esen s he pseudocode o his p ocess.
Func ion C ea eSe Va iables(J) de e mines he cos s
in ol ed in he solu ion, ha is, he minimum o each
clien among he open acili ies. Then hose cos s a e
o de ed o de e mine he posi ion o each clien . Once
we know he couples (i,k)assigned o each open
acili y, he co esponding a iables a e added o he
pool.
Example 4 (Con inuing om Example 1).We illus a e
he use o he unc ion C ea eSe Va iables(J) wi h he
ollowing se J{1,3}(open acili ies). The alloca ion
cos s o his se Jo open acili ies a e c11 1,c21 3,
c33 1. Acco ding o R, he anks o hese cos s a e
11 1< 33 3< 21 5. Thus, we ge he couples (1,1),
(3,2)and (2,3). This means ha clien 1 goes o acil-
i y 1 in posi ion 1, clien 3 goes o acili y 3 in posi ion 2,
and clien 2 goes o acili y 1 in posi ion 3. The e o e,
he a iables y1
{(1,1),(2,3)} and y3
{(3,2)} a e added o he pool.
Algo i hm 3 (Ini ial Columns)
1: Inpu (|J|p);
2: ¯
zz(J); C ea eSe Va iables(J);
3: o n2i e a ions, j1∈J,j2∈¯
J,do
4: i z((J {j1}) ∪ {j2}) <¯
z, hen
5: ¯
zz((J {j1}) ∪ {j2});J(J {j1}) ∪ {j2};
C ea eSe Va iables(J);
6: end i
7: end o
To es he use ulness o GRASP in sol ing p ob-
lem ins ances, Table 1 epo s esul s o he 60 in-
s ances o sizes n20,30, enabling o no he use o
he GRASP. I shows a e age esul s o CPU ime
(Time(s)), pe cen age gap a e mina ion, i.e., 100(zUB −
zLB)/zLB (Gap(%)), and numbe o unsol ed p oblems
(in pa en heses), numbe o nodes |Nodes|, and num-
be o a iables (|Va s|).
Acco ding o Table 1, i is clea ly ad isable o use
he uppe bound p o ided by he GRASP heu is ic: i
educes he numbe o nodes, hus imp o ing he size
o he b anch-and-bound ee.
In Table 2, he same in o ma ion as in Table 1is
epo ed bu only o he ins ances sol ed o op i-
mali y wi hin he ime limi . One can obse e om
his able ha enabling he use o GRASP educes he
CPU ime and numbe o nodes o he B&B ee and, a
he same ime, educes he o e all numbe o a i-
ables equi ed by he B&P&C. In addi ion, by using
he GRASP heu is ic, B&P&C is able o sol e six mo e
ins ances. Fo hose ins ances o which B&P&C does
no ce i y op imali y, GRASP p o ides an uppe
bound ha leads o an a e age gap o 0.89%. Finally,
wi hou he use o GRASP, in many cases, no easible
solu ions a e ound wi hin he ime limi , and hus, no
pe cen age gap can be epo ed.
Ou esul s show ha , by using he GRASP heu-
is ic, 2.03% o he final numbe o a iables a e
gene a ed when applying Algo i hm 3.Thecombi-
na ion o he incumben solu ion (gi en by GRASP)
and ha ini ial pool o a iables leads o sol ing he
conside ed ins ances as e , equi ing a ewe numbe
o nodes and a iables o ce i y op imali y.
Figu e 1 epo s he pe o mance p ofile o GAP
e sus numbe o sol ed ins ances wi hin a ime limi
o 1,800 seconds o he 60 ins ances wi h sizes n
20,30. The dashed line epo s esul s using GRASP
and he solid one wi hou i . I is in e es ing o poin
ou ha , when GRASP is enabled, he B&P&C is
able o sol e o op imali y 30 ins ances, and he GAP
Table 2. CPU Time, Numbe o Nodes, and Numbe o
Va iables wi h and wi hou GRASP Heu is ic o n20,30
GRASP Time(s) |Nodes| |Va s|
Disabled 386.19 272 10,962
Enabled 147.77 79 6,062
No e. Summa y o sol ed ins ances.
Table 1. CPU Time, Numbe o Nodes, and Numbe o
Va iables wi h and wi hou GRASP Heu is ic o n20,30
GRASP Time(s) Gap(%) |Nodes| |Va s|
Disabled 1,107.21 —(36) 158 12,850
Enabled 965.31 0.89 (30) 88 9,907
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS 9
column #unsol ed by Memo y(MB). This new column
shows he a e age equi ed memo y o sol e he co -
esponding se o ins ances. In ha able, ex ensi e
compu a ional expe imen s a e epo ed o ins ances up
o 400 poin s. We would like o ema k ha he inc ease
o he complexi y wi h espec o he ins ance sizes o
|Va s|,|Cu s|,Memo y(MB),andGap(%)is mode a e
(almos linea ), which allows one o handle DOMP
p oblemso la ge size.Mo eo e heGap(%)a e simila
o hose epo ed in Table 5.
To conclude, he esul s show ha he o e all pe -
o mance o B&P&C(MP) in sol ing DOMP is sys em-
a ically be e han he b anch-and-cu o mula ion
B&C(WOC) o ins ances o n≥70. In addi ion, i is
wo h no ing ha B&C(WOC) is no e en able o sol e
he linea elaxa ion o DOMP p oblems o sizes n≥100.
This ac shows he use ulness o ou new app oach.
5. Conclusions
This pape p esen s a fi s b anch-p ice-and-cu ,
B&P&C(MP), algo i hm o sol ing DOMP. This
app oach is based on an ex ended o mula ion using
an exponen ial numbe o a iables coming om a se -
pa i ioning model. Elemen s in he pa i ionsa e couples
con aining in o ma ion abou a clien and i s so ed
posi ion in he so ed sequence o alloca ion cos s. To
add ess he solu ion o his o mula ion, we de elop a
column gene a ion algo i hm, and we p o e ha he p ic-
ing ou ine is polynomially sol able by a dynamic p o-
g amming algo i hm. We embed he column gene a ion
algo i hm wi hin a b anch-and-p ice amewo k. Fu -
he mo e, we adap p ep ocessing and inco po a e ami-
lies o alid inequali ies ha imp o e i s pe o mance.
Ex ensi e compu a ional esul s compa e he pe o -
manceo ou B&P&C(MP)agains hemos ecen
algo i hm in he li e a u e o DOMP, B&C(WOC),
showing ha , o he la ges conside ed ins ances,
B&P&C(MP) pe o ms be e , and i equi es less mem-
o y o upload and un he models. The me hodology
p esen ed in his pape is able o sol e sized ins ances
o DOMP ha had ne e been sol ed in he li e a u e.
Table 6. Nume ical Resul s o B&P&C(MP) o Bigge Ins ances
n p Time(s)|Va s||Nodes||Cu s|Memo y(MB)Gap(%)
100 50 7,201.10 23,057 2 5,221 311 2.43
120 60 7,200.54 29,209 1 6,992 424 2.54
140 70 7,202.11 34,222 2 6,805 449 2.87
160 80 7,201.08 41,811 1 8,069 574 3.13
180 90 7,201.24 50,523 1 7,961 656 3.48
200 100 7,201.61 59,931 1 9,050 805 3.96
220 110 7,201.39 57,685 1 11,097 806 4.39
240 120 7,200.94 63,710 1 11,487 874 4.43
260 130 7,201.83 73,143 1 9,772 910 5.05
280 140 7,200.98 83,892 1 9,592 1,037 6.19
300 150 7,201.74 87,444 1 10,811 1,076 6.83
100 33 7,201.10 29,974 2 5,864 562 3.81
120 40 7,201.12 37,204 5 5,433 621 4.80
140 46 7,200.98 48,286 2 7,953 894 4.47
160 53 7,201.55 57,060 3 7,159 926 5.01
180 60 7,203.85 70,077 1 8,997 1,188 5.99
200 66 7,200.55 67,417 1 11,416 1,199 6.16
220 73 7,201.41 71,731 2 9,356 1,073 6.88
240 80 7,202.02 84,466 2 10,093 1,324 9.80
260 86 7,200.74 92,401 1 10,505 1,390 9.54
280 93 7,201.68 105,535 1 13,265 1,728 9.01
300 100 7,200.28 114,427 1 15,595 2,034 9.41
100 25 7,202.69 31,218 1 7,034 801 4.73
120 30 7,200.98 40,074 1 6,818 922 5.91
140 35 7,203.38 49,539 1 8,466 1,162 5.83
160 40 7,201.35 58,464 1 10,688 1,465 7.29
180 45 7,203.43 72,146 1 10,329 1,674 8.70
200 50 7,201.88 62,568 1 10,252 1,364 11.27
220 55 7,203.56 74,359 1 9,985 1,515 10.34
240 60 7,200.19 80,228 1 9,745 1,422 11.57
260 65 7,200.54 99,628 1 7,944 1,346 11.77
280 70 7,203.63 109,544 1 4,187 1,247 11.32
300 75 7,200.79 128,462 1 3,844 1,261 12.26
400 200 86,400.42 158,287 1 9,308 1,183 7.07
400 133 86,401.23 178,265 1 13,652 2,764 11.26
400 100 86,401.11 236,973 1 7,582 3,125 10.29
No e. Fo ins ances wi h n = 400, he ime limi was se o 24 hou s.
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
16 INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS

Acknowledgmen s
The au ho s hank he SCIP eam (Gam a h e al. 2016) o he
help ul ad ice. They also hank he help ul epo s om wo
anonymous e e ees ha led o imp o ing he quali y o he
pape .
Re e ences
Ach e be g T, Koch T, Ma in A (2005) B anching ules e isi ed.
Ope . Res. Le . 33(1):42–54.
Applega e D, Bixby R, Ch ´
a al V, Cook W (1995) Finding cu s in he
TSP (a p elimina y epo ). DIMACS Technical Repo 95-05,
DIMACS, Ru ge s Uni e si y, New B unswick, NJ.
A ella P, Sassano A, Vasil’e I (2006) Compu a ional s udy o la ge-
scale p-median p oblems. Ma h. P og amming 109(1):89–114.
Ba nha C, Johnson E, Nemhause G, Sa elsbe gh M, Vance P (1998)
B anch-and-p ice: Column gene a ion o sol ing huge in ege
p og ams. Ope . Res. 46(3):316–329.
Beale E, Tomlin J (1970) Special acili ies in a gene al ma hema ical
p og amming sys em o non-con ex p oblems using o de ed
se s o a iables. Law ence J, ed. P oc. 5 h In e na . Con . Ope . Res.
(Ta is ock Publica ions, London), 447–454.
Benichou M, Gau hie J, Gi ode P, Hen ges G, Ribie e G, Vincen O
(1971) Expe imen s in mixed-in ege p og amming. Ma h. P o-
g amming 1(1):71–94.
Boland N, Dom´
ınguez-Ma ´
ın P, Nickel S, Pue o J (2006) Exac
p ocedu es o sol ing he disc e e o de ed median p oblem.
Compu . Ope . Res. 33(11):3270–3300.
Ceselli A, Righini G (2005) A b anch-and-p ice algo i hm o he
capaci a ed p-median p oblem. Ne wo ks 45(3):125–142.
Ceselli A, Libe a o e F, Righini G (2008) A compu a ional e alua ion
o a gene al b anch-and-p ice amewo k o capaci a ed ne -
wo k loca ion p oblems. Ann. Ope . Res. 167(1):209–251.
Ch ´
a al V (1983) Linea P og amming (W. H. F eeman and Company,
New Yo k).
Con e as I, D´
ıaz J, Fe n´
andez E (2011) B anch and p ice o la ge-
scale capaci a ed hub loca ion p oblems wi h single assignmen .
INFORMS J. Compu . 23(1):41–55.
Deleplanque S, Labbé M, Ponce D, Pue o J (2018) An ex ended
e sion o a b anch-p ice-and-cu p ocedu e o he disc e e
o de ed median p oblem. P ep in , submi ed Feb ua y 9, h ps://
a xi .o g/abs/1802.03191.
Des osie s J, Lübecke M (2005) A p ime in column gene a ion.
Desaulnie s G, Des osie s J, Salomon MM, eds. Column Gene -
a ion (Sp inge , Bos on), 1–32.
Dom´
ınguez-Ma ´
ın P, Nickel S, Hansen P, Mladeno ic N (2005)
Heu is ic p ocedu es o sol ing he disc e e o de ed median
p oblem. Ann. Ope . Res. 136(1):145–173.
Doulabi SHH, Rousseau LM, Pesan G (2016) A cons ain -p og amming-
based b anch-and-p ice-and-cu app oach ope a ing oom
planning and scheduling. INFORMS J. Compu . 28(3):432–448.
du Me le O, Vial J (2002) P oximal ACCPM, a cu ing plane me hod
o column gene a ion and Lag angean elaxa ion: Applica ion
o he p-median p oblem. Technical epo , HEC Gen`
e e, Uni-
e si é de Gen`
e e, Gene a, Swi ze land.
du Me le O, Villenue e D, Des osie s J, Hansen P (1999) S abilized
column gene a ion. Disc e e Ma h. 194(1–3):229–237.
Fa kas G (1894) A Fou ie - éle mechanikai el alkalmaz´
asai. Ma h-
ema ikai és Te mésze udom´
anyi ´
E s esi ¨
o12:457–472.
Feo TA, Resende MGC (1989) A p obabilis ic heu is ic o a compu-
a ionally di ficul se co e ing p oblem. Ope . Res. Le . 8(2):67–71.
Feo TA, Resende MGC (1995) G eedy andomized adap i e sea ch
p ocedu es. J. Global Op im. 6(2):109–133.
Fe n´
andez E, Pozo MA, Pue o J (2014) O de ed weigh ed a e age
combina o ial op imiza ion: Fo mula ions and hei p ope ies.
Disc e e Appl. Ma h. 169(31):97–118.
Fe n´
andez E, Pue o J, Rod ´
ıguez-Ch´
ıa AM (2013) On disc e e op-
imiza ion wi h o de ing. Ann. Ope . Res. 207(1):83–96.
Fe n´
andez E, Pozo MA, Pue o J, Scozza i A (2017) O de ed weigh ed
a e age op imiza ion in mul iobjec i e spanning ee p oblems.
Eu . J. Ope . Res. 260(31):886–903.
Gam a h G (2010) Gene ic b anch-cu -and-p ice. Mas e ’s hesis,
Ins i u ü Ma hema ik, Technische Uni e si ¨
a Be lin, Be lin.
Gam a h G, Fische T, Gally T, Gleixne AM, Hendel G, Koch T,
Mahe SJ, Mil enbe ge M, Mülle B, P e sch ME, e al. (2016) The
SCIP op imiza ion sui e 3.2. Technical epo 15-60, ZIB, Be lin.
Günlük O, Lad´
anyi L, de V ies S (2005) A b anch-and-p ice algo i hm
and new es p oblems o spec um auc ions. Managemen Sci.
51(3):391–406.
Johnson EL (1989) Modeling and s ong linea p og ams o mixed
in ege p og amming. Wallace S, ed. Algo i hms and Model Fo -
mula ions in Ma hema ical P og amming,NATOASISe ies, ol.51
(Sp inge , Be lin Heidelbe g), 1–43.
Labbé M, Ponce D, Pue o J (2017) A compa a i e s udy o o mu-
la ions and solu ion me hods o he disc e e o de ed p-median
p oblem. Compu . Ope . Res. 78:230–242.
Lo ena L, Senne E (2004) A column gene a ion app oach o capaci-
a ed p-median p oblems. Compu . Ope . Res. 31(6):863–876.
Ma ´
ın A, Nickel S, Vel en S (2010) An ex ended co e ing model o
flexible disc e e and equi y loca ion p oblems. Ma h. Me hods
Ope . Res. 71(1):125–163.
Ma ´
ın A, Nickel S, Pue o J, Vel en S (2009) A flexible model and
e ficien solu ion s a egies o disc e e loca ion p oblems. Dis-
c e e Appl. Ma h. 157(5):1128–1145.
Nickel S (2001) Disc e e o de ed Webe p oblems. Ope . Res. P oc. 2000:
71–76.
Nickel S, Pue o J (1999) A unified app oach o ne wo k loca ion
p oblems. Ne wo ks 34(4):283–290.
Nickel S, Pue o J (2005) Loca ion Theo y: A Unified App oach (Sp inge ,
Be lin, Heidelbe g).
Olende P, Og yczak W (2018) A e ised a iable neighbo hood
sea ch o he disc e e o de ed median p oblem. Eu . J. Ope . Res.
274(2):445–465.
Pe ea F, Pue o J (2013) Finding he nucleolus o any n–pe son co-
ope a i e game by a single linea p og am. Compu . Ope . Res.
40(10):2308–2313.
Pessoa A, Uchoa E, A agão MP, Rod igues R (2010) Exac algo-
i hm o e an a c ime-indexed o mula ion o pa allel ma-
chine scheduling p oblems. Ma h. P og amming Compu . 2(3–4):
259–290.
Ponce D, Pue o J, Ricca F, Scozza i A (2018) Ma hema ical p o-
g amming o mula ions o he e ficien solu ion o he k-sum
app o al o ing p oblem. Compu . Ope . Res. 98:127–136.
Pue o J (2008) A new o mula ion o he capaci a ed disc e e o de ed
median p oblem wi h {0,1}-assignmen . Kalcsics J, Nickel S, eds.
Ope . Res. P oc. 2007 (Sp inge , Be lin Heidelbe g), 165–170.
Pue o J, Fe n´
andez F (2000) Geome ical p ope ies o he sym-
me ical single acili y loca ion p oblem. J. Nonlinea Con ex Anal.
1(3):321–342.
Pue o J, Rod ´
ıguez-Ch´
ıa AM (2015) O de ed median loca ion p ob-
lems. Lapo e G, Nickel S, Saldanha da Gama F, eds. Loca ion
Science (Sp inge ) Heidelbe g: 249–288.
Pue o J, Pé ez-B i o D, Ga c´
ıa-Gonz´
alez CG (2014) A modified
a iable neighbo hood sea ch o he disc e e o de ed median
p oblem. Eu . J. Ope . Res. 234(1):61–76.
Pue o J, Ramos AB, Rod ´
ıguez-Ch´
ıa AM (2011) Single-alloca ion
o de ed median hub loca ion p oblems. Compu . Ope . Res. 38(2):
559–570.
Pue o J, Ramos AB, Rod ´
ıguez-Ch´
ıa AM (2013) A specialized b anch
& bound & cu o single-alloca ion o de ed median hub loca-
ion p oblems. Disc e e Appl. Ma h. 161(16–17):2624–2646.
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS 17
Pue o J, Rod ´
ıguez-Ch´
ıa AM, Tami A (2009) Minimax eg e
single- acili y o de ed median loca ion p oblems on ne wo ks.
INFORMS J. Compu . 21(1):77–87.
Pue o J, Ramos AB, Rod ´
ıguez-Ch´
ıa AM, S´
anchez-Gil MC (2016)
O de ed median hub loca ion p oblems wi h capaci y con-
s ain s. T anspo a ion Res., Pa C Eme ging Tech. 70:142–156.
Ryan DM, Fos e A (1981) An in ege p og amming app oach o
scheduling. W en A, ed. Compu e Scheduling o Public T anspo :
U ban Passenge Vehicle and C ew Scheduling (No h-Holland,
Ams e dam), 269–280.
Senne E, Lo ena L, Pe ei a MA (2005) A b anch-and-p ice app oach
o p-median loca ion p oblems. Compu . Ope . Res. 32(6):1655–1664.
S animi o ic Z, K a ica J, Dugosija D (2007) Gene ic algo i hms o
sol ing he disc e e o de ed median p oblem. Eu . J. Ope . Res.
182(3):983–1001.
Wolsey LA (1998) In ege P og amming (John Wiley & Sons, New Yo k).
Deleplanque e al.: A B anch-P ice-and-Cu P ocedu e o he DOMP
18 INFORMS Jou nal on Compu ing, A icles in Ad ance, pp. 1–18, © 2020 INFORMS