| |||||||||
Cut generation for an economic lot-sizing (ELS) problem Description This model implements various forms of cut-and-branch and branch-and-cut algorithms. In its simplest form (looping over LP solving) it illustrates the following
features:
Another implementation (main model: runels.mos, submodel: elsp.mos) parallelizes the execution of several model instances, showing the following features:
Further explanation of this example: elscb.mos, elsglobal.mos, runels.mos: Xpress Whitepaper 'Multiple models and parallel solving with Mosel', Section 'Solving several model instances in parallel'.
Source Files By clicking on a file name, a preview is opened at the bottom of this page. Data Files elsglobal.mos (!******************************************************* Mosel Example Problems ====================== file elsglobal.mos `````````````````` Economic lot sizing, ELS, problem (Cut generation algorithm adding (l,S)-inequalities in several rounds at tree nodes) Model version with (optional) global tree cuts Economic lot sizing (ELS) considers production planning over a given planning horizon. In every period, there is a given demand for every product that must be satisfied by the production in this period and by inventory carried over from previous periods. A set-up cost is associated with production in a period, and the total production capacity per period is limited. The unit production cost per product and time period is given. There is no inventory or stock-holding cost. *** This model cannot be run with a Community Licence for the provided data instance *** (c) 2008 Fair Isaac Corporation author: N. Verma, 2006, rev. July 2023 *******************************************************!) model "ELS (global cuts)" uses "mmxprs","mmsystem" parameters CUTDEPTH = 10 ! Maximum tree depth for cut generation EPS = 1e-6 ! Zero tolerance GLOBAL = true ! Apply global cuts end-parameters forward function cb_node:boolean forward procedure tree_cut_gen declarations TIMES = 1..15 ! Range of time PRODUCTS = 1..4 ! Set of products DEMAND: array(PRODUCTS,TIMES) of integer ! Demand per period SETUPCOST: array(TIMES) of integer ! Setup cost per period PRODCOST: array(PRODUCTS,TIMES) of integer ! Production cost per period CAP: array(TIMES) of integer ! Production capacity per period D: array(PRODUCTS,TIMES,TIMES) of integer ! Total demand in periods t1 - t2 produce: array(PRODUCTS,TIMES) of mpvar ! Production in period t setup: array(PRODUCTS,TIMES) of mpvar ! Setup in period t solprod: array(PRODUCTS,TIMES) of real ! Sol. values for var.s produce solsetup: array(PRODUCTS,TIMES) of real ! Sol. values for var.s setup starttime: real num_cuts_added:integer end-declarations initializations from "els.dat" DEMAND SETUPCOST PRODCOST CAP end-initializations forall(p in PRODUCTS,s,t in TIMES) D(p,s,t):= sum(k in s..t) DEMAND(p,k) ! Objective: minimize total cost MinCost:= sum(t in TIMES) (SETUPCOST(t) * sum(p in PRODUCTS) setup(p,t) + sum(p in PRODUCTS) PRODCOST(p,t) * produce(p,t) ) ! Satisfy the total demand forall(p in PRODUCTS,t in TIMES) Dem(p,t):= sum(s in 1..t) produce(p,s) >= sum (s in 1..t) DEMAND(p,s) ! If there is production during t then there is a setup in t forall(p in PRODUCTS, t in TIMES) ProdSetup(p,t):= produce(p,t) <= D(p,t,getlast(TIMES)) * setup(p,t) ! Capacity limits forall(t in TIMES) Capacity(t):= sum(p in PRODUCTS) produce(p,t) <= CAP(t) ! Variables setup are 0/1 forall(p in PRODUCTS, t in TIMES) setup(p,t) is_binary ! Without this setting behaviour of B&B is somewhat non-deterministic setparam("XPRS_THREADS", 1) ! Uncomment to get detailed MIP output setparam("XPRS_VERBOSE", true) ! All cost data are integer, we therefore only need to search for integer ! solutions setparam("XPRS_MIPADDCUTOFF", -0.999) ! Set Mosel comparison tolerance to a sufficiently small value setparam("ZEROTOL", EPS/100) starttime:=gettime tree_cut_gen ! User branch-and-cut (several rounds) setparam("XPRS_CUTSTRATEGY", 0) ! No automatic cuts minimize(MinCost) ! Solve the problem writeln("Time: ", gettime-starttime, "sec, Nodes: ", getparam("XPRS_NODES"), ", Solution: ", getobjval) write("Period setup ") forall(p in PRODUCTS) write(strfmt(p,-7)) forall(t in TIMES) do write("\n ", strfmt(t,2), strfmt(getsol(sum(p in PRODUCTS) setup(p,t)),8), " ") forall(p in PRODUCTS) write(getsol(produce(p,t)), " (",DEMAND(p,t),") ") end-do writeln !************************************************************************* ! Cut generation loop: ! get the solution values ! identify and set up violated constraints ! load the modified problem and load the saved basis !************************************************************************* function cb_node:boolean declarations ncut:integer CutRange: range ! Counter for cuts cut: array(CutRange) of linctr ! Cuts cutid: array(CutRange) of integer ! Cut type identification type: array(CutRange) of integer ! Cut constraint type ndx_cuts: set of integer ! Index of cuts active_cuts,violated_cuts: set of integer objval,ds: real cut_indices: set of integer viol: dynamic array(range) of real end-declarations returned:=false ! OPTNODE: This node is not infeasible node:=getparam("XPRS_NODES") depth:=getparam("XPRS_NODEDEPTH") if depth<=CUTDEPTH then ncut:=0 ! Get the solution values forall(t in TIMES, p in PRODUCTS) do solprod(p,t):=getsol(produce(p,t)) solsetup(p,t):=getsol(setup(p,t)) end-do ! Search for violated constraints forall(p in PRODUCTS,l in TIMES) do ds:=0 forall(t in 1..l) if (solprod(p,t) < D(p,t,l)*solsetup(p,t) + EPS) then ds += solprod(p,t) else ds += D(p,t,l)*solsetup(p,t) end-if ! Generate the violated inequality if ds < D(p,1,l) - EPS then cut(ncut):= sum(t in 1..l) if(solprod(p,t)<(D(p,t,l)*solsetup(p,t))+EPS, produce(p,t), D(p,t,l)*setup(p,t)) - D(p,1,l) cutid(ncut):= 1 type(ncut):= CT_GEQ ncut+=1 end-if end-do ! Add cuts to the problem if ncut>0 then if GLOBAL then storecuts(0,cutid,type,cut,ndx_cuts) writeln("Stored cuts at node ", node, " -> ", getsize(ndx_cuts)) getcplist(1,1,0, violated_cuts,viol) writeln("Current violated cuts in the cutpool after solving node ", node, " -> ", getsize(violated_cuts)) loadcuts(1,1,violated_cuts) else addcuts(cutid, type, cut); num_cuts_added+=ncut if(getparam("XPRS_VERBOSE")=true) then writeln("Cuts added : ", ncut, " (depth ", depth, ", node ", node, ", obj. ", getparam("XPRS_LPOBJVAL"), ") count=", num_cuts_added) end-if end-if else getcplist(1,1,0, violated_cuts,viol) if getsize(violated_cuts)>0 then writeln("All violated cuts in the cutpool after solving node ", node, " -> ", getsize(violated_cuts)) writeln("######################### VIOLATED #########################") end-if delcuts(true,0,-1,-MAX_REAL) ! Delete all cuts from problem at current node that are not required ! writeln("Cuts with non-basic slack are deleted at node ", node) end-if end-if end-function ! ****Optimizer settings for using the cut manager**** procedure tree_cut_gen setparam("XPRS_PRESOLVEOPS",2270) ! Non-destructive presolve only ! setparam("XPRS_PRESOLVE", 0) ! Switch presolve off setparam("XPRS_EXTRAROWS", 5000) ! Reserve extra rows in matrix setcallback(XPRS_CB_OPTNODE, ->cb_node) ! Set the optnode callback function end-procedure end-model | |||||||||
© Copyright 2024 Fair Isaac Corporation. |