# 1-depot Lagrange relaxation of minimum cost vehicle scheduling problem.
#
# Lecture on Integer Programming and Public Transport
# WS 2006/07
# Technische Universitaet Berlin, Fakultaet 2, Institut fuer Mathematik
# Assignment 6, exercise 3 
# Ralf Borndoerfer
# 01/2007
#
# ------------------------------------------------------------------------------
#
# The data are:
#
# - A  	   arcs: set of all arcs, defined by tail, head, and depot
# - E  	   deadheads: set of all deadhead trips corresponding to the arcs
# - V  	   nodes: set of all nodes, corresponding to timetabled trips plus an
#      	   artificial depot node 0 
# - W  	   trips: set of all timetabled trips
# - D  	   depots: set of depots
# - c  	   costs: array of arc costs
# - F  	   flows: set of relaxed individual flow constraints
# - lambda duals: multipliers for relaxed individual flow constraints
# - s      source/sink: artificial depot node to start and end rotations
#
# The variables are:
#
# - x      flow
# - y      fleet: depot fleet size
# - z      fleet: total fleet size
# - r      residuals: residuals of relaxed individual flow constraints
#
# ------------------------------------------------------------------------------

param s := 0;

set A := { read "arcs.dat" as "<2n,3n,4n>" comment "#" };
set E := proj(A,<1,2>);
set V := proj(A,<1>) union proj(A,<2>);
set W := V without { s };
set D := proj(A,<3>);
set F := V cross D;

param c[A] := read "arcs.dat" as "<2n,3n,4n> 5n" comment "#";
param lambda[F] := read "flowduals.dat" as "<1n,2n> 3n" comment "#" default 0;

var x[A] integer >= 0 <= 1;
var y[D] integer >= 0;
var z    integer >= 0;
var r[F]         >= -infinity <= infinity;

minimize obj: 
    sum <u,v,d> in A: c[u,v,d]*x[u,v,d] - sum <v,d> in F: lambda[v,d]*r[v,d];

subto flow1:
    forall <v> in V:
	    sum <u,v,d> in A: x[u,v,d] - sum <v,u,d> in A: x[v,u,d] == 0;

subto flow:
    forall <v> in V:
	forall <d> in D:
	    sum <u,v,d> in A: x[u,v,d] - sum <v,u,d> in A: x[v,u,d] == r[v,d];

subto trip:
    forall <v> in W:
        sum <u,v,d> in A: x[u,v,d]  == 1;

subto count:
    forall <d> in D:
        sum <s,v,d> in A: x[s,v,d] == y[d];

subto fleet:
    sum <d> in D: y[d] == z;