How to bring $\sum_{i=1}^n \lvert x_i \rvert$ with $Ax=b$ in canonical form

Question

I am working on the following exercise:

Bring the LP $$\min \sum_{i=1}^n \lvert x_i \rvert \text{ with } Ax=b$$ in canonical form $$\min \sum_{i=1}^n c_i x_i \text{ with } Ax=b, x \ge 0.$$

My attempt thus far goes as follows: To get rid of the absolute values in the objective function we introduce the variables $u_i$ with $-x_i \le u_i \le x_i$ and obtain:

$$\min \sum_{i=1}^n u_i \text{ with } Ax=b, -x_i \le u_i \le x_i$$

To solve the exercise I woul now only need to get rid of $Ax=b$ somehow and get the additional constraint $u_i \ge 0$, but I do not see how. Could you help me?

Answer 1

Your $u_i\le x_i$ should instead be $\ge$, and $u_i\ge 0$ follows from summing the two new inequalities.

A simpler approach might be to use the “other” linearization of absolute value. Explicitly, introduce nonnegative variables $x_i^+$ and $x_i^-$, replace $|x_i|$ in the objective with $x_i^+ + x_i^-$, and replace $x_i$ in the constraints with $x_i^+ - x_i^-$.