In most applications, LP based Branch and Bound Algorithm 12A actually investigates only a tiny fraction of
Question:
In most applications, LP based Branch and Bound Algorithm 12A actually investigates only a tiny fraction of the possible partial solutions.
Still, this is not always the case. Consider the family of ILPs of the form min y s.t. 2a n
j = 1 xj + y = n xj = 0 or 1 j = 1,c, n y = 0 or 1 where n is odd.
(a) Enter and solve versions for n = 7, n = 11, and n = 15 with class branch and bound software, and record the number of branch and bound nodes explored. (Warning:
Program limits must be set big enough to allow up to 20,000 branch and bound nodes.)
(b) Express your results in part
(a) as fractions as the total number of nodes that might have to be investigated. [Hint: Use the formula in Exercise 12-27(b).]
(c) Comment on the implications for tractability of ILP’s via branch and bound if fractions like those of part
(b) were typical.
Step by Step Answer:
