%------------------------------------------------------------------------------%
% min_cost_flow.mzn
% Jakob Puchinger <jakobp@cs.mu.oz.au>
% Wed Jun 14
%------------------------------------------------------------------------------%

%-----------------------------------------------------------------------------%
% Minimum Cost Flow problem.
% One of the most classic OR problems known: Find the minimum cost
% flow in a network, while satisfying the demands in the nodes,
% and not violating the capacities of the arcs.
%
%-----------------------------------------------------------------------------%

    % number of nodes
int: n;

    % number of arcs
int: m;

    % flow demand at every node
array [1..n] of float: demand;

    % arc descriptors
array [1..m, 1..2] of int: arcs;

    % arc variables
array [1..m] of var float: X;

    % costs
array[1..m] of float: costs;

array[1..m] of float: capacity_lb;
array[1..m] of float: capacity;

    % Objective
solve minimize sum([ costs[i] * X[i] | i in 1..m ]);

    % Capacity constraints
constraint
    forall(i in 1..m)(
        X[i] <= capacity[i]
    );
    
    % Capacity LB
constraint
    forall(i in 1..m)(
        X[i] >= capacity_lb[i] 
    );

    % Satisfy demands
constraint
    forall(j in 1..n)
    (
        sum( [ X[i] | i in 1..m where arcs[i,2] = j ] ) - 
        sum( [ X[i] | i in 1..m where arcs[i,1] = j ] ) = demand[j]
    );

var float: opt_costs = sum([ costs[i] * X[i] | i in 1..m ]);
output
    ["Minimum cost flow: "] ++ [show(opt_costs)] ++ ["\n"] ++
    ["Flow on arcs: "] ++ [show(X)] ;