Milan Hladík. On approximation of the best case optimal value in interval linear programming. Optim. Lett., 8(7):1985–1997, 2014.
[PDF] [gzipped postscript] [postscript] [HTML]
Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.
Page 1993: missing variable $v$ in the system of linear equations in the middle of the page. More importantly, one also needs to check that the remaining dual inequalities are satisfied for $(\mathbf{u},\mathbf{v})$.
@article{Hla2014d,
author = "Milan Hlad\'{\i}k",
title = "On approximation of the best case optimal value in interval linear programming",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
volume = "8",
number = "7",
pages = "1985-1997",
year = "2014",
doi = "10.1007/s11590-013-0715-5",
issn = "1862-4472",
url = "https://doi.org/10.1007/s11590-013-0715-5",
bib2html_dl_html = "https://link.springer.com/article/10.1007%2Fs11590-013-0715-5",
bib2html_dl_pdf = "https://rdcu.be/cnoXg",
bib2html_errata = "Page 1993: missing variable $v$ in the system of linear equations in the middle of the page. More importantly, one also needs to check that the remaining dual inequalities are satisfied for $(\mathbf{u},\mathbf{v})$.",
abstract = "Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.",
keywords = "Linear programming; Interval linear systems; Interval analysis",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44