# Question

Reconsider Prob. 12.4-7. The management of Sunny Skies Unlimited now has decided that the decision on the locations of the fire stations should be based mainly on costs.

The cost of locating a fire station in a tract is $200,000 for tract 1, $250,000 for tract 2, $400,000 for tract 3, $300,000 for tract 4, and $500,000 for tract 5. Management’s objective now is the following:

Determine which tracts should receive a station to minimize the total cost of stations while ensuring that each tract has at least one station close enough to respond to a fire in no more than 15 minutes (on the average).

In contrast to the original problem, note that the total number of fire stations is no longer fixed. Furthermore, if a tract without a station has more than one station within 15 minutes, it is no longer necessary to assign this tract to just one of these stations.

(a) Formulate a complete pure BIP model with 5 binary variables for this problem.

(b) Is this a set covering problem? Explain, and identify the relevant sets.

(c) Use the computer to solve the model formulated in part (a).

The cost of locating a fire station in a tract is $200,000 for tract 1, $250,000 for tract 2, $400,000 for tract 3, $300,000 for tract 4, and $500,000 for tract 5. Management’s objective now is the following:

Determine which tracts should receive a station to minimize the total cost of stations while ensuring that each tract has at least one station close enough to respond to a fire in no more than 15 minutes (on the average).

In contrast to the original problem, note that the total number of fire stations is no longer fixed. Furthermore, if a tract without a station has more than one station within 15 minutes, it is no longer necessary to assign this tract to just one of these stations.

(a) Formulate a complete pure BIP model with 5 binary variables for this problem.

(b) Is this a set covering problem? Explain, and identify the relevant sets.

(c) Use the computer to solve the model formulated in part (a).

## Answer to relevant Questions

Suppose that a state sends R persons to the U.S. House of Representatives. There are D counties in the state (D > R), and the state legislature wants to group these counties into R distinct electoral districts, each of which ...Follow the instructions of Prob. 12.5-2 for the following BIP problem: Maximize Z = –5x1 + 25x2, Subject to and x1, x2 are binary. Consider the following statements about any pure IP problem (in maximization form) and its LP relaxation. Label each of the statements as True or False, and then justify your answer: (a) The feasible region for the LP ...Follow the instructions of Prob. 12.7-2 for the following IP model: Minimize Z = 2x1 + 3x2, Subject to And x1 ≥ 0, x2 ≥ 0 x1, x2 are integer. (a) Solve this problem graphically. (b) Use the MIP branch-and-bound algorithm ...For each of the following constraints of pure BIP problems, use the constraint to fix as many variables as possible: (a) 20x1 – 7x2 + 5x3 ≤ 10 (b) 10x1 – 7x2 + 5x3 ≥ 10 (c) 10x1 – 7x2 + 5x3 ≤ –1Post your question

0