Air National Guard planners are loading a cargo plane with crates of supplies and equipment needed to help victims of the recent wave of floods in the Northeast. The table below shows the criticality of the need for each crate, its weight

(in tons), and its volume (in hundreds of cubic feet). The plane’s capacity limits are 38 tons and 26 hundred cubic feet of cargo.

Crate j  1 2 3 4 5 6 7 8 Criticality 9 3 22 19 21 14 16 23 Weight 5 11 15 12 20 7 10 18 Volume 7 4 13 9 4 18 9 6

(a) Formulate the problem of choosing the maximum total criticality combination of crates to put on the plane as a pure 0-1 ILP over two main constraints and decision variables xj = 1 if crate j is selected and = 0 otherwise. Be sure to annotate the objective and each constraint to indicate their meaning.

(b) Derive one minimum cover inequality from each of the two main constraints of your model in (a). Demonstrate that each meets the requirements of definition 12.48 for such constraints, and explain why both must be valid for the full model of (a).

(c) Suppose now that we are solving your model of

(a) by Branch and Cut Algorithm 12B, and the first LP-relaxation solution is x = 10.5, 0, 0, 1, 0, 0, 1, 0.752. Which, if either of your cuts in

(b) could the algorithm add productively as the next step? Explain.