1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Apr 4, 2013 at 14:41

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.