Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer.
How would one manipulate the resources so that the existing optimal solution remains feasible yet $x_1$ becomes an integer? For those familiar I was considering using the Gomery cutting plane method, but am not sure how to be certain the result is the new optimal solution. Further, this is part of a series of questions that then ask me to use a cutting plane that targets $x_1$ and makes it into an integer. Why would these give different solutions?
Best Answer
A basic branch-and-bound approach works quickly for this problem. The solution to the LP relaxation is $(x_1,x_2)=(3.4,6)$ with an objective value of $z=53$. This is a upper bound for the problem, since enforcing integrality makes the feasible region smaller thus can only make the solution worse.
You then need to "branch" on variable $x_1$ and solve two more LPs, in particular (1) and (2):
(1) The LP relaxation, with the additional constraint: $x_1 \leq 3$
(2) The LP relaxation, with the additional constraint: $x_1 \geq 4$
The solution to (1) is $(x_1,x_2)=(3,6)$ with an objective value of $z=51$.
The solution to (2) is $(x_1,x_2)=(4,10/3)$ with an objective value of $z=40$.
The solution to (1) is now a lower bound for the problem since it is feasible to the original problem. Note that continuing to branch on (2) can only produce solutions worse than $z=40$, so this "node" can be fathomed, and the optimal solution is $(x_1,x_2)=(3,6)$ with an objective value of $z=51$.