Emergency relief agency ERNow is planning flights of small helicopters to deliver medical, food, and housing supplies for populations cutoff by a recent hurricane. The following table shows the fraction of each plane’s weight wi and volume vi capacity of shipping containers for different materials to be sent, along with the number that must be transported.

i Material Weight Fraction wi Volume Fraction vi Quantity Needed qi 1 First aid supplies 0.04 0.10 30 2 Drinking water 0.20 0.14 20 3 Diesel Generators 0.40 0.24 12 4 Generator fuel 0.28 0.32 23 5 Tents 0.10 0.28 15 6 Cots 0.16 0.24 30 7 Blankets 0.03 0.18 40 8 Rain capes 0.08 0.14 25 ERNow wants to meet all these needs with the minimum number of flights.

(a) Formulate ERNow’s challenge as an ILP over decision variables xj ! the number of times load combination j is used, with columns for load combinations made up of ai, j ! the number of containers of material i carried in each load j.

(b) Discuss how the large number of feasible load mixes make Delayed Column Generation Algorithm 13A attractive for this application.

(c) Show that the weight and volume constraints column coefficients ai, j are required to satisfy in terms of parameters wi and vi.

(d) Construct an initial set of columns j for a first partial problem as ones for “pure”

loads with ai, j = 0 except on one product i where the maximum feasible number of that product is specified.

(e) Justify why it is appropriate to solve LP relaxations of each partial problem encountered instead of requiring integer values of decision variables prior to algorithm termination.

(f) Suppose now that the LP relaxation of a partial problem is solved as the algorithm proceeds and yields optimal dual values wQ i on product rows i. Use those results to formulate a column generation subproblem to find a feasible new load mix g with coefficients ag, i having a reduced cost in the LP relaxation of the current partial problem that makes it attractive to enter.

(g) What outcome from solving your generation subproblems of

(f) would justify terminating Algorithm 13A? Explain.

(h) Use class optimization software to solve the LP relaxation of the partial problem of (d). Then solve the resulting column generation subproblem

(f) by inspection and continue Algorithm 13A until 5 new columns have been added, or the termination condition of (g) is met.

(i) Round up to derive an approximate integer optimal solution from the final results of part (h).