Consider the following mixed-integer linear program:

Max 2x1 + 3x2

s.t.

4x1 + 9x2 ... 36

7x1 + 5x2 ... 35

x1, x2 0 and x1 integer

a. Graph the constraints for this problem. Indicate on your graph all feasible mixed-

integer solutions.

b. Find the optimal solution to the LP Relaxation. Round the value of x1 down to find a

feasible mixed-integer solution. Is this solution optimal? Why or why not?

c. Find the optimal solution for the mixed-integer linear program.

Grave City is considering the relocation of several police substations to obtain better en-

forcement in high-crime areas. The locations under consideration together with the areas

that can be covered from these locations are given in the following table:

Potential Locations

for Substations Areas Covered

A 1, 5, 7

B 1, 2, 5, 7

C 1, 3, 5

D 2, 4, 5

E 3, 4, 6

F 4, 5, 6

G 1, 5, 6, 7

a. Formulate an integer programming model that could be used to find the minimum

number of locations necessary to provide coverage to all areas.

b. Solve the problem in part (a).