056: Synchronous Optical Networking (SONET) Problem

language Essence 1.2.0
$ prob129.essence: SONET Configuration
$
$ A SONET communication network comprises a number of rings, each joining a
$ a number of nodes. A node is installed on a ring using an add-drop multiplexer
$ (ADM) and there is a capacity bound on the number of ADMs that can be
$ installed on a ring. Each node can be installed on more than one ring.
$ Communication can be routed between a pair of nodes only if both are installed
$ on a common ring. Given the capacity bound and a specification of which pairs
$ of nodes must communicate, allocate a set of nodes to each ring so that the
$ given communication demands are met. The objective is to minimise the number
$ of ADMs used. (This is a common simplification of the full SONET problem.)
$
$ 03 September 2007
$

given nnodes, nrings, capacity : int(1..)

letting Nodes be domain int(1..nnodes)

given demand : set of set (size 2) of Nodes

find network : mset (size nrings) of set (maxSize capacity) of Nodes

minimising sum ring in network . |ring|

such that 

forAll pair in demand . 
    exists ring in network . 
        pair subsetEq ring