Consider the following problem:

max 2x + y

s.t. 4x + y  less than or equal to 8

2x + y  greater than or equal to 3

x + 4y  less than or equal to 8

x; y E Z

Bounds, Relaxations, Graphical solution method:

(a) Is the problem convex? 

(b) Is the solution (x, y) = (1, 4) feasible?

(c) Is the solution (x, y) = (1, 1) feasible?

(d) Is the solution (x; y) = (1:5; 0:5) feasible?

(e) What is the value of the objective function that corresponds to each of the previous three solutions?

(f) Does each of these three values correspond to a lower bound, upper bounds, none, or both (Note, the problem is a maximization problem!)?

(g) Eliminate the last constraint (integrality of x and y) for a relaxation of the original problem. Is the new relaxation problem convex?

(h) Are the solutions above feasible for the relaxation?

(i) Are the three objective function values lower bounds, upper bounds, none, or both, for the relaxation?

(j) Solve the relaxation by the graphical method.

(k) What does the optimal value of the relaxation give you in terms of the original (non-covex) problem (with integrality constraints)?