056: Synchronous Optical Networking (SONET) Problem

%
% The SONET problem in MiniZinc.
% 
% Translation of the EssencePrime model in the Minion Translator examples:
% http://www.cs.st-andrews.ac.uk/~andrea/examples/sonet/sonet_problem.eprime
% """
% The SONET problem is a network design problem: set up a network between
% n nodes, where only certain nodes require a connection.
% Nodes are connected by putting them on a ring, where all nodes
% on a ring can communicate. Putting a node on a ring requires a so-called
% ADM, and each ring has a capacity of nodes, i.e. ADMs. There is a certain 
% amount of rings, r, that is available. The objective is to set up a network
% by using a minimal amount of ADMs.
%
%
% About the problem model
%
% The problem model has the amount of rings ('r'), amount of nodes('n'),
% the 'demand' (which nodes require communication) and node-capacity of each 
% ring ('capacity_nodes') as parameters.
% The assignement of nodes to rings is modelled by a 2-dimensional matrix 'rings',
% indexed by the amnount of rings and nodes. The matrix-domain is boolean:
% If the node in column j is assigned to the ring in row i, then rings[i,j] = 1 
% and 0 otherwise. So all the '1's in the matrix 'rings' stand for an ADM.
% Hence the objective is to minimise the sum over all columns and rows of matrix
% 'rings'.
% """
%
% Model created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

%
% The Minion solution is:
% """
% Sol: 0 1 1 0 1
% Sol: 1 0 0 1 0
% Sol: 1 1 0 0 0
% Sol: 0 0 0 0 0
% """
%
% Which is the same solution that fz gives for the minimizing
% objective. The problem has 6 solutions with z = 7.
% 
% z: 7
% 0 1 1 0 1
% 1 0 0 1 0
% 1 1 0 0 0
% 0 0 0 0 0


int: r;  % upper bound for amount of rings
int: n;  % amount of clients


% original comment: 
% we have double entries here because of the symmetric structure!
array[1..n, 1..n] of 0..1: demand;
array[1..r] of 1..n: capacity_nodes;

array[1..r, 1..n] of var 0..1: rings;
var int: z =  sum(ring in 1..r, client in 1..n) (rings[ring, client]);

solve minimize z;
% solve satisfy;


constraint
%   z <= 7 % for solve satisfy
%   /\

   % original comment:
   % if there is a demand between 2 nodes, then there has to exist 
   % a ring, on which they are both installed
   forall(client1,client2 in 1..n where client1 < client2) (
      (demand[client1,client2] = 1) ->
           exists(ring in 1..r) (
                 rings[ring,client1] + rings[ring, client2] >= 2
           )
   )   
   /\
   % original comment:
   % capacity of each ring must not be exceeded     
   forall(ring in 1..r) (
        sum(client in 1..n) (
              rings[ring, client]
              ) <= capacity_nodes[ring] 
   )
;


%
% data
% (sonet_problem1nu.param)
%
r = 4;
n = 5;

demand =
array2d(1..n, 1..n,
        [0,1,0,1,0,
         1,0,1,0,0,
         0,1,0,0,1,
         1,0,0,0,0,
         0,0,1,0,0])
;

capacity_nodes = [3,2,2,1];


output 
[
  "z: ", show(z)
] ++
[
  if client = 1 then "\n" else " " endif ++
    show(rings[ring, client])
  | ring in 1..r, client in 1..n
] ++ ["\n"];