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 * *******************************************************!)