0

I am currently studying for an exam in optimization, and in one of the questions the following was mentioned:

"The linear relaxation of the problem $(P)$:

$z^*=\max 4x_1+11x_2+7x_3+13x_4+15x_5+17x_6$

when $x_1+3x_2+2x_3+4x_4+5x_5+6x_6 \leq 9$

and $x_i\in \lbrace0,1\rbrace$, $i=1,...,6$."

I assume here that I should make the relaxation so that $x_i\in[0,1]$, $i=1,...,6$, but my issue with this was when I looked in the answer sheet. There it just says, with no explanation as to what method they used to obtain it, that the optimal solution to the linear relaxation is $x^*=(1,1,1,3/4,0,0)$.

Is there a simple way to arrive at this conclusion from the given relaxation, without using something like the simplex method?

When I tried simplex, I noticed that I would have to add six more conditions $x_i\leq 1$, $i=1,...,6$ to the original problem, and the workload to arrive at the optimal solution seems unreasonable for a question worth 1 point total (a standard question is worth 3 points, with a similar workload to solving that thing with simplex).

Or have I made a mistake in assuming that I need to add the conditions $x_i\leq 1$, $i=1,...,6$?

I am at a loss for the moment, as there are no similar examples to this in my textbook or my lecture notes.

Scounged
  • 937

1 Answers1

0

I now know how they managed to find the solution to the linear relaxation, and here's how:

This linear relaxation will be a bit special, as all the terms in the condition are positive, and that there is only one condition. So we can use the following line of reasoning:

Begin by setting all variables to zero.

We look for which $x_i$ is the most efficient in the sense that the ratio between increase in objective function and space taken up by the variable in the condition is as high as possible. Thus, at first we get that we should take as much as possible of $x_1$, as

$\max\lbrace \frac{4}{1}, \frac{11}{3}, \frac{7}{2}, \frac{13}{4}, \frac{15}{5}, \frac{17}{6} \rbrace=\frac{4}{1},$ which corresponds to the ratio for $x_1$. We see that we can set $x_1=1$ without breaking our condition. Now we modify the problem (as we know the best value of $x_1$) to

$z*=\max 4+11x_2+7x_3+13x_4+15x_5+17x_6$

s.t. $3x_2+2x_3+4x_4+5x_5+6x_6\leq 8$, $x_i\in [0,1]$, $i=1,2,...,6$.

Now, $\max\lbrace \frac{11}{3}, \frac{7}{2}, \frac{13}{4}, \frac{15}{5}, \frac{17}{6} \rbrace=\frac{11}{3},$ so we take $x_2$, and we see that we can set $x_2=1$ without breaking the given condition.

We continue in the same manner as previously, discover that we should take $x_3$ next, and that we can set it equal to 1 without breaking our condition.

In the next step, we have that $x_4$ is the best variable to choose, but we can at most set $x_4=3/4$ without breaking our condition. After that, we cannot increase either $x_5$ or $x_6$ without breaking our given condtion. And by then we have solved the linear relaxation.

Scounged
  • 937