Let be the following integer-linear program.

: min 15x₁ + 12₂

subject to:

4₁ + 2₂ 5

2₁ + 4₂ 8

2₁ 3₂ 4

₁ + ₂ 10

₁ 0, integer

₂ 0, integer

Solve using the Branch-and-Bound algorithm: solve graphically the LP-relaxation of each

subproblem encountered in the enumeration tree (make sure your figures are clear). Branch

on the fractional variable with fractional value (non-integer part) closest to . Among the

unexplored nodes in the enumeration tree, select that with most promising bound (best

bound first search). For each subproblem, highlight the feasible region in the figures. Report

your algorithmic decisions clearly. Give the optimal solution and the optimal value of the

objective function. Show all work.