New pruning tests for the branch-and-prune framework for interval parametric linear systems
New pruning tests for the branch-and-prune framework for interval parametric linear systems
复制标题
区间参数线性系统分支剪枝框架的新剪枝测试
DOI：
10.1007/s00500-022-06971-7
复制
发表时间：
2022
期刊：
影响因子：
4.1
通讯作者：
M. Hladík
中科院分区：
文献类型：
--
作者：
M. Rada;E. Garajová;J. Horáček;M. Hladík
区间系数参数线性系统在工程和其他相关领域的许多实际应用中出现。本文导出了参数系统与区间线性规划之间的一种联系，其中区间参数线性系统可以用来描述弱最优解集。然后，我们讨论了分支和修剪框架，通过区间盒的工会产生的弱可行集的近似这样的系统。我们提出了两个新的修剪条件，可用于测试不可行的间隔框的框架内，基于区间线性代数和几何zonotopes。此外，我们还设计了一个条件，修剪区间盒的可行性，这使得我们能够产生一个内部近似的弱可行集。计算实验表明，与其他可用的剪枝条件相比，所提出的剪枝测试的竞争力。实验表明，基于区间线性代数的测试通常产生最少数量的框，而基于带状拓扑的测试紧随其后，运行速度快了好几倍。
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.