Prepare the following exercise for discussion in class on Monday 12th March 2012.
This problem arises in data communication networks. The SONET (Synchronous Optical NETwork ) ANSI standard describes multiplexed, reliable communication networks with a ring topology. The problem is stated in terms of a number of client nodes and given demands (describing numbers and channels) between pairs of distinct nodes. The ability to add and drop channels (nodes) from an already multiplexed carrier is built into the standard. Each node is installed on a sonet ring using a device called âadd-drop multiplexerâ (ADM) which manages the integration of the nodeâs traffic into the multiplexed channels. Nodes can be installed on multiple rings (thus splitting the given demands). However, in order for two nodes to communicate, both must be installed on the same ring: no inter-ring traffic is allowed â traffic is only routed between nodes that are on the same ring. Capacity constraints are given for the rings in terms of nodes and channels. For the purpose of this problem, the cost of rings is negligible, so that there is no practical limit on the rings used. The objective of the problem is to minimise the number of required ADM devices. In a simplified variant, ring capacity is uniformly stated in terms of maximal number of nodes, the number of available rings is given, and the demand between any two nodes is either 1 or 0 (on or off).
Model the problem as a MIP problem and as a CP problem.