$ The SONET problem
$
$ 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'.

ESSENCE' 1.0

given r : int(1..1000)  $ upper bound for amount of rings
given n : int(1..1000)  $ amount of clients

$ we have double entries here because of the symmetric structure!
given demand : matrix indexed by [int(1..n),int(1..n)] of bool
given capacity_nodes : matrix indexed by [int(1..r)] of int(1..n)

find rings : matrix indexed by [int(1..r),int(1..n)] of bool


minimising sum ring : int(1..r) . 
           sum client : int(1..n) . 
              rings[ring,client]

such that

   $ if there is a demand between 2 nodes, then there has to exist 
   $ a ring, on which they are both installed

   forall client1,client2 : int(1..n) .
      (client1 < client2) => $ we need this to "get rid" of symmetric
                             $ entries in 'demand'
      ((demand[client1,client2] = 1) =>
           exists ring : int(1..r) .
                 rings[ring,client1] + rings[ring, client2] >= 2) ,

  
   $ capacity of each ring must not be exceeded     
   forall ring : int(1..r) .
        (sum client : int(1..n) . 
              rings[ring, client]) <= capacity_nodes[ring]