Economic Lot Sizing Model
milp
FICO-Xpress
MOSEL
short
= sum (s in 1..t) DEMAND(s)
forall(t in RT) setup(t) is_binary ! Variables setup are 0/1
cutgen ! Solve by cut generation
! Print out the solution
forall(t in RT)
writeln("Period ", t,": prod ", getsol(product(t))," (demand: ", DEMAND(t),
", cost: ", PRODCOST(t), "), setup ", getsol(setup(t)),
" (cost: ", SETUPCOST(t), ")")
!*************************************************************************
! Cut generation loop at the top node:
! solve the LP and save the basis
! get the solution values
! identify and set up violated constraints
! load the modified problem and load the saved basis
!*************************************************************************
procedure cutgen
declarations
ncut,npass,npcut:integer ! Counters for cuts and passes
solprod,solsetup: array(RT) of real ! Sol. values for var.s product & setup
objval,starttime,ds: real
cut: array(range) of linctr
bas: basis
end-declarations
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
setparam("XPRS_PRESOLVE", 0) ! Switch presolve off
ncut:=0
npass:=0
repeat
npass+=1
npcut:= 0
minimize(XPRS_LIN+XPRS_PRI, MinCost) ! Solve the LP using primal simplex
savebasis(bas) ! Save the current basis
objval:= getobjval ! Get the objective value
forall(t in RT) do ! Get the solution values
solprod(t):=getsol(product(t))
solsetup(t):=getsol(setup(t))
end-do
! Search for violated constraints:
forall(l in RT) do
ds:=0
forall(t in 1..l)
if(solprod(t) < D(t,l)*solsetup(t) + EPS) then ds += solprod(t)
else ds += D(t,l)*solsetup(t)
end-if
! Add the violated inequality: the minimum of the actual production
! prod(t) and the maximum potential production D(t,l)*setup(t)
! in periods 1 to l must at least equal the total demand in periods
! 1 to l.
! sum(t=1:l) min(product(t), D(t,l)*setup(t)) >= D(1,l)
if(ds < D(1,l) - EPS) then
ncut+=1
npcut+=1
cut(ncut):= sum(t in 1..l)
if(solprod(t)<(D(t,l)*solsetup(t))+EPS, product(t), D(t,l)*setup(t)) >=
D(1,l)
end-if
end-do
writeln("Pass ", npass, " objective value ",
objval, ", cuts added: ", npcut, " (total ", ncut,")")
if(npcut=0) then
writeln("Optimal integer solution found:")
else
loadprob(MinCost) ! Reload the problem
loadbasis(bas) ! Load the saved basis
end-if
until (npcut<=0 or npass>4)
end-procedure
end-model
Economic Lot-Sizing (ELS)
=========================
A well-known class of valid inequalities for ELS are the
(l,S)-inequalities. Let D(pq) denote the total demand in periods p
to q and y(t) be a binary variable indicating whether there is any
production in period t. For each period l and each subset of periods S
of 1 to l, the (l,S)-inequality is
sum (t=1:l | t in S) x(t) + sum (t=1:l | t not in S) D(tl) * y(t)
>= D(1l)
It says that actual production x(t) in periods included S plus maximum
potential production D(tl)*y(t) in the remaining periods (those not in
S) must at least equal total demand in periods 1 to l. Note that in
period t at most D(tl) production is required to meet demand up to
period l.
Based on the observation that
sum (t=1:l | t in S) x(t) + sum (t=1:l | t not in S) D(tl) * y(t)
>= sum (t=1:l) min(x(t), D(tl) * y(t))
>= D(1l)
it is easy to develop a separation algorithm and thus a cutting plane
algorithm based on these (l,S)-inequalities.
]]>
(!*******************************************************
* Mosel Example Problems *
* ====================== *
* *
* file els.mos *
* ```````````` *
* Example for the use of the Mosel language *
* (Economic lot sizing, ELS, problem, solved by *
* adding(l,S)-inequalities) in several rounds *
* looping over the root node) *
* *
* ELS considers production planning over a horizon *
* of T periods. In period t, t=1,...,T, there is a *
* given demand DEMAND[t] that must be satisfied by *
* production prod[t] in period t and by inventory *
* carried over from previous periods. There is a *
* set-up up cost SETUPCOST[t] associated with *
* production in period t. The unit production cost *
* in period t is PRODCOST[t]. There is no inventory *
* or stock-holding cost. *
* *
* (c) 2001 Dash Associates *
* author: S. Heipcke *
*******************************************************!)