FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Static load balancing in a computer network

Description
Static load balancing in a tree computer network with two-way traffic. A set of heterogeneous host computers are interconnected; every node processes jobs (the jobs arrive 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 for forwarding the job and getting a response back.


Source Files

Data Files





loadbal_graph.mos

(!*********************************************************************
   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. Sep. 2017
*********************************************************************!)

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) 

! Solve the problem
 setparam("XNLP_verbose", true)
 setparam("XNLP_solver", 0)
 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

Back to examples browserPrevious exampleNext example