3
$\begingroup$

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.

$\endgroup$

1 Answer 1

9
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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