Milan Hladík and David Hartman. Absolute value linear programming. J. Glob. Optim., 93(4):1097–1120, December 2025.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@article{HlaHar2025a,
author = "Milan Hlad\'{\i}k and David Hartman",
title = "Absolute value linear programming",
journal = "J. Glob. Optim.",
fjournal = "Journal of Global Optimization",
volume = "93",
number = "4",
pages = "1097-1120",
month = " December",
year = "2025",
doi = "10.1007/s10898-025-01569-3",
issn = "1573-2916",
url = "https://link.springer.com/article/10.1007/s10898-025-01569-3",
bib2html_dl_html = "https://doi.org/10.1007/s10898-025-01569-3",
bib2html_dl_pdf = "https://rdcu.be/eVis9",
abstract = "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.",
keywords = "Linear programming; Nonsmooth optimization; Interval analysis; NP-hardness",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Dec 22, 2025 15:50:44