Absolute value optimization

Question

If you have an LP

Maximize/Minimize:

$c_1|x_1| + c_2|x_2| ... c_n|x_n|$

Subject to:

$Ax = b$

Can this be solved in polynomial time with respect to the amount of data used to represent the problem?

Answer 1

For minimizing you can translate this to a standard linear program.

minimize $\sum_i c_i y_i$ s.t. $Ax=b$, $y_i \ge x_i$, and $y_i \ge -x_i$. $y_i = |x_i|$ in any optimal solution. This is solvable in polynomial time, but not by the simplex method, although that is likely the fastest method.

For maximizing absolute value you have a NP hard problem. Consider the number partitioning problem. If the values to be partitioned are $w_i$. The optimization problem maximize $\sum_i |x_i|$ subject to $\sum_i w_i x_i = 0$, $x_i \le 1$, and $x_i \ge -1$ will have an optimal value of $|I|$ if and only there is a partitioning of the $w_i$ into two equal subsets.