Consider the following integer nonlinear programming problem.

Maximize Z
4x2 1  x3 1 10x2 2  x4 2, subject to x1 x2 3 and x1  0, x2  0 x1 and x2 are integers.

This problem can be reformulated in two different ways as an equivalent pure BIP problem (with a linear objective function) with six binary variables (y1 j and y2 j for j
1, 2, 3), depending on the interpretation given the binary variables.

(a) Formulate a BIP model for this problem where the binary variables have the interpretation, yij

C

(b) Use the computer to solve the model formulated in part (a), and thereby identify an optimal solution for (x1, x2) for the original problem.

(c) Formulate a BIP model for this problem where the binary variables have the interpretation, yij

C

(d) Use the computer to solve the model formulated in part (c), and thereby identify an optimal solution for (x1, x2) for the original problem.