Consider solving an ILP of the following form by Delayed Column Generation Algorithm 13A.

min aj cj xj s.t. aj ai, j xj Ú bi i = 1,

c, 5 all xj Ú 0 and integer where right-hand sides are given positive integers, bi … 5, coefficients ai, j in any column j are nonnegative integers summing to at most 5, and corresponding cost cjd a 5

i = 1 log 101ai, j + 12.

(a) Specify an initial partial problem using only columns j with a single ai, j  0 that admits a feasible primal solution.

(b) Justify why it is appropriate to solve LP relaxations of each partial prob lem encountered by Algorithm 13A instead of requiring integer values of decision variables prior to overall algorithm termination.

(c) Now suppose a partial problem is at hand with columns j  J, and its LP relaxation is solved to obtain optimal dual solution vQ 1,c, vQ 5. Formulate a INLP column generation subproblem model that seeks an attractive next new column g to enter (if there is one) with coefficients ai, g and cost cg conforming to the rules above.

(d) Explain why a generated column g that qualifies to enter the partial problem cannot already be one of the columns in J.

(e) Explain how subproblem generation in

(c) will also detect when the algorithm should stop because no further columns qualify to enter.