Consider solving (approximately) the ILP max 12x1 + 7x2 + 9x3 + 8x4 s.t. 3x1 + x2 + x3 + x4 … 3 x3 + x4 … 1 x1,c, x4 = 0 or 1 by a version of discrete improving search Algorithm 15B that always advances to the feasible neighbor with best objective value and uses the single-complement neighborhood permitting any one xj = 1 to be switched to = 0, or vice versa.

(a) Identify a global optimal solution by inspection.

(b) Use Algorithm 15B to compute a local optimum starting from x102 = 10, 0, 0, 02.

(c) Apply the multistart extension of improving search to compute a local optimum by trying starts at x = 10, 1, 0, 02, and (0, 0, 0, 1).