How to minimize the sum of absolute values

Question

How can I solve a problem such as the following:

$$ \text{minimize}~~~ \sum_{i=1}^n |x_i| \\ \text{subject to}~~~ A x \geq b $$ ? Without the absolute values on the variables, it is a simple linear program. Is it possible to convert the verstion with absolute values into a standard linear program?

_{Note: this question How to minimize an absolute value in the objective of an LP? looks similar, but it is different.}

Answer 1

You can use the same approach as in the linked question, but with a separate variable for each summand. Explicitly, minimize $\sum_i z_i$ subject to \begin{align} Ax&\ge b\\ z_i&\ge x_i &&\text{for all $i$}\\ z_i&\ge -x_i &&\text{for all $i$} \end{align}