prodplan.gms : A Production Planning Example

**Description**

This uncapacitated lot-sizing problem finds the least cost production plan meeting demand requirements. There are costs given for producing, stocking, and setting up the machines. Four solving approaches are presented: 1) Solving the original model as a MIP 2) Solving a tight reformulation as an RMIP 3) Solving a tight reforumulation without stock as an RMIP 4) Solving the original model as an RMIP using a separation algorithm

**Reference**

- Pochet, Y, and Wolsey, L A, Production Planning by Mixed Integer Programming (Springer Series in Operations Research and Financial Engineering). Springer-Verlag New York, Inc., 2006.

**Small Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** prodplan.gms

```
$Title A Production Planning Example (PRODPLAN, SEQ=356)
$ontext
This uncapacitated lot-sizing problem finds the least cost production plan
meeting demand requirements. There are costs given for producing, stocking,
and setting up the machines.
Four solving approaches are presented:
1) Solving the original model as a MIP
2) Solving a tight reformulation as an RMIP
3) Solving a tight reforumulation without stock as an RMIP
4) Solving the original model as an RMIP using a separation algorithm
Pochet, Y, and Wolsey, L A, Production Planning by Mixed Integer
Programming (Springer Series in Operations Research and Financial
Engineering). Springer-Verlag New York, Inc., 2006.
$offtext
*1) Initial tiny formulation
Sets t Time periods / t1*t8 /
ut(t,t) Upper triangle;
Alias (t,tt,k);
Parameters
DEMAND(T) Demand per period / (t1,t2) 400, (t3,t4) 800, (t5*t8) 1200 /
SETUPCOST Setup cost per period / 5000 /
PRODCOST Production cost per period / 100 /
INVCOST Production cost per period / 5 /
STOCKINI Production cost per period / 200 /
BigM(T) Max production - BigM
;
*We assume that the initial stock is lower equal than the demand in the first period
abort$(Demand('t1') < STOCKINI) 'Initial stock is too large';
ut(k,t) = ord(k) <= ord(t);
BigM(t) = sum(k$(ord(k) >= ord(t)), DEMAND(k) - STOCKINI$(ord(t)=1));
Display ut, BigM;
Variables
s(t) Inventory in period t
x(t) Production in period t
y(t) Setup in period t
cost
Binary variable y; Positive variables s,x;
Equations
Balance(t) Stock balance
Production(t) Production set-up
Mincost Objective function
;
Mincost.. cost =e= sum(t, ifthen(ord(t)<card(t),INVCOST,INVCOST/2)*s(t))
+ sum(t, SETUPCOST*y(t) + PRODCOST*x(t));
Production(t).. x(t) =L= BigM(t)*y(t);
Balance(t).. STOCKINI$(ord(t)=1) + s(t-1) + x(t) =e= DEMAND(t) + s(t);
Model tiny / Mincost, Production, Balance /;
tiny.optcr=0;
Solve tiny minimizing cost using MIP;
*2) Multi-commodity formulation (tight reformulation)
Variables
smc(t,t) Inventory entered in period i for period t
xmc(t,t) Production in period i for demand in t
Positive variables smc,xmc;
Equations
Balancemc(t,t) Stock balance
Productionmc(t,t) Production set-up
Mincostmc Objective function
;
Mincostmc.. cost =e= sum(ut, PRODCOST*xmc(ut) + INVCOST*smc(ut))
+ sum(t, SETUPCOST*y(t));
Balancemc(ut(k,t)).. STOCKINI$(ord(t)=1) + smc(k-1,t) + xmc(k,t)
=E= smc(k,t) + diag(k,t)*DEMAND(t);
Productionmc(ut(k,t)).. xmc(k,t) =L= (DEMAND(t) - STOCKINI$(ord(t)=1))*y(k);
Model tinymc / Mincostmc, Balancemc, Productionmc /;
Solve tinymc minimizing cost using RMIP;
*3) Multi-commodity formulation without stock (tight reformulation)
Parameter
dist(t,t) Distance between time periods;
dist(ut(k,t)) = ord(t)-ord(k); Display dist;
Equations
Demandmcws(t) Demand satisfaction
Mincostmcws Objective function
;
Mincostmcws.. cost =e= sum(ut, PRODCOST*xmc(ut) + INVCOST*dist(ut)*xmc(ut))
+ sum(t, SETUPCOST*y(t));
Demandmcws(t).. sum(ut(k,t), xmc(k,t)) =g= DEMAND(t) - STOCKINI$(ord(t)=1);
Model tinymcws / Mincostmcws, Demandmcws, Productionmc /;
Solve tinymcws minimizing cost using RMIP;
*4) Separation Algorithm
Sets j Iterations /j1*j10/
n(j,t) Set of cuts
Scon(j,t,t) Set of violated constraints;
n(j,t)=no; Scon(j,t,t)=no;
Alias (t,l), (j,jj);
Parameter
D(t,t) Accumulated demand
left(t,t) Left side of cut;
D(ut(t,k)) = sum[tt$(ord(tt) <= ord(k) and ord(tt) >= ord(t)), DEMAND(tt)];
Equation
cuts(j,t) Cuts for the RMIP (complete linear description);
cuts(n(jj,t)).. sum(Scon(jj,t,k), x(k) - D(k,t)*y(k)) =l= s(t);
Model tinycuts / tiny, cuts /;
Scalar more / 1 /
epsilon / 1e-6 /;
file fx; put fx;
*If STOCKINI < DEMAND(t1) there has to be production in the first period
y.fx('t1') = 1;
loop(j$more,
Solve tinycuts using RMIP min cost;
option limcol=0, limrow=0, solprint=silent;
*Store the left hand side of potential cuts
left(ut(tt,l)) = x.l(tt)-d(tt,l)*y.l(tt);
*Use only those LHS which are greater zero
Scon(j,l,tt) = left(tt,l) > epsilon;
*If the sum of those is greater than the inventory level: violation found
*Add this cut to the model
n(j,l)= sum[Scon(j,l,tt), left(tt,l)] - epsilon > s.l(l);
*Proceed if at least one cut was added during this iteration
more = sum(n(j,l), yes);
);
Put_utility$(not more) 'log' /
'>>>>Integer solution found. A total of 'sum(n(j,t),1):0:0' cuts were added.';
```