<p>We study linear programming problems involving absolute values in their formulations, which are therefore no longer expressible as standard linear programs. The presence of absolute values makes the problems nonconvex and nonsmooth, and thus hard to solve. In this paper, we study fundamental properties of 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. We show that the feasible set is a (nonconvex) polyhedral set and, more importantly, every nonconvex polyhedral set can be described using absolute value constraints. We also provide a necessary and sufficient condition when a Karush–Kuhn–Tucker (KKT) point of a nonconvex quadratic programming reformulation solves the original problem.</p>