(!*********************************************************************
Mosel NL examples
=================
file loadbal.mos
````````````````
Convex NLP problem
Static load balancing in a tree computer network with two-way traffic.
A set of heterogeneous host computers are interconnected, in which each
node processes jobs (the jobs arriving at each node according to a time
invariant Poisson process) locally or sends it to a remote node.
In the latter case, there is a communication delay of forwarding the job
and getting a response back.
The problem is then to minimize the mean response time of a job.
The example considered here features 11 computers arranged as follows:
1 6 9
\ | /
\ | /
2---4---5---8---10
/ | \
/ | \
3 7 11
Based on AMPL model loadbal.mod
Source: http://www.orfe.princeton.edu/~rvdb/ampl/nlmodels/cute
Reference:
J. Li and H. Kameda,
"Optimal load balancing in tree network with two-way traffic",
Computer networks and ISDN systems, vol. 25, pp. 1335-1348, 1993.
(c) 2008 Fair Issac Corporation
author: S. Heipcke, Sep. 2008, rev. Jun. 2023
*********************************************************************!)
model "loadbal"
uses "mmxnlp", "mmsystem"
declarations
NODES : range ! Set of nodes (computers)
RL : range ! Set of directional arcs
ARC: dynamic array(NODES,NODES) of integer ! Network topology: matching node pairs with arcs
NCAP: array(NODES) of real ! Limits on node workload
DEM: array(NODES) of real ! Processing requests at nodes
FCAP: array(RL) of real ! Capacity of arcs
flow: array(RL) of mpvar ! Flow on arcs
process: array(NODES) of mpvar ! Workload at nodes
end-declarations
initialisations from "loadbal.dat"
ARC
DEM NCAP FCAP
end-initialisations
! Push variables away from bounds to avoid division by zero
BoundaryPush := 0.01
! Bounds and start values
forall(n in NODES) do
process(n)>=0; process(n)<=NCAP(n) - BoundaryPush
setinitval(process(n), DEM(n))
end-do
! Objective function: minimize response time
Obj:= sum(n in NODES) process(n)/(NCAP(n)-process(n))/102.8 +
sum(n,m in NODES | exists(ARC(n,m)))
((flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(80*flow(ARC(n,m))+20*flow(ARC(m,n))))/6.425)+
(flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(20*flow(ARC(n,m))+80*flow(ARC(m,n))))/25.7))
! Limits on arcs
forall(n,m in NODES | exists(ARC(n,m)))
CtrA(ARC(n,m)):= 20*flow(ARC(n,m))+80*flow(ARC(m,n)) <= FCAP(ARC(n,m))
! Flow balance in nodes
forall(n in NODES)
CtNODES(n):= sum(m in NODES | exists(ARC(m,n))) flow(ARC(m,n)) -
sum(m in NODES | exists(ARC(n,m))) flow(ARC(n,m)) = process(n) - DEM(n)
! Since this is a convex problem, it is sufficient to call a local solver
setparam("xprs_nlpsolver", 1)
setparam("XNLP_solver", 0) ! Solver choice: Xpress NonLinear (SLP)
setparam("XNLP_verbose", true)
! Solve the problem
minimise(Obj)
! Test whether a solution is available
nlstat:=getparam("XNLP_STATUS")
if nlstat<>XNLP_STATUS_LOCALLY_OPTIMAL and nlstat<>XNLP_STATUS_OPTIMAL then
writeln("No solution found.")
exit(0)
end-if
! Display the results
writeln("Solution: ", Obj.sol)
EPS:=0.001
writeln("Transfer:")
forall(n,m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS)
writeln(" ", n, "->", m, ": ", flow(ARC(n,m)).sol)
writeln("Workload at nodes:")
forall(n in NODES) do
write(strfmt(n,3), ": dem: ", DEM(n), " sol: ", process(n).sol, " (lim:", NCAP(n), ")")
forall(m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS)
write(" ->", m, ": ", flow(ARC(n,m)).sol)
forall(m in NODES | exists(ARC(m,n)) and flow(ARC(m,n)).sol>EPS)
write(" <-", m, ": ", flow(ARC(m,n)).sol)
writeln
end-do
end-model
|
(!*********************************************************************
Mosel NL examples
=================
file loadbal_graph.mos
``````````````````````
Convex NLP problem
Static load balancing in a tree computer network with two-way traffic.
A set of heterogeneous host computers are interconnected, in which each
node processes jobs (the jobs arriving at each node according to a time
invariant Poisson process) locally or sends it to a remote node.
In the latter case, there is a communication delay of forwarding the job
and getting a response back.
The problem is then to minimize the mean response time of a job.
The example considered here features 11 computers arranged as follows:
1 6 9
\ | /
\ | /
2---4---5---8---10
/ | \
/ | \
3 7 11
Based on AMPL model loadbal.mod
Source: http://www.orfe.princeton.edu/~rvdb/ampl/nlmodels/cute
Reference:
J. Li and H. Kameda,
"Optimal load balancing in tree network with two-way traffic",
Computer networks and ISDN systems, vol. 25, pp. 1335-1348, 1993.
- Graphical representation of results -
(c) 2008 Fair Issac Corporation
author: S. Heipcke, Sep. 2008, rev. Jun. 2023
*********************************************************************!)
model "loadbal"
uses "mmxnlp", "mmsvg"
declarations
NODES : range ! Set of nodes (computers)
RL : range ! Set of directional arcs
ARC: dynamic array(NODES,NODES) of integer ! Network topology: matching node pairs with arcs
NCAP: array(NODES) of real ! Limits on node workload
DEM: array(NODES) of real ! Processing requests at nodes
FCAP: array(RL) of real ! Capacity of arcs
flow: array(RL) of mpvar ! Flow on arcs
process: array(NODES) of mpvar ! Workload at nodes
end-declarations
initialisations from "loadbal.dat"
ARC
DEM NCAP FCAP
end-initialisations
! Push variables away from bounds to avoid division by zero
BoundaryPush := 0.01
! Bounds and start values
forall(n in NODES) do
process(n)>=0; process(n)<=NCAP(n) - BoundaryPush
setinitval(process(n), DEM(n))
end-do
! Objective function: minimize response time
Obj:= sum(n in NODES) process(n)/(NCAP(n)-process(n))/102.8 +
sum(n,m in NODES | exists(ARC(n,m)))
((flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(80*flow(ARC(n,m))+20*flow(ARC(m,n))))/6.425)+
(flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(20*flow(ARC(n,m))+80*flow(ARC(m,n))))/25.7))
! Limits on arcs
forall(n,m in NODES | exists(ARC(n,m)))
CtrA(ARC(n,m)):= 20*flow(ARC(n,m))+80*flow(ARC(m,n)) <= FCAP(ARC(n,m))
! Flow balance in nodes
forall(n in NODES)
CtNODES(n):= sum(m in NODES | exists(ARC(m,n))) flow(ARC(m,n)) -
sum(m in NODES | exists(ARC(n,m))) flow(ARC(n,m)) = process(n) - DEM(n)
! Since this is a convex problem, it is sufficient to call a local solver
setparam("xprs_nlpsolver", 1)
setparam("XNLP_solver", 0) ! Solver choice: Xpress NonLinear (SLP)
setparam("XNLP_verbose", true)
! Solve the problem
minimise(Obj)
! Test whether a solution is available
nlstat:=getparam("XNLP_STATUS")
if nlstat<>XNLP_STATUS_LOCALLY_OPTIMAL and nlstat<>XNLP_STATUS_OPTIMAL then
writeln("No solution found.")
exit(0)
end-if
! Display the results
writeln("Solution: ", Obj.sol)
EPS:=0.001
writeln("Transfer:")
forall(n,m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS)
writeln(" ", n, "->", m, ": ", flow(ARC(n,m)).sol)
writeln("Workload at nodes:")
forall(n in NODES) do
write(strfmt(n,3), ": dem: ", DEM(n), " sol: ", process(n).sol, " (lim:", NCAP(n), ")")
forall(m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS)
write(" ->", m, ": ", flow(ARC(n,m)).sol)
forall(m in NODES | exists(ARC(m,n)) and flow(ARC(m,n)).sol>EPS)
write(" <-", m, ": ", flow(ARC(m,n)).sol)
writeln
end-do
!**************** Graphical representation of results ****************
declarations
X,Y: array(NODES) of integer
end-declarations
initialisations from "loadbal.dat"
X Y
end-initialisations
! Draw nodes
svgaddgroup("Gcap", "Capacity", SVG_BLUE)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgaddgroup("Gwork", "Processing load", SVG_MAGENTA)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_OPACITY, 0.75)
svgaddgroup("Greq", "Demand", SVG_SILVER)
svgsetstyle(SVG_FILL,SVG_CURRENT)
svgsetstyle(SVG_OPACITY, 0.75)
FAC:=(max(n in NODES) DEM(n))*2
forall(n in NODES) do
svgaddcircle("Gcap", X(n), Y(n), NCAP(n)/FAC)
svgaddcircle("Greq", X(n), Y(n), DEM(n)/FAC)
svgaddcircle("Gwork", X(n), Y(n), process(n).sol/FAC)
end-do
! Draw the arcs
svgaddgroup("GrA", "Flow direction", svgcolor(50,150,50))
svgaddgroup("GrV", "Transfer volume", svgcolor(255,150,10))
forall(n,m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>0.001) do
svgaddline("GrV", X(n),Y(n),X(m),Y(m))
svgsetstyle(svggetlastobj,SVG_STROKEWIDTH, flow(ARC(n,m)).sol/2)
svgsetstyle(svggetlastobj,SVG_OPACITY, 0.25)
svgaddarrow("GrA", X(n),Y(n),X(m),Y(m))
end-do
! Scale the size of the displayed graph
svgsetgraphscale(20)
svgsave("loadbal.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model
|
