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](http://orinanobworld.blogspot.fr/2012/07/modeling-absolute-values.html) 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.



Maximizing linear objective function with absolute values
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''](http://uivtx.cs.cas.cz/~rohn/publist/norm.pdf).


