Students often mistakenly believe ILPs are more tractable than LPs because the straightforward rules of Algorithm 12A seem less complex than the simplex and interior point methods of Chapters 5–7.

(a) Explain why solution of any ILP by LPbased branch and bound always takes at least as much work as a linear program of comparable size and coefficients.

(b) Justify the number of LP relaxations that might have to be solved in branch-andbound enumeration of an ILP with n binary variables is 21n + 12 - 1.

(c) Use part

(b) to compute the number of linear programs that could have to be solved in branch and bound search of ILP models with 100, 300, and 500 binary variables respectively, and determine how long each such search could take at the rate of one LP per second.

(d) How practical is it be to solve LPs of 100, 300, and 500 variables in reasonable amounts of time?

(e) Comment on the implications of your analysis in parts

(a) to

(d) for tractability of LPs versus ILPs of comparable size.