Milan Hladík. Interval linear programming: A survey. In Zoltán Ádám Mann, editor, Linear Programming -- New Frontiers in Theory and Applications, pp. 85–120, Nova Science Publishers, New York, 2012.
Uncertainty is a common phenomenon in practice. Due to measurement errors we can hardly expect precise values in real-life linear programming problems. Using estimated quantities may lead to unsatisfactory results, so inexactness must be taken into account. Uncertainty can be handled in various manners, e.g. by stochastic programming, interval analysis or fuzzy numbers; each of them has some pros and cons. In this paper, we suppose that we are given lower and upper bounds on the quantities, and the quantities may perturb independently and simultaneously within these bounds. In this model we investigate the problems of optimal value range, basis stability, optimal solutions enclosures, duality etc. Complexity issues are discussed, too; some tasks are polynomially solvable while another are NP-hard. This approach is more general and powerful than the standard sensitivity analysis. In sensitivity analysis, we consider variations of only one parameter, which is very restrictive. On the other hand, interval analysis based approach enables to handle simultaneously all required parameters. We present a brief exposition of the known results with new insights, and close the survey by some challenging problems.
Some of the HP-hard problems mentioned in Table 1 are co-NP-hard instead; particularly strong feasibility, strong unboundedness and strong optimality. Interval subtraction is defined with the wrong sign. Theorem 11 is wrong, even in the original paper. Reference [94] should be entitled ``Development of a Fuzzy-Queue-Based Interval Linear Programming Model for Municipal Solid Waste Management''
@inCollection{Hla2012a,
author = "Milan Hlad\'{\i}k",
title = "{Interval linear programming: A survey}",
editor ="Mann, Zolt\'{a}n \'{A}d\'{a}m",
booktitle = "Linear Programming -- New Frontiers in Theory and Applications",
publisher = "Nova Science Publishers",
address = "New York",
isbn = "978-1-61209-579-0",
chapter = "2",
pages = "85-120",
year = "2012",
bib2html_dl_html = "https://www.novapublishers.com/catalog/product_info.php?products_id=21789",
abstract = "Uncertainty is a common phenomenon in practice. Due to measurement errors we can hardly expect precise values in real-life linear programming problems. Using estimated quantities may lead to unsatisfactory results, so inexactness must be taken into account. Uncertainty can be handled in various manners, e.g. by stochastic programming, interval analysis or fuzzy numbers; each of them has some pros and cons. In this paper, we suppose that we are given lower and upper bounds on the quantities, and the quantities may perturb independently and simultaneously within these bounds. In this model we investigate the problems of optimal value range, basis stability, optimal solutions enclosures, duality etc. Complexity issues are discussed, too; some tasks are polynomially solvable while another are NP-hard.
This approach is more general and powerful than the standard sensitivity analysis. In sensitivity analysis, we consider variations of only one parameter, which is very restrictive. On the other hand, interval analysis based approach enables to handle simultaneously all required parameters. We present a brief exposition of the known results with new insights, and close the survey by some challenging problems.",
bib2html_errata = "Some of the HP-hard problems mentioned in Table 1 are co-NP-hard instead; particularly strong feasibility, strong unboundedness and strong optimality.
Interval subtraction is defined with the wrong sign.
Theorem 11 is wrong, even in the original paper.
Reference [94] should be entitled ``Development of a Fuzzy-Queue-Based Interval Linear Programming Model for Municipal Solid Waste Management''",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42