, pro cessi ng times] [pa ram: σ [i ,l ]∈ K , newsp ap er read by i in p osition l)] Releas e time : A 8:30 – B 8:45 – C 8:45 – D 9:30. [pa ram R

F our Italia n friends [fro m La Setti mana Enigmist ica ]

Andrea,Bruno,CarloandDarioshareanapartmentandreadfournewspapers:“La Repubblica”,“IlMessaggero”,“LaStampa”and“LaGazzettadelloSport”beforegoing out.Eachofthemwantstoreadallnewspapersinaspecificorder.Andreastartswith “LaRepubblica”foronehour,thenhereads“LaStampa”for30minutes,“Il Messaggero”fortwominutesandthen“LaGazzettadelloSport”for5minutes.Bruno preferstostartwith“LaStampa”for75minutes;hethenhasalookat“IlMessaggero” forthreeminutes,thenhereads“LaRepubblica”for25minutesandfinally“La GazzettadelloSport”for10minutes.Carlostartswith“IlMessaggero”for5minutes, thenhereads“LaStampa”for15minutes,“LaRepubblica”for10minutesand“La GazzettadelloSport”for30minutes.Finally,Dariostartswith“LaGazzettadello Sport”for90minutesandthenhededicatesjustoneminutetoeachof“La Repubblica”,“LaStampa”and“IlMessaggero”inthisorder.Thepreferredorderisso importantthateachiswillingtowaitandreadnothinguntilthenewspaperthathe wantsbecomesavailable.Moreover,noneofthemwouldstopreadinganewspaperand resumelater.BytakingintoaccountthatAndreagetsupat8:30,BrunoandCarloat 8:45andDarioat9:30,andthattheycanwash,getdressedandhavebreakfastwhile readingthenewspapers,whatistheearliesttimetheycanleavehometogether? DeGiovanni,DiSummaMeMoCO22/36

F our Italia n friends : a Job-S hop Schedul ing Probl em (JS P) Jobs : A ndr ea, B run o, C arlo, D ario [set I] Machi nes : “La R epub bli ca”, “Il M essagge ro”, “La S tamp a” and “La G azze tta dell o Sp ort” [set K ] Pro cess ing times and o rder : A: R (60) → S (30) → M (2) → G (5); B: S (75) → M (3) → R (25) → G (10); C: M (5) → S (15) → R (10) → G (30); A: G (90) → R (1) → S (1) → M (1); [pa ram: D

ik

, pro cessi ng times] [pa ram: σ [i ,l ]∈ K , newsp ap er read by i in p osition l)] Releas e time : A 8:30 – B 8:45 – C 8:45 – D 9:30. [pa ram R

i

] Object ive: Minim ize the Mak espan (job- comple tion time) No p re-empti on

DeGiovanni,DiSummaMeMoCO23/36

F our Italia n friends : a Job-S hop Schedul ing Probl em (JS P) Jobs : A ndr ea, B run o, C arlo, D ario [set I] Machi nes : “La R epub bli ca”, “Il M essagge ro”, “La S tamp a” and “La G azze tta dell o Sp ort” [set K ] Pro cess ing times and o rder : A: R (60) → S (30) → M (2) → G (5); B: S (75) → M (3) → R (25) → G (10); C: M (5) → S (15) → R (10) → G (30); A: G (90) → R (1) → S (1) → M (1); [pa ram: D

ik

, pro cessi ng times] [pa ram: σ [i ,l ]∈ K , newsp ap er read by i in p osition l)] Releas e time : A 8:30 – B 8:45 – C 8:45 – D 9:30. [pa ram R

i

] Object ive: Minim ize the Mak espan (job- comple tion time) No p re-empti on

DeGiovanni,DiSummaMeMoCO23/36

LP mo del fo r JSP h

ik

: sta rt time (in minu tes after 8:30) of i∈ I on k ∈ K ; y : comple tion time (in mi nutes after 8:30); x

ijk

: bina ry , 1 if i∈ I preced es j∈ I on k ∈ K , 0 otherwi se. min y s.t. y ≥ h

iσ[i,|K|]

+ D

iσ[i,|K|]

∀ i∈ I h

iσ[i,l]

≥ h

iσ[i,l−1]

+ D

iσ[i,l−1]

∀ i∈ I, l = 2... |K | h

iσ[i,1]

≥ R

i

∀ i∈ I h

ik

≥ h

jk

+ D

jk

− M x

ijk

∀ k ∈ K ,i ∈ I, j∈ I : i� = j h

jk

≥ h

ik

+ D

ik

− M (1 − x

ijk

) ∀ k ∈ K ,i ∈ I, j∈ I : i� = j y ∈ R

+

h

ik

∈ R

+

∀ k ∈ K ,i ∈ I x

ijk

∈ { 0, 1} ∀ k ∈ K ,i ∈ I, j∈ I : i� = j

DeGiovanni,DiSummaMeMoCO24/36

Proj ect schedulin g in the b oat ya rd indus try

Constructingaboatrequiresthecompletionofthefollowingoperations: OperationsDurationPrecedences A2none B4A C2A D5A E3B,C F3E G2E H7D,E,G I4F,G Someoftheoperationsarealternativetoeachother.Inparticular,onlyoneofBandC needstobeexecuted,andonlyoneofFandGneedstobeexecuted.Furthermore,if bothCandGareexecuted,thedurationofIincreasesby2days.Thetablealsoshows theprecedencesforeachoperation(i.e.,operationsthatmustbecompletedbeforethe beginningofthenewoperation).Forinstance,Hcanstartonlyafterthecompletionof E,DandG(ifGwillbeexecuted).Writealinearprogrammingmodelthatcanbeused todecidewhichoperationsshouldbeexecutedinordertominimizethetotaldurationof theconstructionoftheboat. DeGiovanni,DiSummaMeMoCO25/36

Proj ect schedulin g in the b oat ya rd indus try: hints

minz s.t.z≥ti∀i∈A...I tA≥dA tB≥tA+dB−M(1−yB) tC≥tA+dC−M(1−yC) tD≥tA+dD tE≥tB+dE tE≥tC+dE tF≥tE+dF−M(1−yF) tG≥tA+dG−M(1−yG)

tH≥tD+dH tH≥tE+dH tH≥tG+dH tI≥tF+dI+2yCG tI≥tG+dI+2yCG yB+yC=1 yF+yG=1 yC+yG<=1+yCG z,ti≥0∀i∈{A...I} y.∈{0,1}

where ticompletiontimeofoperationi∈{A,B,C,D,E,F,G,H,I}; yi1ifoperationi∈{B,C,F,G}isexecuted,0otherwise; yCG1ifbothCandGareexecuted,0otherwise; zcompletiontimeofthelastoperation; diparameterindicatingthedurationofoperationi; Msufficientlylargeconstant. Exercise:writeamoregeneralmodelforgenericsetsofoperationsandprecedence. DeGiovanni,DiSummaMeMoCO26/36

A (shift ) coveri ng problem The pha rmacy fede ration w ants to organi ze the op enin g shif ts on publ ic holi da ys all over the region. The numb er of shifts is alre ady deci ded, and the numb er of pha rmaci es op en on the same da y has to b e as bala nced as p ossibl e. F urtherm ore, every pha rmacy is pa rt of one shif t only . F or insta nce, if there are 12 pha rmaci es and the numb er of shif ts is 3, every shif t will consis t of 4 pha rmaci es. Pha rmaci es and users are thought as concen trated in centr oids (fo r insta nce, vill ages). F or every cen troid, the numb er of user s and pha rmac ies are kno wn. The dist ance b et w een every order ed pair of centroi ds is also kno wn. F or the sak e of simp lici ty , w e igno re congesti on probl ems and w e assume that every use r will go to the closest op en pha rmacy . The ta rget is to deter mine the sifts so that the total dista nce covered by the user s is mini mize d.

DeGiovanni,DiSummaMeMoCO27/36

A (shift ) coveri ng problem : mo del 1

yik:1ifpharmacyj∈Ptakespartinshiftk=1...K,0otherwise; zijk:1ifcentroidi∈Cusespharmacyj∈Pduringshiftk=1...K,0otherwise (notice:byoptimality,zselectsthenearestopenpharmacy) min

K� k=1

� i∈C

� j∈PDijzijk(parameterDij:distancefromitoj) s.t.

K� k=1yjk=1∀j∈P � j∈Pzijk=1∀i∈C,k=1...K xijk≤yjk∀i∈C,j∈P,k=1...K

�� �� |/|P.K..1=k∀K�P≤|/�|�Ky≤jk Pj∈ C.K..1=,kP∈,j∈i∈},10{,yz∀jkijk sesconstraintsbutsufferfromvariablandofdeler:themoNoticehasnumbpolynomiala edinmanydiays,erentwbyrepresentffeis,bsymmetriesthat,thesame“real”solutioncan ofs.shiftsametheto)knamesvalueenterffdiggivin(i.e. MeMoCO/28DeSummaDini,Giovan36

A (shift ) coveri ng problem : mo del 1

yik:1ifpharmacyj∈Ptakespartinshiftk=1...K,0otherwise; zijk:1ifcentroidi∈Cusespharmacyj∈Pduringshiftk=1...K,0otherwise (notice:byoptimality,zselectsthenearestopenpharmacy) min

K� k=1

� i∈C

� j∈PDijzijk(parameterDij:distancefromitoj) s.t.

K� k=1yjk=1∀j∈P � j∈Pzijk=1∀i∈C,k=1...K xijk≤yjk∀i∈C,j∈P,k=1...K

�� �� |/|P.K..1=k∀K�P≤|/�|�Ky≤jk Pj∈ C.K..1=,kP∈,j∈i∈},10{,yz∀jkijk butandconstraintsfromsuffersriablespvahasofthemodel:aolynomialnumberNotice diedinmanywfferentays,byrepresentcaneis,symmb,thatetriesthesame“real”solution s.shiftsametheto)ofknamesvalueenterffdiggivin(i.e. MeMoCO36/28ni,SummaDiGiovanDe

: 1 del mo ) problem ng coveri (shift A

in;rwise0,.K..1=kshiftothertphapay:if1rmacyj∈Ptakesik 1shiftk=rwise...K,0othePduringj∈cenrmacyz1if:troidi∈Cusesphaijk the)rmacyphaenoprestneabyctsselezy,malitoptitice:(no min

K� k=1

� i∈C

� j∈PDijzijk(parameterDij:distancefromitoj) s.t.

K� k=1yjk=1∀j∈P � j∈Pzijk=1∀i∈C,k=1...K xijk≤yjk∀i∈C,j∈P,k=1...K

�� �� |/|P.K..1=k∀K�P≤|/�|�Ky≤jk Pj∈ C.K..1=,kP∈,j∈i∈},10{,yz∀jkijk sesconstraintsbutsufferfromvariablandofdeler:themoNoticehasnumbpolynomiala edinmanydiays,erentwbyrepresentffeis,bsymmetriesthat,thesame“real”solutioncan ofs.shiftsametheto)knamesvalueenterffdiggivin(i.e. MeMoCO/28DeSummaDini,Giovan36

A (shift ) coveri ng problem : mo del 2

P:setofallpossiblesubsetsofP(withbalancedcardinalityforbalancingconstraint) D(J):totaldistancecoveredbyallusersinCtoreachthenearestpharmacyinJ∈P xJ:1ifthesetJ∈Pisselectedasashift,0otherwise; min� J∈PDJxJ s.t.� J∈PxJ=K � J∈P:j∈JxJ=1∀j∈P xJ∈{0,1}∀J∈P Notice:themodeldoesnotsufferfromsymmetries(ashiftisdirectlydeterminedbythe definingsubset),buthasanexponentialnumberofvariables[wewillseehowtofacethisissue]. DeGiovanni,DiSummaMeMoCO29/36

A (shift ) coveri ng problem : mo del 2

P:setofallpossiblesubsetsofP(withbalancedcardinalityforbalancingconstraint) D(J):totaldistancecoveredbyallusersinCtoreachthenearestpharmacyinJ∈P xJ:1ifthesetJ∈Pisselectedasashift,0otherwise; min� J∈PDJxJ s.t.� J∈PxJ=K � J∈P:j∈JxJ=1∀j∈P xJ∈{0,1}∀J∈P Notice:themodeldoesnotsufferfromsymmetries(ashiftisdirectlydeterminedbythe definingsubset),buthasanexponentialnumberofvariables[wewillseehowtofacethisissue]. DeGiovanni,DiSummaMeMoCO29/36

A (shift ) coveri ng problem : mo del 2

P:setofallpossiblesubsetsofP(withbalancedcardinalityforbalancingconstraint) D(J):totaldistancecoveredbyallusersinCtoreachthenearestpharmacyinJ∈P xJ:1ifthesetJ∈Pisselectedasashift,0otherwise; min� J∈PDJxJ s.t.� J∈PxJ=K � J∈P:j∈JxJ=1∀j∈P xJ∈{0,1}∀J∈P Notice:themodeldoesnotsufferfromsymmetries(ashiftisdirectlydeterminedbythe definingsubset),buthasanexponentialnumberofvariables[wewillseehowtofacethisissue]. DeGiovanni,DiSummaMeMoCO29/36

An energ y fl ow proble m A compan y distr ibuti ng electr ic ener gy has several p ow er pla nts and distr ibuti ng station s conne cted by wire s. Each station i can: pro duce p

i

kW of energy (p

i

= 0 if the station cannot pro duce energ y); distr ibute energy on a sub-n et w ork whose users have a total deman d of d

i

kW (d

i

= 0 if the station serves no users) ; ca rry energy from/to di ff erent station s. The wires connect ing station i to station j have a maxim um capac it y of u

ij

kW and a cost of c

ij

euros fo r each kW ca rri ed by the wires . The compa ny w ants to determ ine the mini mum cost distr ibuti on plan , under the assu mption that the total amount of ener gy pro duce d equa ls the total amount of energy requ ired by all sub- net w orks.

DeGiovanni,DiSummaMeMoCO30/36

Net w ork fl ows mo dels: single commo dit y

Parameters:uij,cijand G=(N,A),N=power/distributionstations,A=connectionsbetweenstations bv=dv−pv,v∈N[demand(bv>0)/supply(<0)/transshipment(=0)node] Variables: xijamountofenergytoflowonarc(i,j)∈A min� (i,j)∈Acijxij s.t.� (i,v)∈Axiv−� (v,j)∈Axvj=bv∀v∈N xij≤uij∀(i,j)∈A xij∈R+ MinimumCostNetworkFlowProblem DeGiovanni,DiSummaMeMoCO31/36

Net w ork fl ows mo dels: single commo dit y

Parameters:uij,cijand G=(N,A),N=power/distributionstations,A=connectionsbetweenstations bv=dv−pv,v∈N[demand(bv>0)/supply(<0)/transshipment(=0)node] Variables: xijamountofenergytoflowonarc(i,j)∈A min� (i,j)∈Acijxij s.t.� (i,v)∈Axiv−� (v,j)∈Axvj=bv∀v∈N xij≤uij∀(i,j)∈A xij∈R+ MinimumCostNetworkFlowProblem DeGiovanni,DiSummaMeMoCO31/36

Net w ork fl ows mo dels: single commo dit y

Parameters:uij,cijand G=(N,A),N=power/distributionstations,A=connectionsbetweenstations bv=dv−pv,v∈N[demand(bv>0)/supply(<0)/transshipment(=0)node] Variables: xijamountofenergytoflowonarc(i,j)∈A min� (i,j)∈Acijxij s.t.� (i,v)∈Axiv−� (v,j)∈Axvj=bv∀v∈N xij≤uij∀(i,j)∈A xij∈R+ MinimumCostNetworkFlowProblem DeGiovanni,DiSummaMeMoCO31/36

Net w ork fl ows mo dels: single commo dit y

Parameters:uij,cijand G=(N,A),N=power/distributionstations,A=connectionsbetweenstations bv=dv−pv,v∈N[demand(bv>0)/supply(<0)/transshipment(=0)node] Variables: xijamountofenergytoflowonarc(i,j)∈A min� (i,j)∈Acijxij s.t.� (i,v)∈Axiv−� (v,j)∈Axvj=bv∀v∈N xij≤uij∀(i,j)∈A xij∈R+ MinimumCostNetworkFlowProblem DeGiovanni,DiSummaMeMoCO31/36

An multi- typ e energy fl ow problem A compan y distr ibuti ng electr ic ener gy has several p ow er and distri buti ng station s connec ted by wires . Each station pro duces /distr ibute s di ff er ent kin ds of energy . Each station i can: pro duce p

^{k i}

kW of energy of typ e k (it ma y b e p

^{k i}

= 0); distr ibute energy of typ e k on a sub-n et w ork whose users have a total deman d of d

^{k i}

kW (it ma y b e d

^{k i}

= 0); ca rry energy from/to di ff erent station s. Note that every stati on can pro duce and/o r distri bute di ff er ent typ es of energy . The wires connect ing station i to station j have a maxim um capac it y of u

ij

kW, inde p enden tly of the typ e of energy ca rri ed. The transp ortation cost dep ends b oth on the pair of station s (i ,j ) and the typ e of energy k , and is equal to c

^{k ij}

euros fo r each kW. The compa ny w ants to determ ine the mini mum cost distr ibuti on plan , unde r the assump tion that, fo r each typ e of energy , the total amoun t pro duced equa ls the total amoun t of ener gy of the same typ e requ ired by all sub-n et w orks.

DeGiovanni,DiSummaMeMoCO32/36

Net w ork fl ows mo dels: multi- commo dit y

Parameters:uij,c^{k ij},K(setofenergytypesorcommodities)and G=(N,A),N=power/distributionstations,A=connectionsbetweenstations b^{k v}=d^{k v}−p^{k v},v∈N[demand(b^{k v}>0)/supply(<0)/transshipment(=0)node] Variables: x^{k ij}amountofenergyoftypektoflowonarc(i,j)∈A min� k∈K

� (i,j)∈Ac^{k ij}x^{k ij} s.t.� (i,v)∈Ax^{k iv}−� (v,j)∈Ax^{k vj}=b^{k v}∀v∈N,∀k∈K � k∈Kx^{k ij}≤uij∀(i,j)∈A x^{k ij}∈R+∀(i,j)∈A,∀k∈K MinimumCostNetworkMulti-commodityFlowProblem DeGiovanni,DiSummaMeMoCO33/36

Net w ork fl ows mo dels: multi- commo dit y

Parameters:uij,c^{k ij},K(setofenergytypesorcommodities)and G=(N,A),N=power/distributionstations,A=connectionsbetweenstations b^{k v}=d^{k v}−p^{k v},v∈N[demand(b^{k v}>0)/supply(<0)/transshipment(=0)node] Variables: x^{k ij}amountofenergyoftypektoflowonarc(i,j)∈A min� k∈K

� (i,j)∈Ac^{k ij}x^{k ij} s.t.� (i,v)∈Ax^{k iv}−� (v,j)∈Ax^{k vj}=b^{k v}∀v∈N,∀k∈K � k∈Kx^{k ij}≤uij∀(i,j)∈A x^{k ij}∈R+∀(i,j)∈A,∀k∈K MinimumCostNetworkMulti-commodityFlowProblem DeGiovanni,DiSummaMeMoCO33/36

Net w ork fl ows mo dels: multi- commo dit y

Parameters:uij,c^{k ij},K(setofenergytypesorcommodities)and G=(N,A),N=power/distributionstations,A=connectionsbetweenstations b^{k v}=d^{k v}−p^{k v},v∈N[demand(b^{k v}>0)/supply(<0)/transshipment(=0)node] Variables: x^{k ij}amountofenergyoftypektoflowonarc(i,j)∈A min� k∈K

� (i,j)∈Ac^{k ij}x^{k ij} s.t.� (i,v)∈Ax^{k iv}−� (v,j)∈Ax^{k vj}=b^{k v}∀v∈N,∀k∈K � k∈Kx^{k ij}≤uij∀(i,j)∈A x^{k ij}∈R+∀(i,j)∈A,∀k∈K MinimumCostNetworkMulti-commodityFlowProblem DeGiovanni,DiSummaMeMoCO33/36

Net w ork fl ows mo dels: multi- commo dit y

Parameters:uij,c^{k ij},K(setofenergytypesorcommodities)and G=(N,A),N=power/distributionstations,A=connectionsbetweenstations b^{k v}=d^{k v}−p^{k v},v∈N[demand(b^{k v}>0)/supply(<0)/transshipment(=0)node] Variables: x^{k ij}amountofenergyoftypektoflowonarc(i,j)∈A min� k∈K

� (i,j)∈Ac^{k ij}x^{k ij} s.t.� (i,v)∈Ax^{k iv}−� (v,j)∈Ax^{k vj}=b^{k v}∀v∈N,∀k∈K � k∈Kx^{k ij}≤uij∀(i,j)∈A x^{k ij}∈R+∀(i,j)∈A,∀k∈K MinimumCostNetworkMulti-commodityFlowProblem DeGiovanni,DiSummaMeMoCO33/36

Lab exerci se - P art I Problem descri ption A compan y pro duce s b oa rds with hole s used to bui ld elec tric frame s. Boa rds are p osition ed over a machi nes and a dri ll moves over the b oa rd, stops at the desir ed p osition s and mak es the holes . Once a b oa rd is dri lled , a new b oa rd is p osition ed and the pro cess is itera ted many times. Given the p osition of the holes on the b oa rd, the compan y asks us to deter mine the hole sequ ence that mini mize s the total dril ling time, taki ng into accoun t that the time neede d fo r maki ng an hole is the same and constan t fo r all the holes .

DeGiovanni,DiSummaMeMoCO34/36

Lab exerci se - P art I: graph mo del Can b e see n as a T ravel ing Sale sman Probl em (TSP )

�

graph G = (N ,A ): N = holes, A = trajec to ries from i to j, i, j∈ N

�

fi nd a mini mum w eight (c

ij

) hami ltonia n cycl e on G Can b e mo dele d as a net w ork fl ow probl em

�

b

0

= − |N |, (0 ∈ N is an arbitr ary no de)

�

b

i

= 1, ∀ i∈ N \ { 0}

�

the cost is rel ated to the use of an arc (fi xed cost)

�

at most one incomi ng and one outgoin g arc, fo r each no de Decisi on va riab les:

xij

amoun t of the fl ow shipp ed from i to j, ∀ (i ,j ) ∈ A ;

yij

1 if arc (i ,j ) ship s some fl ow, 0 otherwi se, ∀ (i ,j ) ∈ A .

DeGiovanni,DiSummaMeMoCO35/36

Lab exerci se - P art I: ILP mo del

min� i,j:(i,j)∈Acijyij s.t.� j:(0,j)∈Ax0j=|N| � i:(i,k)∈Axik−� j:(k,j)∈Axkj=1∀k∈N\{0} � j:(i,j)∈Ayij=1∀i∈N � i:(i,j)∈Ayij=1∀j∈N xij≤|N|yij∀(i,j)∈A xij∈Z+∀(i,j)∈A yij∈{0,1}∀(i,j)∈A DeGiovanni,DiSummaMeMoCO36/36