A city is reviewing the location of its fire stations. The city is made up of a number of neighborhoods, as illustrated in Figure. A fire station can be placed in any neighborhood. It is able to handle the fires for both its neighborhood and any adjacent neighborhood. The objective is to minimize the number of fire stations used.

a. Formulate the problem as a binary-integer programming problem. Specify the complete model including all decision variables and constraints.

b. Specify what neighborhoods should contain a fire station.

c. In addition to part B, give two more feasible solutions to this problem. Which solution is best, justify.

1 2 3 4 6 7 5 8 10 11 12