Milan Hladík. Range of optimal values in absolute value linear programming with interval data. Int. J. Approx. Reason., 197:109750:1–16, October 2026.
[PDF] [gzipped postscript] [postscript] [HTML]
Absolute value linear programming (AVLP) problems are a relatively recent class of optimization problems involving linear functions and absolute values in the model formulation. In this paper, we consider interval uncertainty in the input data and study the corresponding range of optimal values. Our goal is to determine the best- and worst-case optimal values. For the best-case optimal value, we derive an explicit characterization that reduces its computation to one specific AVLP problem. In contrast, the worst-case optimal value is more challenging; we therefore propose lower and upper bounding approaches to estimate it. We also investigate the concept of basis stability, under which the best-case optimal value becomes efficiently computable. In this setting, the worst-case optimal value admits a simplified characterization as well, although its computational complexity remains an open question.
@article{Hla2026c,
author = "Milan Hlad\'{\i}k",
title = "Range of optimal values in absolute value linear programming with interval data",
journal = "Int. J. Approx. Reason.",
fjournal = "International Journal of Approximate Reasoning",
volume = "197",
pages = "109750:1-16",
month = "October",
year = "2026",
doi = "10.1016/j.ijar.2026.109750",
issn = "0888-613X",
url = "https://www.sciencedirect.com/science/article/abs/pii/S0888613X26001258",
bib2html_dl_html = "https://doi.org/10.1016/j.ijar.2026.109750",
bib2html_dl_pdf = "https://doi.org/10.1016/j.ijar.2026.109750",
abstract = "Absolute value linear programming (AVLP) problems are a relatively recent class of optimization problems involving linear functions and absolute values in the model formulation. In this paper, we consider interval uncertainty in the input data and study the corresponding range of optimal values. Our goal is to determine the best- and worst-case optimal values. For the best-case optimal value, we derive an explicit characterization that reduces its computation to one specific AVLP problem. In contrast, the worst-case optimal value is more challenging; we therefore propose lower and upper bounding approaches to estimate it. We also investigate the concept of basis stability, under which the best-case optimal value becomes efficiently computable. In this setting, the worst-case optimal value admits a simplified characterization as well, although its computational complexity remains an open question.",
keywords = "Linear programming; Interval analysis; Absolute value; Robustness; NP-hardness; Lower and upper bound",
}
Generated by bib2html.pl (written by Patrick Riley ) on Thu Jul 02, 2026 12:34:40