Miroslav Rada, Elif Garajová, Jaroslav Horáček, and Milan Hladík. New pruning tests for the branch-and-prune framework for interval parametric linear systems. Soft Comput., 27(18):12897–12912, September 2023.
[PDF] [gzipped postscript] [postscript] [HTML]
Parametric linear systems with interval coefficients arise in many practical applications in engineering and other related areas. In this paper, we derive a connection between parametric systems and interval linear programming, where interval parametric linear systems can be used to describe the weak optimal solution set. Then, we discuss the branch-and-prune framework for generating an approximation of the weak feasible set of such systems via a union of interval boxes. We propose two new pruning conditions that can be used to test infeasibility of interval boxes within the framework, based on interval linear algebra and on the geometry of zonotopes. Furthermore, we also design a condition for pruning the interval boxes by feasibility, which allows us to generate an inner approximation of the weak feasible set. Computational experiments illustrate competitiveness of the proposed pruning tests in comparison with other available pruning conditions. The experiments indicate that the test based on interval linear algebra usually produces the least number of boxes, while the zonotope-based test is right behind and runs several times faster.
@article{RadGar2023a,
author = "Miroslav Rada and Elif Garajov\'{a} and Jaroslav Hor\'{a}{\v{c}}ek and Milan Hlad\'{\i}k",
title = "New pruning tests for the branch-and-prune framework for interval parametric linear systems",
journal = "Soft Comput.",
fjournal = "Soft Computing",
volume = "27",
number = "18",
month = "September",
pages = "12897-12912",
year = "2023",
doi = "10.1007/s00500-022-06971-7",
issn = "1432-7643",
issnonline = "1433-7479",
url = "https://doi.org/10.1007/s00500-022-06971-7",
bib2html_dl_html = "https://link.springer.com/article/10.1007/s00500-022-06971-7",
bib2html_dl_pdf = "https://rdcu.be/djz1N",
abstract = "Parametric linear systems with interval coefficients arise in many practical applications in engineering and other related areas. In this paper, we derive a connection between parametric systems and interval linear programming, where interval parametric linear systems can be used to describe the weak optimal solution set. Then, we discuss the branch-and-prune framework for generating an approximation of the weak feasible set of such systems via a union of interval boxes. We propose two new pruning conditions that can be used to test infeasibility of interval boxes within the framework, based on interval linear algebra and on the geometry of zonotopes. Furthermore, we also design a condition for pruning the interval boxes by feasibility, which allows us to generate an inner approximation of the weak feasible set. Computational experiments illustrate competitiveness of the proposed pruning tests in comparison with other available pruning conditions. The experiments indicate that the test based on interval linear algebra usually produces the least number of boxes, while the zonotope-based test is right behind and runs several times faster.",
keywords = "Interval parametric linear systems; Interval linear programming; Branch-and-prune; Zonotope",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42