0
$\begingroup$

$$\begin{array}{ll} \text{maximize} & \dfrac{2x_1 - 2x_2 - 2}{x_1 + 3x_2 + 4}\\ \text{subject to} & -x_1 + x_2 \leq 4\\ & 2x_1 + x_2 \leq 14\\ & x_2 \leq 6\\ & x_1 \geq 0\\ & x_2 \geq 0\end{array}$$

I want to obtain a linear problem by introducing new variables. Then it will be possible to solve it. Unfortunately, I have no idea how to introduce these variables.

$\endgroup$
  • $\begingroup$ Can you please give the source of this problem? Thanks! $\endgroup$ – Matthew Conroy Nov 18 '17 at 3:30
  • $\begingroup$ There exists $\color{blue}{\texttt{no optimal solution}}$. For any valid value of $x_1$ a greater value of $x_1$ is always valid, which makes the value of the objective function larger. $\endgroup$ – callculus Nov 18 '17 at 16:02
  • $\begingroup$ In general it is a good idea to look at a (mathematical) problem carefully before thinking of an algorithm. $\endgroup$ – callculus Nov 18 '17 at 16:11
  • 1
    $\begingroup$ @callculus lets pretend we treat everything except $x_1$ to be constant, the quotient will then stagnate at 2 as the limit $\displaystyle\lim_{x_1\to \infty}\frac{2x_1+c_1}{x_1+c_2} = 2$, which clearly does not grow unbounded. $\endgroup$ – mathreadler Nov 19 '17 at 7:37
  • $\begingroup$ @mathreadler But don´t we need $x_1 \in \mathbb R$ for an optimal solution ? $\endgroup$ – callculus Nov 19 '17 at 10:41
0
$\begingroup$

In general, when we have

$min z=\frac{px+a}{qx+d}$

s.t. $Ax<=b $ , $x>=0$

We changed problem by $z=\frac{1}{qx+d}$ and $y=zx$

Then the original problem changed to:

$ min z= py+az$

s.t.$Ay<=bz$

$qy+dz=1$

$y>=0$

$z>=0$

$\endgroup$
0
$\begingroup$

You can introduce new variables together with equations: $$\cases{x_3 = \phantom{2}x_1+3x_2+4\\x_4 = 2x_1-2x_2-2}$$and you will get:

$$\min\left\{\frac{x_4}{x_3}\right\}$$

which will be achieved (by monotonicity of the $\log$ family of functions), when:

$$\min\{\log(x_4)-\log(x_3)\}$$

Which indeed is linear in the new variables $\cases{x_6=\log(x_4)\\x_5=\log(x_3)}$ : $\min\{1\cdot x_6 - 1\cdot x_5\}$

Now what remains is to find a way to represent the logarithmic function linearly of some suitable representation of $x_3,x_4$ and to linearly fuse all the variables and the constraints. That is a separate (but even more important) problem! Especially if we want to be able to linearize more advanced non-linear functions in the future.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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