# Linear Programming for Integer Solutions

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?

-
In a low-dimensional problem such as this, it can be visualized that for integer $x_1,x_2$ the objective function $z$ having integer coefficients must also be an integer. Try setting a new constraint, parallel to the objective function, that limits $5x_1 + 6x_2$ by the floor of the optimal value in the non-integer case. If this floor can be attained with integer $x_1,x_2$, it is clearly optimal among integer solutions. – hardmath Apr 4 '13 at 14:41

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$.

-