this question is from Ronald L. Rardin - Optimization in Operations Research second editon chapter 13 exercises.

1. (30 points) Emergency relief agency ERNow is planning flights of small helicopters to deliver medical, food, and housing supplies for populations cut off by a recent hurricane. The following table shows the fraction of each plane's weight wand volume capacity of shipping containers for different materials to be sent, along with the number that must be transported. Weicht Fraction Volume Fraction Quantity Needed 0.04 010 0.20 0.14 20 i Material First aid supplies 2 Drinking water 3 Diesel Generators 4 Generator fuel 5 Tents 6 Cots 7 Blankets & Raincapes 028 123 232 0.28 23 0.10 0.16 005 0.18 009 0.14 ERNow wants to meet these needs with the minimum number of flights. (a) Formulate ERNow's challenge as an ILP over decision variables x, which is the number of times load combination is used, with columns for load combinations made up of which is the number of containers of material i carried in each load). (b) Discuss how the large number of feasible load mixes makes Column Generation Algorithm attractive for this application. (e) Show that the weight and volume constraints column coefficients are required to satisfy in terms of parameters Wi and vi. (d) Construct an initial set of columns for a first restricted master problem as ones for "pure" loads with a = 0 except on one product i where the minimum 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 (1) Suppose now that the LP relaxation of a restricted master problem is solved as the algorithm proceeds and yields optimal dual values on product rows. Use those results to formulate a column generation subproblem (pricing problem) to find a feasible new load mix g with coefficients having a reduced cost in the LP relation of the current partial problem that makes it attractive to enter. (g) What outcome from your pricing problem would justify the termination of the column generation algorithm? 1. (30 points) Emergency relief agency ERNow is planning flights of small helicopters to deliver medical, food, and housing supplies for populations cut off by a recent hurricane. The following table shows the fraction of each plane's weight wand volume capacity of shipping containers for different materials to be sent, along with the number that must be transported. Weicht Fraction Volume Fraction Quantity Needed 0.04 010 0.20 0.14 20 i Material First aid supplies 2 Drinking water 3 Diesel Generators 4 Generator fuel 5 Tents 6 Cots 7 Blankets & Raincapes 028 123 232 0.28 23 0.10 0.16 005 0.18 009 0.14 ERNow wants to meet these needs with the minimum number of flights. (a) Formulate ERNow's challenge as an ILP over decision variables x, which is the number of times load combination is used, with columns for load combinations made up of which is the number of containers of material i carried in each load). (b) Discuss how the large number of feasible load mixes makes Column Generation Algorithm attractive for this application. (e) Show that the weight and volume constraints column coefficients are required to satisfy in terms of parameters Wi and vi. (d) Construct an initial set of columns for a first restricted master problem as ones for "pure" loads with a = 0 except on one product i where the minimum 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 (1) Suppose now that the LP relaxation of a restricted master problem is solved as the algorithm proceeds and yields optimal dual values on product rows. Use those results to formulate a column generation subproblem (pricing problem) to find a feasible new load mix g with coefficients having a reduced cost in the LP relation of the current partial problem that makes it attractive to enter. (g) What outcome from your pricing problem would justify the termination of the column generation algorithm