Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
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 at 14:41

1 Answer

up vote 2 down vote

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.