# Quadratic Integer Programming Model
# GreenWave Routing for WSNs

set S;                  # sensors
set R;                  # sinks
set V := S union R;     # all nodes
set E within {u in V, v in V: u<>v};    # edges

param c0{E} >= 0;               # cost matrix
param Lambda := 10;             # frame size
param p := 0.5;

# main (binary) variables to be solved: Define a flow k for each sensor node.
var X {(u,v) in E, k in S} binary;
var Y {v in V} = sum{(u,v) in E, k in S} X[u,v,k];

# combinatorial case (ignore edge weights - just ~load balancing)
#var Z{k in S} = sum{(u,v) in E} X[u,v,k]*Y[v];

var Z{k in S} = sum{(u,v) in E} X[u,v,k]*(Lambda*p*Y[v] + c0[u,v]);

# OBJECTIVE FUNCTION
minimize Total_Cost: sum{k in S} Z[k];

# each commodity s starts at source vertex s
subject to S_out {s in S}: sum{(s,v) in E} X[s,v,s] = 1;

# each commodity must reach a destination vertex
subject to R_in {k in S}: sum{s in S, r in R: (s,r) in E} X[s,r,k]=1;

# flow conservation equations for intermediate nodes  
subject to Balance{k in S, i in S: k<>i}: sum{(i,j) in E} X[i,j,k] = sum{j in S: (j,i) in E} X[j,i,k];

data;
set R := 1 2;
set S := 3 4 5 6 7 8 9 10;

#@
param: E:       c0 :=
	   1    8      6
	   8    1      4
	   2    4      4
	   4    2      6
	   2    5      2
	   5    2      8
	   2    6      1
	   6    2      9
	   2    9      2
	   9    2      8
	   2   10      5
	  10    2      5
	   3    4      3
	   4    3      7
	   3    6     10
	   6    3     10
	   3    7      7
	   7    3      3
	   3   10      4
	  10    3      6
	   4    5      8
	   5    4      2
	   4    6      7
	   6    4      3
	   4    7      4
	   7    4      6
	   4    8      6
	   8    4      4
	   4    9      8
	   9    4      2
	   4   10      1
	  10    4      9
	   5    8      8
	   8    5      2
	   5    9      9
	   9    5      1
	   5   10      3
	  10    5      7
	   6    7      7
	   7    6      3
	   6   10      4
	  10    6      6
	   7   10      7
	  10    7      3
	   8    9      2
	   9    8      8
	   8   10      5
	  10    8      5
;

solve;
 option omit_zero_rows 1;
 display X;