# Model Cross-Facility Management of Production and Transportation Plannning Problem - (PTPP) # Eksioglu, S, D.; Romeijn, H. E.; Pardalos, P. M., (2006), Computers and Operations Research, 33, 3231-3251 # Implementation: João Flávio de Freitas Almeida # Otimização de Grande Porte - Doutorado - PPGEP - UFMG # (Usando formulacao primal do subproblema) # ======================================================= # Parametros do Problema # ======================================================= # Initial Data param F; # Facilities param R; # Retailers param T; # Time Period # Problem Data param P{i in 1..F, t in 1..T}; # Production unit cost at facility i in period t param S{i in 1..F, t in 1..T}; # Fixed setup cost if there is production at facility i in period t param H{i in 1..F, t in 1..T}; # Inventory unit cost at facility i in period t param CTE; param B{j in 1..R, t in 1..T}; # Demand at retailer j in period t param TC{i in 1..F, j in 1..R, t in 1..T: B[j,t]>0} := CTE; # Transportation cost function from facility i to retailer j in period t param C{i in 1..F, j in 1..R, t in 1..T} := TC[i,j,t]/B[j,t]; # Transportation unit cost from facility i to retailer j in period t # Decision Variables var q{i in 1..F, t in 1..T}, >= 0; # Amount produced at facility i in period t var x{i in 1..F, j in 1..R, t in 1..T}, >= 0; # Amount transported from facility i to retailer j in period t var I{i in 1..F, t in 1..T}, >= 0; # Amount in inventory at facility i in the end of period t var y{i in 1..F, t in 1..T}, >= 0, binary; # Setup variable: {1 if q[i,t] > 0, 0 otherwise} var eta, >= 0; # ======================================================= # Parametros do método de Decomposição # ======================================================= param Tempo; param ncortes default 0, integer; # Numero de cortes de Benders param TipoCorte{1..ncortes} symbolic within {"point","ray"}; # Tipo de corte de Benders param Pare default 0; param supremum default 0; param lb default 0; # Lower Bount - Solução primal atual param ub default Infinity; # Upper Bount - Solução dual param it default 0; # Iteração # ======================================================= # Problema original # ======================================================= minimize PFO: sum{i in 1..F, t in 1..T}(P[i,t]*q[i,t] + S[i,t]*y[i,t] + H[i,t]*I[i,t] + sum{j in 1..R}C[i,j,t]*x[i,j,t]); # Restrições s.t. R1{i in 1..F, t in 1..T: t = 1}: q[i,t] = sum{j in 1..R}x[i,j,t] + I[i,t]; s.t. R2{i in 1..F, t in 1..T: t > 1}: q[i,t] + I[i,t-1] = sum{j in 1..R}x[i,j,t] + I[i,t]; s.t. R3{j in 1..R, t in 1..T}: sum{i in 1..F}x[i,j,t] = B[j,t]; s.t. R4{i in 1..F, t in 1..T}: q[i,t] <= sum{j in 1..R, tt in t..T}B[j,tt] * y[i,t] ; s.t. R5: sum{i in 1..F, t in 1..T} y[i,t] >= 1; # Desigualdades validas s.t. R6: sum{i in 1..F,j in 1..R, t in 1..T} y[i,t]*B[j,t] = sum{i in 1..F, t in 1..T} q[i,t] - sum{i in 1..F, t in 1..T}I[i,t]; # Desigualdades validas # ======================================================= # Subproblema primal # ======================================================= param _y{i in 1..F, t in 1..T}; param _I{i in 1..F, t in 1..T}; minimize SPFO: sum{i in 1..F, t in 1..T}(P[i,t]*q[i,t] + sum{j in 1..R}C[i,j,t]*x[i,j,t]); # Restrições s.t. SPR1{i in 1..F, t in 1..T: t = 1}: q[i,t] - sum{j in 1..R}x[i,j,t] = _I[i,t]; s.t. SPR2{i in 1..F, t in 1..T: t > 1}: q[i,t] - sum{j in 1..R}x[i,j,t] = _I[i,t] - _I[i,t-1]; s.t. SPR3{j in 1..R, t in 1..T}: sum{i in 1..F}x[i,j,t] = B[j,t]; s.t. SPR4{i in 1..F, t in 1..T}: q[i,t] <= sum{j in 1..R, tt in t..T}B[j,tt] * _y[i,t] ; s.t. SPR5: 1 <= sum{i in 1..F, t in 1..T} _y[i,t]; # Desigualdades validas s.t. SPR6: sum{i in 1..F, t in 1..T} q[i,t] = sum{i in 1..F,j in 1..R, t in 1..T} _y[i,t]*B[j,t] - sum{i in 1..F, t in 1..T}_I[i,t]; # Desigualdades validas # ======================================================= # Problema mestre # ======================================================= param _u{i in 1..F, t in 1..T, h in 1..ncortes}; param _v{j in 1..R, t in 1..T, h in 1..ncortes}; param _w{i in 1..F, t in 1..T, h in 1..ncortes} <= 0.00000001; param _alpha{h in 1..ncortes}; param _beta{h in 1..ncortes}; minimize PMFO: sum{i in 1..F, t in 1..T} ( S[i,t]*y[i,t] + H[i,t]*I[i,t] ) + eta; s.t. corte_I{h in 1..ncortes}: if TipoCorte[h] = "point" then eta >= sum{j in 1..R, t in 1..T} B[j,t] * _v[j,t,h] + sum{i in 1..F, t in 1..T}( sum{j in 1..R, tt in t..T}B[j,tt] * y[i,t] ) * _w[i,t,h] + sum{i in 1..F, t in 1..T: t = 1} I[i,t] * _u[i,t,h] + sum{i in 1..F, t in 1..T: t > 1} ( I[i,t] - I[i,t-1] ) * _u[i,t,h]; s.t. corte_II{h in 1..ncortes}: if TipoCorte[h] = "ray" then sum{j in 1..R, t in 1..T} B[j,t] * _v[j,t,h] + sum{i in 1..F, t in 1..T}( sum{j in 1..R, tt in t..T}B[j,tt] * y[i,t] ) * _w[i,t,h] + sum{i in 1..F, t in 1..T: t = 1} I[i,t] * _u[i,t,h] + sum{i in 1..F, t in 1..T: t > 1} ( I[i,t] - I[i,t-1] ) * _u[i,t,h] <= 0; /* # Decomposição em Blocos: StairCase s.t. corte_I{h in 1..ncortes, t in 1..T}: if TipoCorte[h] = "point" then eta >= sum{j in 1..R} B[j,t] * _v[j,t,h] + sum{i in 1..F}( sum{j in 1..R, tt in t..T}B[j,tt] * y[i,t] ) * _w[i,t,h] + sum{i in 1..F: t = 1} I[i,t] * _u[i,t,h] + sum{i in 1..F: t > 1} ( I[i,t] - I[i,t-1] ) * _u[i,t,h]; s.t. corte_II{h in 1..ncortes, t in 1..T}: if TipoCorte[h] = "ray" then sum{j in 1..R} B[j,t] * _v[j,t,h] + sum{i in 1..F}( sum{j in 1..R, tt in t..T}B[j,tt] * y[i,t] ) * _w[i,t,h] + sum{i in 1..F: t = 1} I[i,t] * _u[i,t,h] + sum{i in 1..F: t > 1} ( I[i,t] - I[i,t-1] ) * _u[i,t,h] <= 0; */ # ======================================================= # Modelo extendido # ======================================================= param Ct{i in 1..F, j in 1..R, t in 1..T, tt in t..T} := P[i,t] + C[i,j,t] + sum{s in t+1..tt}H[i,s]; # Transportation unit cost from facility i to retailer j in period t var qt{i in 1..F, j in 1..R, t in 1..T, tt in t..T}, >= 0; # Amount produced at facility i for relailer j in period t # ======================================================= # Restrições da formulacao extendida # ======================================================= s.t. EXR1{i in 1..F, t in 1..T}: q[i,t] = sum{j in 1..R, tt in t..T}qt[i,j,t,tt]; s.t. EXR2{i in 1..F, j in 1..R, t in 1..T}: x[i,j,t] = sum{s in 1..t}qt[i,j,s,t]; s.t. EXR3{i in 1..F, t in 1..T}: I[i,t] = sum{tt in 1..t}q[i,tt] - sum{j in 1..R, tt in 1..t}x[i,j,tt]; s.t. EXR4{i in 1..F, t in 1..T}: I[i,t] = sum{j in 1..R}(sum{s in 1..t, tt in t..T}qt[i,j,s,tt] - sum{s in 1..t}qt[i,j,s,t]); # ======================================================= # Modelo extendido # ======================================================= minimize PEXFO: sum{i in 1..F, t in 1..T}(sum{j in 1..R, tt in t..T} Ct[i,j,t,tt]*qt[i,j,t,tt] + S[i,t]*y[i,t]); s.t. EXR5{j in 1..R, tt in 1..T}: sum{i in 1..F, t in 1..tt}qt[i,j,t,tt] = B[j,tt]; s.t. EXR6{i in 1..F, j in 1..R, t in 1..T, tt in t..T}: qt[i,j,t,tt] <= B[j,tt] * y[i,t]; # ======================================================= # Subproblema dual do modelo extendido # ======================================================= var v{j in 1..R, t in 1..T}; var w{i in 1..F, j in 1..R, t in 1..T, tt in t..T}, >= 0; maximize SPEXFO: sum{j in 1..R, t in 1..T}B[j,t] * v[j,t]; s.t. SPEXR1{i in 1..F, t in 1..T}:sum{j in 1..R, tt in t..T}B[j,tt] * w[i,j,t,tt] <= S[i,t]; s.t. SPEXR2{i in 1..F, j in 1..R, t in 1..T, tt in t..T}: v[j,tt] - w[i,j,t,tt] <= Ct[i,j,t,tt]; end;