  We deal with linear programming problems involving absolute values in their
formulations, so that they are no more expressible as standard linear programs.
The presence of absolute values causes the problems to be nonconvex and
nonsmooth, so hard to solve. In this paper, we study fundamental properties on
the topology and the geometric shape of the solution set, and also conditions
for convexity, connectedness, boundedness and integrality of the vertices.
Further, we address various complexity issues, showing that many basic
questions are NP-hard to solve. We show that the feasible set is a (nonconvex)
polyhedral set and, more importantly, every nonconvex polyhedral set can be
described by means of absolute value constraints. We also provide a necessary
and sufficient condition when a KKT point of a nonconvex quadratic programming
reformulation solves the original problem.
