An exac column-gene a ion app oach o he
lo - ype design p oblem
Mi iam Kießling Sascha Ku z J¨o g Rambau
Augus 3, 2012
Abs ac
We conside a ashion discoun e dis ibu ing i s many b anches wi h
in eg al mul iples om a se o a ailable lo - ypes. Fo he p oblem o
app oxima ing he b anch and size dependen demand using hose lo s
we p opose a ailo ed exac column gene a ion app oach assis ed by as
algo i hms o in insic subp oblems, which u ns ou o be e y e icien
on ou eal-wo ld ins ances. Keywo ds: p-median, acili y loca ion, lo -
ype design, eal wo ld da a, column gene a ion Ma hema ics subjec s
classi ica ion: 90C06; 90C90; 90B99
1 In oduc ion
Due o small p o i ma gins o mos ashion discoun e s, applying OR me hods
is manda o y o hem. In o de o educe he handling cos s and he e o
p oneness in he cen al wa ehouse, ou business pa ne o de s all p oduc s in
mul iples o so-called lo - ypes om he supplie s and dis ibu es hem wi hou
any eplenishing o i s b anches. A lo - ype speci ies a numbe o pieces o a
p oduc o each a ailable size, e.g., lo - ype (1,2,2,1) means wo pieces o size
M and L, one piece o size S and XL, i he sizes a e (S,M,L,XL).
We wan o sol e he ollowing app oxima ion p oblem: which (in eg al)
mul iples o which (in eg al) lo - ypes should be supplied o a se o b anches
in o de o mee a ( ac ional) expec ed demand as closely as possible? We call
his speci ic demand app oxima ion p oblem he lo - ype design p oblem (LDP)
in [6]. In ha pape , also a basic model o he LDP was in oduced, accom-
panied by an in ege linea p og amming o mula ion and a ailo ed heu is ic,
which u ned ou o pe o m e y well o he eal-wo ld da a o ou pa ne .
Fo many p ac ical ins ances he se o applicable lo - ypes and hus he
numbe o a iables is so la ge ha he ILP o mula ion om [6] canno be sol ed
di ec ly.1In his pape , we he e o e p opose a column gene a ion app oach.
Fo ou p oblem adding a new a iable o column equi es he in oduc ion
1E.g. o 12 di e en sizes, which is easonable o linge ie o child en’s clo hing, he e a e
1 159 533 584 di e en lo - ypes, i we assume ha he e should be a mos 5 i ems o each
size and ha he o al numbe o i ems in a lo - ype should be be ween 12 and 30.
1
o addi ional cons ain s in mos cases. So we ha e o gene a e columns and
cu s simul aneously. Simila p oblems and app oaches ha e been add essed
in [5, 10]. In o de o o e come he in eg ali y gap o he ILP elaxa ion we
p opose a ailo ed b anching scheme complemen ed by he use o addi ional
co e cu s. This esul s in an exac column gene a ion app oach o he LDP,
which is enhanced by p ope ly chosen algo i hms o impo an subp oblems.
We apply his algo i hm o a s ochas ic e sion SLDP o he LDP, whe e he
expec a ion o e mo e han one demand-scena io is op imized. The SLDP is
o he same o m as he LDP, and hus all op imiza ion echniques iable o
he LDP immedia ely apply o he SLDP. Since using he SLDP ins ead o he
LDP can make decisions mo e obus agains o ecas ing e o s, we based ou
in es iga ions in his pape on he SLDP.
B anch-and-p ice algo i hms a e common o la ge-scale in ege p og am-
ming p oblems [8]. Uni ying gene al ema ks can be ound in [2, 11]. B anch-
p ice-and-cu algo i hms a e su eyed in [9]. The LDP is ela ed o he p-median
and he acili y loca ion p oblem: o ecen compu a ional esul s on la ge in-
s ances o he p-median p oblem we e e he eade o [1, 4, 7].
A o mal p oblem s a emen is gi en in Sec ion 2, ollowed by an ILP model
in Sec ion 3. Ou algo i hm is p esen ed in Sec ion 4. We show compu a ional
esul s on eal-wo ld da a in Sec ion 5, be o e we conclude wi h Sec ion 6.
2 Fo mal p oblem s a emen
We conside he dis ibu ion o supply o a single p oduc and s a wi h he
o mal p oblem s a emen in he de e minis ic con ex .
Da a. Le Bbe he se o b anches, Sbe he se o sizes, and M ⊂ Nbe an
in e al o possible mul iples. A lo - ype is a ec o (ls)s∈S ∈N|S|,lis applicable
i minc≤ls≤maxc o all s∈ S and min ≤Ps∈S ls≤max .2
By Lwe abb e ia e he se o applicable lo - ypes. The e is an uppe bound
Iand a lowe bound Igi en on he o al supply o e all b anches and sizes.
Mo eo e , he e is an uppe bound k∈Non he numbe o lo - ypes used. By
db,s ∈Q≥0we deno e he expec ed demand a b anch bin size s.
Decisions. Conside an assignmen o a unique lo - ype l(b)∈ L and an
assignmen o a unique mul iplici y m(b)∈ M o each b anch b∈ B. These
da a speci y ha m(b) lo s o lo - ype l(b) a e o be deli e ed o b anch b.
Objec i e. The goal is o ind a subse L⊆ L o a mos klo - ypes and
assignmen s l(b)∈ L and m(b)∈ M such ha he o al supply is wi hin he
bounds I,I, and he de ia ion be ween in en o y and demand is minimized.
2A pa ame e izable se o applicable lo - ypes is a p ac ically ele an case: By se ing
minc= 1 we can en o ce ha each b anch is supplied in each size wi h a leas one i em, a
equi emen which legally a ises o ad e ised p oduc s. Since he main ad an age o using
lo - ypes lies in he educ ion o he numbe o picks in he cen al wa ehouse, we should
gua an ee, ha his e ec does no dwindle away by selec ing lo - ypes wi h oo ew i ems,
which can be con olled by a sui able alue o min . The e a e p ac ical easons o he
pa ame e max , oo: combining oo many win e coa s in a lo would cause se ious handling
p oblems.
2
We call his op imiza ion p oblem he Lo -Type Design P oblem (LDP), see
[6] o mo e de ails. Using he in oduced decision a iables we can exp ess
he ele an decision-dependen en i ies as ollows. The in en o y o b anch b
in size sgi en assignmen s l(b) and m(b) is gi en by Ib,s(l, m) = m(b)l(b)s.
Mo eo e , he o al supply esul ing om l(b) and m(b) is gi en by I(l, m) =
Pb∈B Ps∈S Ib,s(l, m).
This de e minis ic model can sligh ly be enhanced o a s ochas ic model
by conside ing a se Ao scena ios ( o he success o he p oduc ). Fo each
scena io a∈ A we deno e by pai s p obabili y and wi h da
b,s ∈Q≥0 he demand
a B anch bin Size sin Scena io a o all b∈ B and s∈ S. The goal hen is o
minimize he expec ed o al de ia ion be ween in en o y and demand.
We call his single-s age s ochas ic op imiza ion p oblem he S ochas ic Lo -
Type Design P oblem (SLDP). The SLDP is equi alen o an o dina y LDP wi h
a modi ied objec i e unc ion, since he expec ed o al de ia ion ∆(l, m) can be
w i en as Pb∈B Ps∈S Pa∈A paδa
b,s(l, m), whe e δa
b,s(l, m) := |da
b,s −Ia
b,s(l, m)|.
In o he wo ds, he ce ain y equi alence p inciple (see e.g. [3, p. 28]) holds i
he inpu da a a e he expec ed de ia ions o all b anches and sizes. Ce ain y
equi alence does no hold i he inpu da a a e he expec ed demands, hough.
3 Modelling
We use bina y assignmen a iables xb,l,m indica ing whe he l(b) = land
m(b) = mand bina y selec ion a iables ylindica ing whe he l∈Lin o de
o model he SLDP as he ollowing in ege linea p og am. As an abb e ia ion
we u ilize |l|:= P
s∈S
ls.
min X
b∈B X
l∈L X
m∈M
cb,l,m ·xb,l,m (1)
s. . X
l∈L X
m∈M
xb,l,m = 1 ∀b∈ B (2)
X
l∈L
yl≤k(3)
X
m∈M
xb,l,m ≤yl∀b∈ B, l ∈ L (4)
I≤X
b∈B X
l∈L X
m∈M
m· |l| · xb,l,m ≤I(5)
xb,l,m ∈ {0,1} ∀b∈ B, l ∈ L, m ∈ M (6)
yl∈ {0,1} ∀l∈ L,(7)
whe e cb,l,m =P
a∈A
pa·P
s∈Sda
b,s −m·ls≥0.
3
4 A cus om-made b anch-and-p ice algo i hm
Since he se o applicable lo - ypes and, hus, he se o bina y a iables in
he s a ed ILP o mula ion may become qui e la ge, a na u al app oach is o
conside applicable lo - ypes dynamically in a b anch-and-p ice algo i hm.
In his sec ion we show how special s uc u e can be used o ob ain a as
b anch-and-p ice algo i hm o p ac ically ele an ins ances: We ypically ha e
300 ≤ |B| ≤ 1600 and 3 ≤ |M| ≤ 7 while |L| can be a ound 109, see he example
s a ed in he in oduc ion.
The idea o ou specialized exac b anch-and-p ice algo i hm is based on he
ollowing p ac ical obse a ions on eal-wo ld da a:
•The in eg ali y gap o ou SLDP model is small.
•Solu ions gene a ed by heu is ics pe o m e y well (see [6]).
•The e seems o be a “small” se o good and a “la ge” se o bad solu ions.
•No ma hema ical s uc u e o he se o good solu ions is known a-p io i.
•A p oo o op imali y is wan ed.
This led us o he ollowing b anch-and-p ice algo i hm:
(1) Use he heu is ics om [6] o de e mine a s a ing solu ion (x?, y?).
(2) Ini ialize he es ic ed mas e p oblem RMP (see below), as ollows: Fo
each b anch bwe compu e he h ee (locally) bes i ing lo - ypes and
add hem o ζb. Addi ionally we add all lo - ypes used in (x?, y?). We
se L0=∪b∈B ζ(b). Fo each b anch b∈ B and each lo - ype l∈ζ(b)
we compu e he co esponding op imal mul iplici y ˆmand se η(b, l) =
{ˆm−1,ˆm, ˆm+ 1}∩M.
(3) Le (x0, y0) be an op imal solu ion o RMP. I he cos s a e smalle han
he cos s o (x?, y?), hen we se ¯
L={l∈ L0|y0
l≥ε}, whe e εis a small
cons an , e.g., ε= 0.15, and b anch on ¯
L, i.e., we pe o m s ep (5).
(4) We sol e he p icing p oblem and possibly add lo - ypes om L0 o a ζb,
enla ge a η(b, l), o add a new lo - ype o L0, i.e., we gene a e new columns
and ows, go on wi h s ep (3), o s op o he wise.
(5) Sol e he lo - ype design p oblem es ic ed o he se ¯
Lo applicable lo -
ypes and possibly upda e he bes solu ion (x?, y?). Add he co e -cu
Pl∈Ciyl≤k−1 wi h Ci=¯
L o RPM and go o s ep (3).
S ep (1) – he s a ing heu is ics – is ske ched and Subsec ion 4.7 and used in
s ep (2) o ini ialize he se o columns and cons ain s o he RMP, see Subsec-
ion 4.6. The b anching scheme o s ep (3) and (5) is desc ibed in Subsec ion 4.4.
The p icing algo i hm, i.e. s ep (4) can be ound in Subsec ion 4.5.
4
In o de o ob ain as implemen a ions o he men ioned i e s eps we ha e
iden i ied some common subp oblems which can be sol ed by pu ely combi-
na o ial algo i hms. Those wo kho se me hods o de e mining locally bes
i ing lo - ypes, de e mining op imal mul iplie s and sol ing he es ic ion o
he SLDP o kapplicable lo - ypes a e s a ed in subsec ions 4.1, 4.2, and 4.3,
espec i ely.
Be o e we s a wi h he de ails le us i s commen on he adap ed b anch-
ing scheme in s eps (3) and (5). We gene a e wo b anches: One b anch con-
aining he comple ely enume a ed decision op ions ( his b anch can be sol ed
o op imali y immedia ely, e.g., by comple e enume a ion), one b anch wi h he
emaining decision op ions only ( his b anch ecei es a single co e cu excluding
he decision op ions conside ed in he o he b anch).
Al hough his kind o b anching seems wei d a i s glance – spli ing o
a mos a usually cons an numbe o easible solu ions asymp o ically yields a
linea dep h o he ull ee –, he e is a a ionale behind his: Whene e we can
ind all he ew good solu ions by sol ing p omising subp oblems, we can p une
he emaining sub ee as soon as all subp oblems con aining a good solu ion
ha e been gene a ed. Because o he small in eg ali y gap, his can be de ec ed
by he LP elaxa ion alue. And a p icing algo i hm can p o e LP op imali y
e en i no all a iables ha e been gene a ed.
Ou b anch-and-p ice algo i hm mus gene a e a p omising subp oblem in
such a way ha excluding ha subp oblem can be done e icien ly in he e-
s ic ed mas e p oblem.
The mas e p oblem (MP) o a b anch-and-p ice node is de ined o consis
o he s a ic SLDP model plus some co e -cu s (14) (see Subsec ion 4.4) o he
node, which exclude he decision op ions o subp oblems. (MP) can be es ic ed
o a manageable sized es ic ed mas e p oblem (RMP) by he ollowing: We
only conside a (small) subse L0⊆ L o he lo - ypes. Fo each b anch b∈ B
we conside a subse ζL0(b) = ζ(b)⊆ L0o hese lo - ypes and o each l∈ζL0(b)
we conside only a subse ηM(b, l) = η(b, l)⊆ M o he mul iplici ies.
The es ic ed mas e p oblem (RMP) hen eads as ollows:
min X
b∈B X
l∈ζ(b)X
m∈η(b,l)
cb,l,m ·xb,l,m (8)
s. . X
l∈ζ(b)X
m∈η(b,l)
xb,l,m = 1 ∀b∈ B (9)
X
l∈L0
−yl≥ −k(10)
X
b∈B X
l∈ζ(b)X
m∈η(b,l)
m· |l| · xb,l,m ≥I(11)
X
b∈B X
l∈ζ(b)X
m∈η(b,l)
−m· |l| · xb,l,m ≥ −I(12)
X
m∈η(b,l)
−xb,l,m +yl≥0∀b∈ B, l ∈ζ(b) (13)
5

X
l∈Ci
−yl≥ −γi∀i∈ I (14)
xb,l,m ≥0∀b∈ B, l ∈ζ(b), m ∈η(b, l) (15)
yl≥0∀l∈ L0.(16)
The dual es ic ed mas e p oblem (DRMP) is hen gi en by:
max X
b∈B
αb−kπ +Iu −I −X
i∈I
γiµi(17)
s. . αb−βb,l +m|l|u−m|l| ≤cb,l,m ∀b∈ B, l ∈ζ(b), m ∈η(b, l)
(18)
−π+X
b∈B :l∈ζ(b)
βb,l −X
i∈I :l∈Ci
µi≤0∀l∈ L0(19)
αb∈R∀b∈ B (20)
π, u, ≥0 (21)
βb,l ≥0∀b∈ B, l ∈ζ(b) (22)
µi≥0∀i∈ I.(23)
The p icing p oblem is de ined by inding hose cons ain s in he dual (DMP)
o he un es ic ed mas e p oblem (MP) ha a e mos iola ed by he cu en
solu ion o (DRMP).
4.1 Wo kho se 1: Finding bes i ing lo - ypes o single
b anches
The ollowing op imiza ion p oblem is ex ensi ely used in he p icing s ep, see
Lemma 1, and in p imal heu is ics in Sec ions 4.6 and 4.7 (se ing Ω = 0,
L0=∅).
Fo a gi en b anch bwe show how o sol e he op imiza ion p oblem
min
l∈L L0,m∈M cb,l,m −Ω·m· |l|,(24)
whe e Ω = u− ∈Ris gi en.
So le us assume ha he cos coe icien s cb,l,m a e gi en by he exp ession in
Sec ion 2, he se o lo - ypes Lis pa ame e ized using he in ege s minc, min ,
maxc, max ,L0is gi en by an explici lis , and M=m, m o wo in ege s m,
m. In a p ep ocessing s ep we compu e o each b anch b∈ B, each size s∈ S,
and each mul iplici y m∈ M he alues γ(b, s, m, ls) = Pa∈A pa·da
b,s −m·ls,
whe e minc≤ls≤maxc, and ψ(b, s, m) = minγ(b, s, m, ls) : minc≤ls≤
maxc.
Le Λ be he alue cb,ˆ
l, ˜m−Ω·˜m·|ˆ
l|o ou cu en champion, whe e we ini ialize
Λ = +∞. Nex we ix he possible mul iplici ies m≤m≤mand in each case
s a a b anch&bound ee. To desc ibe he nodes o he b anch&bound ee we
use a se F ⊆ S, whe e we se F=∅ o he oo node. In each ixing s ep we
6
choose a size s∈ S F and ix minc≤ls≤maxc, i.e., he numbe o i ems in size
so he eme ging lo - ype. I we ei he ha e Ps∈F ls+Ps∈S F minc>max o
Ps∈F ls+Ps∈S F maxc<min , we can p une he sea ch ee, since he ixed
alues lscan no be con inued o an admissible lo - ype.
Now le us es ima e he minimal possible cos o he pa ially ixed lo -
ype co esponding o F. The maximum numbe o i ems ha can occu in
he emaining sizes in S F is gi en by = min|S F| · maxc,max −Ps∈F ls.
Simila ly he minimum numbe o i ems o he emaining sizes is gi en by =
max|S F|·minc,min −Ps∈F ls. I Ω >0 hen we se = , o he wise we se
= . Wi h his, e e y ex ension o he pa ially ixed lo - ype co esponding
o F esul s in cos s o a leas
X
s∈F
γ(b, s, m, ls) + X
s∈S F
ψ(b, s, m)−Ω·m·X
s∈F
ls−Ω·m· .
I hese cos s a e a leas as la ge as he cos s Λ o ou cu en champion, we
can p une he sea ch ee.
In he lea s, whe e he lo - ype lis comple ely speci ied, we check whe he
l∈ L0. I his is no he case we ha e ound a new champion.
4.2 Wo kho se 2: Op imal mul iplici ies
A a he easy bu ele an subp oblem o he SLDP is he de e mina ion o
an op imal mul iplici y ˆm, i.e., o a gi en b anch band lo - ype lwe ask o
ˆm∈ M sa is ying cb,l, ˆm≤cb,l,m o all m∈ M. The mos simple way would
be o check all |M| possibili ies o mand pick he bes one.
As he de ia ions cb,l,m a e con ex in mand Mconsis s o an in e al o
non-nega i e in ege s, we can de e mine ˆmin a mos O(log |M|) e alua ions
using bina y sea ch.
4.3 Wo kho se 3: Sol ing he SLDP-k
In his subsec ion we p esen an e icien algo i hm o he SLDP-k, which is
he SLDP wi h only kapplicable lo - ypes. In o he wo ds we assume ha
he yio he ILP o mula ion om Sec ion 2 a e al eady ixed and i emains o
de e mine he op imal xb,l,m. I we d op Inequali y (5) on he o e all supply he
esul ing op imiza ion p oblem becomes easy. Since he numbe ko lo - ypes
is a small numbe we may check hem all o each b anch b∈ B and de e mine
he co esponding op imal mul iplici y using he me hods om Subsec ion 4.2.
This way, we can easily de e mine a bes i ing lo - ype l(b) and an op imal
mul iplici y m(b) o each b anch sepa a ely.
I acciden ally Inequali y (5) is alid, hen we ha e an op imum solu ion
o he SLDP-k. O o he wise we ha e de i ed a lowe bound o i s op imum
objec i e alue. In he la e case we conside he SLDP-kand elax he in-
eg ali y condi ion o 0 ≤xb,l,m ≤1. Due o he con exi y o he objec i e
unc ion (1) his p oblem can be e icien ly sol ed by g eedily adjus ing he
mul iplici ies m(b) and he assignmen s l(b) in o de o ul ill Inequali y (5).
7
Fo b e i y we discuss only he case whe e he o e all supply is s ic ly la ge
han I. He e we ha e o i e a i ely ake away i ems om some b anches. To
his end we in oduce ela i e cos s o each b anch band each al e na i e. I
m(b)−1 is also an elemen o M hen we can simply educe m(b) by one,
which esul s in ela i e cos s o cb,l(b),m(b)−1−cb,l(b),m(b)
|l(b)|≥0 pe i em. Ano he
possibili y is o change he used lo - ype l(b). The e o e we deno e by ϕb(l0) he
la ges in ege such ha ϕb(l0)· |l0|< m(b)· |l(b)|, i.e., ϕb(l0) is he mul iplici y
m o b anch band lo - ype l esul ing in a minimal coe icien cb,l0,m while
educing he numbe o supplied i ems o b anch b. I and only i ϕb(l0)∈ L we
can modi y he pai (l(b), m(b)) o (l0, ϕb(l0)) esul ing in ela i e cos s o
cb,l,ϕb(l0)−cb,l(b),m(b)
m(b)· |l(b)| − ϕb(l0)· |l0|≥0
pe i em. So, a e a mos O(1 + (k−1) log M) e alua ions o coe icien s
cb,l,m we can de e mine he al e na i e wi h minimum ela i e cos s ∆−
b o
each b anch b, whe e we se ∆−
b=∞i he e is no easible al e na i e.
I we ha e he ela i e cos s ∆−
b o all b∈ B and he co esponding ac ions
a hand, we can pick a ˆ
b∈ B which minimizes ∆−
b. Le δ > 0 deno e he numbe
o i ems which a e emo ed by he co esponding ac ion and Ideno e he o e all
supply co esponding o he cu en pai o unc ions l, b. Due o he con exi y
o he objec i e unc ion (1) we can s a e he ollowing:
(a) I ∆−
ˆ
b=∞, hen he SLDP-ksubp oblem is in easible.
(b) I I−δ≥I, hen, a e pe o ming he g eedily op imal ac ion, he new
assignmen s ˜
l(b) and ˜m(b) co espond o an op imal solu ion o SLDP-k,
whe e Inequali y (5) is eplaced by P
b∈B P
l∈L P
m∈M
m· |l| · xb,l,m ≤I−δ.
(c) I I−δ < I we ob ain he op imal solu ion o he SLDP-kwi h ac ional
a iables xb,l,m by u ilizing a sui able linea combina ion o he old assign-
men (l(b), m(b)) and he cheapes dec easing al e na i e (˜
l(b),˜m(b)).
Thus, a e a ini e numbe o i e a ions, depending a mos linea ly on he di -
e ence be ween he ini ial o e all supply and I, we ob ain he op imal solu ion
o he SLDP-kwi h a mos wo ac ional a iables xb,l,m. To also sol e he
in eg al SLDP-kwe u ilize a b anch-bound app oach.
In o de o ob ain an e icien algo i hm we main ain he ∆−
b- alues in a
heap da a s uc u e, so ha in each ecu sion s ep we only ha e o de e mine
one new ∆−
b- alue, while he upda e o he heap can be done in O(log |B|).
4.4 B anching in o he mos p omising subp oblem and
he es
A a node o Dep h io he b anch-and-p ice ee we spli he cu en node in o
wo: one b anch con ains he mos p omising subp oblem, he o he b anch
con ains he emaining decision op ions.
8
Le us now s a e how o de e mine he mos p omising subp oblem: Gi en an
op imal solu ion o he cu en (RMP), we conside he alues o he a ained y-
a iables. To simpli y he no a ion we assume ha hey a e o de ed downwa ds,
i.e., y1≥y2≥ · · · ≥ y|L0|. Fo a small cons an ε > 0, e.g., ε= 0.15, we conside
an index qsuch ha yq≥εand yq+1 < ε. We call he subp oblem o he SLDP
wi h a gi en C:= {1, . . . , q}⊆Las i s se o applicable lo - ypes he mos
p omising subp oblem SLDP|Co SLDP.
The node co esponding SLDP|Ciis hen sol ed exac ly. I Ci
k≤100 000
hen we comple ely enume a e all k-subse s o lo - ypes in Ciand subsequen ly
sol e he co esponding SLDP-k(see Subsec ion 4.3). O he wise we sol e he
co esponding ILP o mula ion om Sec ion 3 di ec ly. The o he node has
o be wo ked on u he by b anch-and-p ice: Excluding he mos p omis-
ing subp oblem in his b anch can be achie ed by adding a single co e cu
Pl∈Ciyl≤γi:= k−1.
4.5 The combina o ial p icing algo i hm
We associa e wi h he cons ain s o he mas e p oblem (MP) he dual a iables
αb,π,u, ,βb,l, and µi. Wi h his, o each lo - ype l he educed cos s o a
a iable xb,l,m a e gi en by
cb,l,m −αb−m· |l| · (u− ) + βb,l,(25)
and o a a iable yl he educed cos s a e gi en by
0 + π−X
b∈B
βb,l +X
i∈I:l∈Ci
µi.(26)
Lemma 1 I Si∈I Ci⊆ L0,
min
b∈B,l∈ζ(b),m∈M cb,l,m −αb−m· |l| · (u− ) + βb,l ≥0,(27)
min
b∈B,l∈L0 ζ(b),m∈M cb,l,m −αb−m· |l| · (u− )≥0,and (28)
max
L L0X
b∈B
max0,max
m∈M αb+m· |l| · (u− )−cb,l,m≤π(29)
hen he cu en op imal solu ion o (RMP) is op imal o (MP).
P oo 1 I Inequali y (27) is alid, hen he e is no a iable xb,l,m wi h l∈
ζ(b)ha ing nega i e educed cos s. Fo a gi en b anch band a gi en lo - ype
l∈ L ζ(b)(DRMP) does no con ain he a iable βb,l since (RMP) does no
include he co esponding inequali y. We ex end he dual solu ion by se ing
βb,l =0 : l∈ L0 ζ(b),
max (0,maxm∈M αb+m· |l| · (u− )−cb,l,m) : l∈ L L0
(30)
9