Bounds, Relaxations, Graphical solution method: 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

(a) Is the problem convex? Justify your answer.

(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)?