How about this approach.
Rewrite the linear part of the objective function as $c^Tx = \sum\limits_i c_i x_i = \sum\limits_i c_i^{+}(\frac{x_i+|x_i|}{2}) + c_i^{-}(\frac{x_i-|x_i|}{2})$
Now, firstly you see that you have the superposition of $-|x|$ function that are not convex so the initial problem might be not convex.
Secondly, if all of your $c_i^- \leq 0$ and $c_i^+ \geq 0$ then the function is convex so you can either introduce new variables to handle the modulos or use non-differentiable optimization software to solve this.
Thirdly, you observe that non-convexity happen only if your $c_i^-$ (or +) is greater (less) than 0 and $x_i$ could actually reach the negative (positive) hyperpsace. So, maybe some preprocessing might help to throw away some "bad" coefficients.
In the worst case, as I see, when for example you have an extremely wide polytope, you should check every hyperspace $sign(x_i)=const$ and find a solution there, that is $2^n$ runs which might be too expensive for you.