2
$\begingroup$

This is really a basic (undergrad) question in LP but still i would like to clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$. I've seen that the standard way to convert it to LP is to represent $x_i$ as the difference of two non negative variables. We question is, can i also handle it like so : add a new variable t : $|x_i|=t_i$ and get $$\min \sum_i t_i \\ Ax \le b \\ -t_i \le x_i \le t_i $$ Thanks.

$\endgroup$
  • $\begingroup$ Looks fine to me. $\endgroup$ – Austin Buchanan Jul 8 '13 at 14:52
2
$\begingroup$

Your formulation ensures that $|x_i|=t_i$ in every optimal solution. However, this does not hold for an arbitrary feasible point.

Picky people could then complain that your formulation isn't entirely correct. However, as long as you don't change your objective function nor use $t_i$ in any other constraint, then you will be fine in practice.

This blog post describes several ways to model absolute values.

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