# AMPL node-arc model file for the all-pairs uniform-capacity 
# maximum concurrent flow problem.

param n;		  # n is the number of nodes in the graph

param filename symbolic default ' ';

set V := {1 .. n};	  # Vertices in the graph
set E within {V,V};	  # Edges in the graph

set INTRACOM_EDGES within E default {};


# A is the set of directed arcs for the network flow model
set A within {V,V} := {i in V, j in V: (i,j) in E or (j, i) in E};

# By default we assume there is demand for
# one unit of flow between all pairs of nodes
# in the network. Thus d[i,j] = 1 if i < j, and zero otherwise.
param d {i in V, j in V} default if i < j then 1 else 0;

# There are n-1 commodities in this model.
#
# With fixed demand of one unit between all pairs, the model would work as follows:
#
# There is a supply of n-1 units of commodity 1 at node 1.
# There is a demand for 1 unit of commodity 1 at nodes 2, 3, ..., n.
#
# There is a supply of n-2 units of commodity 2 at node 2.
# There is a demand for 1 unit of commodity 2 at nodes 3, 4, ..., n.
#
# There is a supply of n-i units of commodity i at node i.
# There is a demand for 1 unit of commodity i at nodes i+1, i+2, ..., n.

# some data files use c[i,j] as the weight of undirected edge (i,j)
param c {(i,j) in E} default 1;	

# some data files use C[i,j] as the weight of undirected edge (i,j)
param C {(i,j) in E} default 1;

param w {(i,j) in E} default C[i,j];	 # w[i,j] is the weight of undirected edge (i,j)


var flow {v in 1 .. n-1, (i,j) in A} >= 0;

var z;

param selected_component default 1;

maximize concurrent_flow: z;

subject to supply {i in 1 .. n-1}:
sum{j in V: (i,j) in A} flow[i,i,j] = sum{j in V: j > i} d[i,j]*z;

subject to transshipment {k in 1 .. n-1, i in 1 .. k -1}:
sum{j in V: (i,j) in A} flow[k,i,j] = 
sum{j in V: (j,i) in A} flow[k,j,i];

subject to demand {k in 1 .. n-1, j in k+1 .. n}:
sum{i in V: (j,i) in A} flow[k,j,i] -
sum{i in V: (i,j) in A} flow[k,i,j] = 
-z*d[k,j];

subject to edge_capacity {(i,j) in E}:
sum{k in 1 .. n-1} (flow[k,i,j] + flow[k,j,i]) <= c[i,j];