Consider the following mixed-integer linear program: Max 2 x1 + 3 x2 s.t. 4 x1 + 9 x2 ? 36 7 x1 + 5 x2 ? 35 x1, x2 ?

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.