# Maximizing linear objective function with absolute values

This has be asked on other forums, though couldn't find authoritative answer.

I have a linear program over the reals and don't want to introduce integer or binary variables.

The objective function is $\text{maximize} \sum |x_i|$ (maximizing sum of absolute values of variables).

Is is possible to model this as a standard linear program (without integer variables and extensions like disjunctions).

What I know. Minimizing sum of absolute values is possible.

This blog suggests several solutions. The solution with SOS2 method appears to work sometimes in glpk and coin-or, though sometimes it doesn't work.

The lpsolve documentation suggests using a binary variable.

If this is impossible, there might be reduction from a NP-hard problem.

• What do the constraints look like? If you have a typical polyhedral feasible region, then maximizing the sum of absolute values is in general nonconvex, hence not a linear program (which are convex). – martin Feb 12 '14 at 12:12

In general such a problem is NP-hard, so not expressible by a polynomially-sized linear program. A special case of the problem you mention is computing the $\lVert A\rVert_{\infty,1}$ norm of a matrix, i.e. the maximum of $\lVert Ax\rVert_1$ over all $x$ with $\lVert x\rVert_\infty\leq 1$. Rohn has shown that this matrix norm is NP-hard to approximate in the paper Computing the norm $\Vert A\rVert_{\infty,1}$ is NP-hard''.