Consider the following BIP problem.

Maximize Z 2x1 3x2 x3 4x4 3x5 2x6 2x7 x8 3x9, subject to 3x2 x4 x5  3 x1 x2  1 x2 x4  x5  x6  1 x2 2x6 3x7 x8 2x9  4

x3 2x5 x6 2x7  2x8 x9  5 and all xj binary.

Develop the tightest possible formulation of this problem by using the techniques of automatic problem reprocessing (fixing variables, deleting redundant constraints, and tightening constraints). Then use this tightened formulation to determine an optimal solution by inspection.