(Shortest Paths and Branch-and-Bound) Consider a general integer-constrained problem of the form

where X is some set. Construct a branch-and-bound tree that starts with a subproblem where the integer constraints are relaxed, and proceeds with successive restriction of the variables x1,...,xn to the values 0 or 1.

(a) Show that the original integer-constrained problem is equivalent to a single origin/single destination shortest path problem that involves the branchand-bound tree.

(b) Modify the label correcting method of Section 2.5.2 so that it becomes similar to the branch-and-bound method (see also the discussion in Section 2.5.2)