# Solution to sheet 4, exercise 1.
# Lecture: Integer Programming in Public Transport  (TU Berlin, winter term 2006/07).
# Ralf Borndoerfer, Christian Liebchen, and Marc Pfetsch
#
# Direct travelers model for line planning.
#
# Marc Pfetsch
# 11/2006
# ------------------------------------------------------------------------------
#
# The data are:
# - edges   edges of the graph. They are directed and the data should contain
#           forward and backward directions if necessary.
# - load    passenger load on each edge
# - odnodes contains a list of all OD-nodes, which are a subset of the nodes of
#           the graph. We need this for reading and accessing the OD-matrix.
# - od      OD-matrix
# - lines   edges on lines. The lines are taken as undirected, i.e., the file
#           only contains one direction and the model has to take care to check
#           both directions.
# ------------------------------------------------------------------------------
# sets:

# OD-Nodes
# The OD-nodes could be inferred from the edges "E", but
# for reading the OD-matrix we need the correct order.
set O := { read "odnodes.dat" as "<1s>" comment "#" };

# edges (directed!)
set E := { read "edges.dat" as "<1s,2s>" comment "#" };

# line set
set line := { read "lines.dat" as "<1s,2s,3s>" comment "#" };

# line names
set L := proj(line,<1>);

# nodes on lines
set N := proj(line, <1,2>) union proj(line, <1,3>);

do print "Number of OD-nodes:";
do print card(O);

do print "Number of edges:";
do print card(E);

do print "Number of lines:";
do print card(L);


# ------------------------------------------------------------------------------
# parameters:

# load on each edge
param load[E] := read "load.dat" as "<1s,2s> 3n" comment "#";

# OD-matrix
param d[O*O] := read "od.dat" as "n+" comment "#";

# Parameters for computing the capacity
param carcap := 467;
param maxcars := 5;
param traincap := maxcars * carcap;
param maxfreq := 10;

# compute lower bound on frequency
param lbf[<u,v> in E] := ceil(load[u,v]/traincap);

# ------------------------------------------------------------------------------
# sets once again:

# demand pairs
set D := { <s,t> in O * O with d[s,t] > 0 };

# possible combinations for traveling: 
# direct connection between all nodes s and t that lie on line l:
set R := { <l,s,t> in L*D with <l,s> in N and <l,t> in N };

# ------------------------------------------------------------------------------
# checks
do forall <l,u,v> in line do check <u,v> in E and <v,u> in E;

# ------------------------------------------------------------------------------
# variables:

# y[l,s,t] direct travelers on line l from s to t
var y[R] integer >= 0;

# f[l] frequency of line l
var f[L] integer >= 0;

# ------------------------------------------------------------------------------
# objective

maximize obj: sum <l,s,t> in R do y[l,s,t];

# ------------------------------------------------------------------------------
# constraints

# note that the graph is directed - hence we have to include 
# the back direction as well
subto lb: 
	forall <u,v> in E:
	sum <l> in L with <l,u,v> in line or <l,v,u> in line: f[l] >= lbf[u,v];

subto ub: 
	forall <u,v> in E:
	sum <l> in L with <l,u,v> in line or <l,v,u> in line: f[l] <= maxfreq;

subto demand:
	forall <s,t> in D:
	sum <l> in L with <l,s,t> in R: y[l,s,t] <= d[s,t];

subto capacity:
	forall <l> in L:
	sum <s,t> in D with <l,s,t> in R: y[l,s,t] - traincap * f[l] <= 0;