language Essence 1.2.0
$ prob056.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|
forAll pair in demand .
exists ring in network .
pair subsetEq ring