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.
Best Answer
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''.