% % 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"];