Miroslav Rada, Milan Hladík, and Elif Garajová. Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomially-solvable cases. Optim. Lett., 13(4):875–890, June 2019.
[PDF] [gzipped postscript] [postscript] [HTML]
We address the problem of testing weak optimality of a given solution of a given interval linear program. The problem was recently wrongly stated to be polynomially solvable. We disprove it. We show that the problem is NP-hard in general. We propose a new algorithm for the problem, based on orthant decomposition and solving linear systems. Running time of the algorithm is exponential in the number of equality constraints. In particular, the proposed algorithm runs in polynomial time for interval linear programs with no equality constraints.
@article{RadHla2019a,
author = "Miroslav Rada and Milan Hlad\'{\i}k and Elif Garajov\'{a}",
title = "Testing weak optimality of a given solution in interval linear programming revisited: {NP}-hardness proof, algorithm and some polynomially-solvable cases",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
volume = "13",
number = "4",
month = "June",
pages = "875-890",
year = "2019",
doi = "10.1007/s11590-018-1289-z",
issn = "1862-4480",
url = "http://link.springer.com/article/10.1007/s11590-018-1289-z",
bib2html_dl_html = "https://doi.org/10.1007/s11590-018-1289-z",
bib2html_dl_pdf = "https://rdcu.be/20qn",
abstract = "We address the problem of testing weak optimality of a given solution of a given interval linear program. The problem was recently wrongly stated to be polynomially solvable. We disprove it. We show that the problem is NP-hard in general. We propose a new algorithm for the problem, based on orthant decomposition and solving linear systems. Running time of the algorithm is exponential in the number of equality constraints. In particular, the proposed algorithm runs in polynomial time for interval linear programs with no equality constraints.",
keywords = "Linear programming; Interval analysis; Uncertainty modeling",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44