Friday, June 17, 2011

Network formulation

I was looking at a model containing underlying traffic network. Such a network can be quite elegantly formulated in GAMS, but apparently many users still have problems with this. The mathematical formulation is:

image

The GAMS formulation can look like:

$ontext
 
max flow network example

 
Data from example in
    
Mitsuo Gen, Runwei Cheng, Lin Lin
    
Network Models and Optimization: Multiobjective Genetic Algorithm Approach
    
Springer, 2008

 
Erwin Kalvelagen,
 
Amsterdam Optimization,
 
May 2008

$offtext

sets
  i
'nodes' /node1*node11/
  source(i)
/node1/
  sink(i)
/node11/
;
alias(i,j);

abort$(card(source)<>1) "We want one source node"
;
abort$(card(sink)<>1) "We want one sink node"
;

parameter capacity(i,j) /

  
node1.node2 60,   node1.node3 60,   node1.node4 60,   node2.node3 30
  
node2.node5 40,   node2.node6 30,   node3.node4 30,   node3.node6 50
  
node3.node7 30,   node4.node7 40,   node5.node8 60,   node6.node5 20
  
node6.node8 30,   node6.node9 40,   node6.node10 30,  node7.node6 20
  
node7.node10 40,  node8.node9 30,   node8.node11 60,  node9.node10 30
  
node9.node11 50,  node10.node11 50 /;

set
arcs(i,j);
arcs(i,j)$capacity(i,j) =
yes
;
display
arcs;

parameter
rhs(i);
rhs(source) = -1;
rhs(sink) = 1;


variables

  x(i,j)
'flow along arcs'
  f     
'total flow'
;
positive variables x;
x.up(i,j) = capacity(i,j);


equations

   flowbal(i)
'flow balance' ;

flowbal(i)..
  
sum(arcs(j,i), x(j,i)) - sum
(arcs(i,j), x(i,j)) =e= f*rhs(i);

model m/flowbal/
;
solve m maximizing f using lp;