(!*******************************************************
Mosel Example Problems
======================
file runelsd.mos
````````````````
Run several instances of the model elsd.mos in
parallel and coordinate the solution update.
-- Distributed computing version --
Before running this model, you need to set up the array
NodeNames with machine names/addresses of your local network.
All nodes that are used need to have the same version of
Xpress installed and suitably licensed, and the server
"xprmsrv" must have been started on these machines.
All files are local to the root node, no write access is
required at remote nodes.
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010, rev. Jun. 2015
*******************************************************!)
model "Els main"
uses "mmjobs", "mmsystem"
parameters
DATAFILE = "els.dat"
T = 15
P = 4
end-parameters
declarations
RI = 1..2 ! Set of (remote) Mosel instances
RM = 0..5 ! Range of models
TIMES = 1..T ! Time periods
PRODUCTS = 1..P ! Set of products
solprod: array(PRODUCTS,TIMES) of real ! Sol. values for var.s produce
solsetup: array(PRODUCTS,TIMES) of real ! Sol. values for var.s setup
DEMAND: array(PRODUCTS,TIMES) of integer ! Demand per period
modELS: array(RM) of Model ! Models
NEWSOL = 2 ! Identifier for "sol. found" event
Msg: Event ! Messages sent by models
params: text ! Submodel runtime parameters
moselInst: array(RI) of Mosel ! (Remote) Mosel instances
NodeNames: array(RI) of string ! Node names for remote connections
end-declarations
! Setting up remote connections
! Use machine names within your local network, IP addresses, or
! empty string for the current node running this model
NodeNames :: (1..2)["", "localhost"]
! Start the remote Mosel instances
forall(i in RI)
if connect(moselInst(i), NodeNames(i))<>0 then exit(1); end-if
! Compile, load, and run models M1 and M2
M1:= 1; M2:=3
res:= compile("elsd.mos") ! Compile locally
load(moselInst(1), modELS(M1), "rmt:elsd.bim") ! Load on remote nodes
load(moselInst(2), modELS(M2), "rmt:elsd.bim")
forall(m in RM) modELS(m).uid:= m
setmodpar(params, "DATAFILE", DATAFILE)
setmodpar(params, "T", T); setmodpar(params, "P", P)
! Start submodel runs
setmodpar(params, "ALG", M1); run(modELS(M1), params)
setmodpar(params, "ALG", M2); run(modELS(M2), params)
objval:= MAX_REAL
algsol:= -1; algopt:= -1
repeat
wait ! Wait for the next event
Msg:= getnextevent ! Get the event
if getclass(Msg)=NEWSOL then ! Get the event class
if getvalue(Msg) < objval then ! Value of the event (= obj. value)
algsol:= Msg.fromuid ! ID of model sending the event
objval:= getvalue(Msg)
writeln("Improved solution ", objval, " found by model ", algsol)
forall(m in RM | m <> algsol) send(modELS(m), NEWSOL, objval)
else
writeln("Solution ", getvalue(Msg), " found by model ", Msg.fromuid)
end-if
end-if
until getclass(Msg)=EVENT_END ! A model has finished
algopt:= Msg.fromuid ! Retrieve ID of terminated model
forall(m in RM) stop(modELS(m)) ! Stop all running models
if algsol=-1 then
writeln("No solution available")
exit(1)
else ! Retrieve the best solution from shared memory
initializations from "bin:sol_"+algsol
solprod
solsetup
end-initializations
initializations from DATAFILE
DEMAND
end-initializations
! Solution printing
writeln("Best solution found by model ", algsol)
writeln("Optimality proven by model ", algopt)
writeln("Objective value: ", objval)
write("Period setup ")
forall(p in PRODUCTS) write(strfmt(p,-7))
forall(t in TIMES) do
write("\n ", strfmt(t,2), strfmt(sum(p in PRODUCTS) solsetup(p,t),8), " ")
forall(p in PRODUCTS) write(strfmt(solprod(p,t),3), " (",DEMAND(p,t),")")
end-do
writeln
end-if
! Cleaning up temporary files
forall(m in RM) fdelete("sol_"+m)
fdelete("elsd.bim")
end-model
|
(!*******************************************************
Mosel Example Problems
======================
file elsd.mos
`````````````
Economic lot sizing, ELS, problem
(Cut generation algorithm adding (l,S)-inequalities
in one or several rounds at the root node or in
tree nodes)
-- Distributed computing version --
*** Can be run standalone - intended to be run from runelsd.mos ***
ELS considers production planning over a horizon
of T periods. In period t, t=1,...,T, there is a
given demand DEMAND[p,t] that must be satisfied by
production produce[p,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[p,t]. There is no inventory
or stock-holding cost.
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010, rev. Sep. 2014
*******************************************************!)
model Els
uses "mmxprs","mmsystem","mmjobs"
parameters
ALG = 0 ! Default algorithm: no user cuts
CUTDEPTH = 3 ! Maximum tree depth for cut generation
DATAFILE = "els4.dat"
T = 60
P = 4
RMT = "rmt:" ! Files are on root node
end-parameters
forward public function cb_node: boolean
forward procedure tree_cut_gen
forward public function cb_updatebnd: boolean
forward public procedure cb_intsol
declarations
NEWSOL = 2 ! "New solution" event class
EPS = 1e-6 ! Zero tolerance
TIMES = 1..T ! Time periods
PRODUCTS = 1..P ! 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 real ! 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
Msg: Event ! An event
end-declarations
initializations from RMT+DATAFILE
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) )
! Production in period t must not exceed the total demand for the
! remaining periods; 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)
! Production in periods 0 to t must satisfy the total demand
! during this period of time
forall(p in PRODUCTS,t in TIMES)
sum(s in 1..t) produce(p,s) >= sum (s in 1..t) DEMAND(p,s)
! Capacity limits
forall(t in TIMES) 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
setparam("zerotol", EPS/100) ! Set Mosel comparison tolerance
starttime:=gettime
setparam("XPRS_THREADS", 1) ! No parallel threads for optimization
! Uncomment to get detailed MIP output
! setparam("XPRS_VERBOSE", true)
setparam("XPRS_LPLOG", 0)
setparam("XPRS_MIPLOG", -1000)
writeln("**************ALG=",ALG,"***************")
SEVERALROUNDS:=false; TOPONLY:=false
case ALG of
1: do
setparam("XPRS_CUTSTRATEGY", 0) ! No cuts
setparam("XPRS_HEURSTRATEGY", 0) ! No heuristics
end-do
2: do
setparam("XPRS_CUTSTRATEGY", 0) ! No cuts
setparam("XPRS_HEURSTRATEGY", 0) ! No heuristics
setparam("XPRS_PRESOLVE", 0) ! No presolve
end-do
3: tree_cut_gen ! User branch-and-cut (single round)
4: do ! User branch-and-cut (several rounds)
tree_cut_gen
SEVERALROUNDS:=true
end-do
5: do ! User cut-and-branch (several rounds)
tree_cut_gen
SEVERALROUNDS:=true
TOPONLY:=true
end-do
end-case
! Parallel setup
setcallback(XPRS_CB_PRENODE, "cb_updatebnd")
setcallback(XPRS_CB_INTSOL, "cb_intsol")
! Solve the problem
minimize(MinCost)
!*************************************************************************
! Cut generation loop:
! get the solution values
! identify violated constraints and add them as cuts to the problem
! re-solve the modified problem
!*************************************************************************
public function cb_node:boolean
declarations
ncut:integer ! Counter for cuts
cut: array(range) of linctr ! Cuts
cutid: array(range) of integer ! Cut type identification
type: array(range) of integer ! Cut constraint type
objval,ds: real
end-declarations
depth:=getparam("XPRS_NODEDEPTH")
if((TOPONLY and depth<1) or (not TOPONLY and 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
! Add the violated inequality: the minimum of the actual production
! produce(p,t) and the maximum potential production D(p,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(produce(p,t), D(p,t,l)*setup(p,t)) >= D(p,1,l)
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
returned:=false ! Call this function once per node
! Add cuts to the problem
if(ncut>0) then
addcuts(cutid, type, cut);
writeln("Model ", ALG, ": Cuts added : ", ncut,
" (depth ", depth, ", node ", getparam("XPRS_NODES"),
", obj. ", getparam("XPRS_LPOBJVAL"), ")")
if SEVERALROUNDS then
returned:=true ! Repeat until no new cuts generated
end-if
end-if
end-if
end-function
! ****Optimizer settings for using the cut manager****
procedure tree_cut_gen
setparam("XPRS_HEURSTRATEGY", 0) ! Switch heuristics off
setparam("XPRS_CUTSTRATEGY", 0) ! Switch automatic cuts off
setparam("XPRS_PRESOLVE", 0) ! Switch presolve off
setparam("XPRS_EXTRAROWS", 5000) ! Reserve extra rows in matrix
setcallback(XPRS_CB_CUTMGR, "cb_node") ! Define the cut manager callback
end-procedure
!*************************************************************************
! Setup for parallel solving:
! check whether cutoff update required at every node
! store and communicate any new solution found
!*************************************************************************
! Update cutoff value
public function cb_updatebnd: boolean
if not isqueueempty then
repeat
Msg:= getnextevent
until isqueueempty
newcutoff:= getvalue(Msg)
cutoff:= getparam("XPRS_MIPABSCUTOFF")
writeln("Model ", ALG, ": New cutoff: ", newcutoff,
" old: ", cutoff)
if newcutoff<cutoff then
setparam("XPRS_MIPABSCUTOFF", newcutoff)
end-if
if (newcutoff < getparam("XPRS_LPOBJVAL")) then
returned:= true ! Node becomes infeasible
end-if
end-if
end-function
! Store and communicate new solution
public procedure cb_intsol
objval:= getparam("XPRS_LPOBJVAL") ! Retrieve current objective value
cutoff:= getparam("XPRS_MIPABSCUTOFF")
writeln("Model ", ALG, ": Solution: ", objval, " cutoff: ", cutoff)
if(cutoff > objval) then
setparam("XPRS_MIPABSCUTOFF", objval)
end-if
! 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
! Store the solution in shared memory
initializations to "bin:" + RMT + "sol_"+ALG
solprod
solsetup
end-initializations
! Send "solution found" signal
send(NEWSOL, objval)
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.
|
