Elif Garajová, Milan Hladík, and Miroslav Rada. On the properties of interval linear programs with a fixed coefficient matrix. In Antonio Sforza and Claudio Sterle, editors, Optimization and Decision Science: Methodologies and Applications, Springer Proceedings in Mathematics & Statistics, pp. 393–401, Springer, Cham, 2017.
[PDF] [gzipped postscript] [postscript] [HTML]
Interval programming is a modern tool for dealing with uncertainty in practical optimization problems. In this paper, we consider a special class of interval linear programs with interval coefficients occurring only in the objective function and the right-hand-side vector, i.e. programs with a fixed (real) coefficient matrix. The main focus of the paper is on the complexity-theoretic properties of interval linear programs. We study the problems of testing weak and strong feasibility, unboundedness and optimality of an interval linear program with a fixed coefficient matrix. While some of these hard decision problems become solvable in polynomial time, many remain (co-)NP-hard even in this special case. Namely, we prove that testing strong feasibility, unboundedness and optimality remains co-NP-hard for programs described by equations with non-negative variables, while all of the weak properties are easy to decide. For inequality-constrained programs, the (co-)NP-hardness results hold for the problems of testing weak unboundedness and strong optimality. However, if we also require all variables of the inequality-constrained program to be non-negative, all of the discussed problems are easy to decide.
@inCollection{GarHla2017b,
author = "Elif Garajov\'{a} and Milan Hlad\'{\i}k and Miroslav Rada",
title = "On the properties of interval linear programs with a fixed coefficient matrix",
editor = "Sforza, Antonio and Sterle, Claudio",
booktitle = "Optimization and Decision Science: {Methodologies} and Applications",
fbooktitle = "Optimization and Decision Science: Methodologies and Applications: ODS, Sorrento, Italy, September 4-7, 2017",
publisher = "Springer",
address = "Cham",
series = "Springer Proceedings in Mathematics \& Statistics",
volume = "217",
pages = "393-401",
year = "2017",
doi = "10.1007/978-3-319-67308-0_40",
isbn = "978-3-319-67308-0",
issn = "2194-1017",
url = "https://link.springer.com/chapter/10.1007/978-3-319-67308-0_40",
bib2html_dl_html = "https://doi.org/10.1007/978-3-319-67308-0_40",
abstract = "Interval programming is a modern tool for dealing with uncertainty in practical optimization problems. In this paper, we consider a special class of interval linear programs with interval coefficients occurring only in the objective function and the right-hand-side vector, i.e. programs with a fixed (real) coefficient matrix. The main focus of the paper is on the complexity-theoretic properties of interval linear programs. We study the problems of testing weak and strong feasibility, unboundedness and optimality of an interval linear program with a fixed coefficient matrix. While some of these hard decision problems become solvable in polynomial time, many remain (co-)NP-hard even in this special case. Namely, we prove that testing strong feasibility, unboundedness and optimality remains co-NP-hard for programs described by equations with non-negative variables, while all of the weak properties are easy to decide. For inequality-constrained programs, the (co-)NP-hardness results hold for the problems of testing weak unboundedness and strong optimality. However, if we also require all variables of the inequality-constrained program to be non-negative, all of the discussed problems are easy to decide.",
keywords = "Interval linear programming; Computational complexity",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44