The Town of Simplexville is considering installing automatic

The Town of Simplexville is considering installing automatic traffic monitoring devices in its downtown area. The following map shows the 6 intersections (represented by circles) at which automatic traffic monitoring devices might be installed. A traffic monitoring device at any particular intersection can monitor all the roads meeting that intersection. For example, a device installed at intersection 5 can monitor roads d, e, g and h. The cost of installing and operating an automatic traffic monitoring device at each intersection is given below. The town wants to install devices at intersections so that all roads (a through h) are monitored. In addition, due to the design of the town\'s electric grid, there are some additional constraints on where the devices can be installed: If a device is installed at intersection 1, a device must be installed at intersection 4. If a device is installed at intersection 2, a device cannot be installed at either intersection 1 or intersection 3. Formulate an integer linear program that determines where to install devices in a way that minimizes the total installation and operating costs. (You do not need to solve it with software.)

Solution

There are clearly two optimal solutions as of the cost of installation is considered; either to choose the intersection 2 or not.

If we formulate with considering clause 1, we\'ll be having the minimal installations at intersections 1,3,4 and 5. Which results in an expense of 225. But if we choose to go with 2nd clause and optimizing withintersection 4 instead, the possible nodes will be 2,4,5 and 6; giving a lower installation cost of 214.

Answer should be for the intersections 2,4,5 and 6.