8 Suppose we have branched on a subproblem (call it subproblem 0, having optimal solution SOL0) and have obtained the following two subproblems:

Subproblem 1 Subproblem 0  Constraint x1  i.

Subproblem 2 Subproblem 0  Constraint x1  i  1 (i is some integer).

Prove that there will exist at least one optimal solution to subproblem 1 having x1  i and at least one optimal solution to subproblem 2 having x1  i  1. [Hint: Suppose an optimal solution to subproblem 1 (call it SOL1) has x1 

x1, where x1 i. For some number c ( 0 c

1), c(SOL0)

 (1  c)SOL1 will have the following three properties:

a The value of x1 in c(SOL0)  (1  c)SOL1 will equal i.

b c(SOL0)  (1  c)SOL1 will be feasible in subproblem 1.

c The z-value for c(SOL0)  (1  c)SOL1 will be at least as good as the z-value for SOL1.

Explain how this result can help when we graphically solve branch-and-bound problems.]