Enrique Brava is responsible for upgrading the wireless network for his employer. He has identified seven possible locations to install new nodes for the network. Each node can provide service to different regions within his employer's corporate campus. The cost of installing each node and the regions that can be served by each node are summarized below.

Node 1: Regions 1, 2, 5; Cost $100

Node 2: Regions 3, 6, 7; Cost $1,100

Node 3: Regions 2, 3, 7, 9; Cost $750

Node 4: Regions 1, 3, 6, 10; Cost $1,150

Node 5: Regions 2, 4, 6, 8; Cost $1,000

Node 6: Regions 4, 5, 8, 10; Cost $500

Node 7: Regions 1, 5, 7, 8, 9; Cost $600

(a)

Formulate an ILP for this problem to minimize cost (in dollars) while providing coverage to every region. (Let X_i = 1 if node i is installed and 0 otherwise.)

MIN:

Subject to:

Region 1-

Region 2-

Region 3-

Region 4-

Region 5-

Region 6-

Region 7-

Region 8-

Region 9-

Region 10-

X_i binary

(b)

Implement your model in a spreadsheet and solve it. What is the optimal solution?

(X₁, X₂, X₃, X₄, X₅, X₆, X₇) =