An exact column-generation approach for the lot-type design problem

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