Elif Garajová and Milan Hladík. Checking weak optimality and strong boundedness in interval linear programming. Soft Comput., 23(9):2937–2945, 2019.
[PDF] [gzipped postscript] [postscript] [HTML]
Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.
@article{GarHla2019b,
author = "Elif Garajov\'{a} and Milan Hlad\'{\i}k",
title = "Checking weak optimality and strong boundedness in interval linear programming",
journal = "Soft Comput.",
fjournal = "Soft Computing",
volume = "23",
number = "9",
pages = "2937-2945",
year = "2019",
doi = "10.1007/s00500-018-3520-3",
issn = "1432-7643",
issnonline = "1433-7479",
url = "https://doi.org/10.1007/s00500-018-3520-3",
bib2html_dl_html = "https://link.springer.com/article/10.1007%2Fs00500-018-3520-3",
bib2html_dl_pdf = "https://rdcu.be/cno0j",
abstract = "Interval programming provides a mathematical tool for dealing with uncertainty in optimization problems. In this paper, we study two properties of interval linear programs: weak optimality and strong boundedness. The former property refers to the existence of a scenario possessing an optimal solution, or the problem of deciding non-emptiness of the optimal set. We investigate the problem from a complexity-theoretic point of view and prove that checking weak optimality is NP-hard for all types of programs, even if the variables are restricted to a single orthant. The property of strong boundedness implies that each feasible scenario of the program has a bounded objective function. It is co-NP-hard to decide for inequality-constrained interval linear programs. For this class of programs, we derive a sufficient and necessary condition for testing strong boundedness using the orthant decomposition method. We also discuss the open problem of checking strong boundedness of programs described by equations with nonnegative variables.",
keywords = "Interval linear programming; Weak optimality; Strong boundedness; Computational complexity",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44