1. **Problem statement:** We have a linear programming (LP) problem (P) and its integer programming (IP) version with integer constraints on $x_1, x_2$. 2. **Part (a):** What can be said about the optimum objective value $w^*$ of (IP) compared to $w_{LP}$ of (P)? - The LP relaxation (P) allows fractional values, so its optimum $w_{LP}$ is an upper bound on the integer problem's optimum $w^*$. - Therefore, $w^* \leq w_{LP}$. - Also, $w^* \geq w_k$ for every subproblem $(P_k)$ in the Branch-and-Bound (BnB) tree because subproblems are relaxations or restrictions. 3. **Part (b):** About the bound $w_B$ in BnB for (IP): - $w_B$ is a lower bound on the optimum objective value for maximization. - $w_B$ cannot be less than $w_{LP}$ because $w_{LP}$ is the best relaxation bound. - $w_B$ can be based on some non-integer solution (from LP relaxation). - $w_B$ cannot decrease during the BnB procedure; it only improves or stays the same. 4. **Part (c):** Given a subproblem with constraint $x_1 \geq 2$ and bound $w_B = \max\{x_1=2, x_2=7/2\} = 17/2$: - Since the bound equals the current best solution, and the subproblem is not integer feasible, we must branch further. - Branching can be done on $x_1$ or $x_2$ to explore integer solutions. 5. **Part (d):** Number of constraints (excluding non-negativity): - Original constraints: $x_2 \leq 2$, $2x_1 + 2x_2 \leq 7$ (2 constraints) - Additional constraint in subproblem: $x_1 \geq 2$ (1 constraint) - Total constraints = 3 **Final answers:** (a) $w^* \leq w_{LP}$ and $w^* \geq w_k$ for every subproblem $(P_k)$. (b) $w_B$ can be based on a non-integer solution and cannot decrease during BnB. (c) Branch on $x_1$ or $x_2$. (d) The subproblem has 3 constraints (excluding non-negativity).