Explore BrainMass

Zero-One Programming Problem: Example

Problem 11-17

Horizon Wireless, a cellular telephone company, is expanding into a new era. Relay towers are necessary to provide wireless telephone coverage to the different areas of the city. A grid is superimposed on a map of the city to help determine where the towers should be located. The grid consists of 8 areas labeled A through H. Six possible tower locations (numbered 1-6) have been identified, and each location could serve several areas. The table below indicates the areas served by each of the towers.

Tower Location 1 2 3 4 5 6
Areas Served A, B, D B, C, G C, D, E, F E, F, H E, G, H A, D, F

Formulate this as a 0-1 programming model to minimize the total number of towers required to cover all the areas. Solve this using a computer.

(Hint: OF = Min X1 + X2 + . . ., one constraint would equal: X1 + X6 => 1 (do you see why?)

Solution Summary

This is an example for 0-1 programming problem. The problem is mathematically formulated and solved by using solver of M S Excel.