Answer Happy

1. A certain state allows a restricted form of branch banking; specifically, a bank can do business in county i if the bank has a "principal place of business" in county i or in a county sharing a nonzero-length border with county i. The figure below is a map of the state in question. F A K B E G D H I J We consider two approaches to formulating the problem of locating a minimum number of principal places of business so that a bank can do business in every county in the state. (a) Set Covering The set covering problem is defined as follows: There is a ground set of objects and a collection of (pre- determined) subsets of those objects. Each subset comes with a cost for using it. The objective is to select subsets so that every ground set item appears in at least one of the selected subsets, and the subsets are selected to minimize the total cost. The integer programming formulation includes a 0-1 vari- able x; for each subset S;. There is a constraint for each elementi in the ground set so that x ≥ 1 for all i € S. j:iES, The objective is to minimize Σct; j We can formulate the bank's problem as a set covering problem as follows: . The ground set is the set of counties. • There is a subset for each county i consisting of the counties that the bank can do business in if they locate in county i. • The objective is simply to minimize the number of locations selected.