34 The Smalltown Fire Department currently has seven conventional ladder companies and seven alarm boxes. The two closest ladder companies to each alarm box are given in Table 33. The city fathers want to maximize the number of conventional ladder companies that can be replaced with tower ladder companies. Unfortunately, political considerations dictate that a conventional company can be replaced only if, after replacement, at least one of the two closest companies to each alarm box is still a conventional company.

a Formulate an IP that can be used to maximize the number of conventional companies that can be replaced by tower companies.

b Suppose yk  1 if conventional company k is replaced.

Show that if we let zk  1  yk, the answer in part

(a) is equivalent to a set-covering problem.