4
$\begingroup$

Suppose I have an objective function in my LP as follows

$max$ $|x|$

Based on some googling, I have found there are two ways to convert this into a standard LP.

Method 1.

$|x|$ = $ x^+ + x^-$

$x = x^+ - x^-$

$max$ $x^+ - x^-$

subject to

$x^+, x^- > 0$

Method 2 Since $|x| = max(x,-x)$, we introduce a new variable $t$ and rewrite the problem as

$max$ $t$

subject to

$t >= x$

My main question is are these 2 methods equivalent? Is one of them preferred over the other? $t >= -x$

$\endgroup$
1
$\begingroup$

If your objective function was a minimization problem, then the two methods would work and are equivalent. For instance, consider a problem where $x=-2$. Then, using method 2 for a minimization problem, you would have

$\begin{equation} \text{min }t\\ t \geq 2\\ t \geq -2\\ \end{equation} $

and the solution is 2. Now try it with a max - the solution will be unbounded above.

However, you have a maximization problem. Note that $|x|$ is a convex function. There is no LP reformulation of this problem.

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