Interval-Based Projection Method for Under-Constrained Numerical Systems
Interval-Based Projection Method for Under-Constrained Numerical Systems
复制标题
欠约束数值系统的基于区间的投影方法
DOI：
10.1007/s10601-012-9126-y
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Christophe Jermann
中科院分区：
文献类型：
--
作者：
石井大輔;Alexandre Goldsztejn;Christophe Jermann
本文提出了一种基于区间的方法，遵循的分支和修剪计划，计算一个验证铺路的投影的解集的欠约束系统。该算法的优点包括随时求解过程，内盒的齐次验证，以及对一般问题的适用性，允许任何数量的（可能是非线性的）等式和不等式约束。我们提出了三个关键的改进算法致力于投影问题：（i）验证过程得到增强，以证明更快的投影空间中的大盒子。(ii)通过删除解决方案集中可能相同投影的冗余部分，可以节省计算工作量。(iii)专用分支策略允许减少处理的框的数量。实验结果表明，各种应用程序可以建模为投影问题，并可以有效地解决所提出的方法。
This paper presents an interval-based method that follows the branch-and-prune scheme to compute a verified paving of a projection of the solution set of an under-constrained system. Benefits of this algorithm include anytime solving process, homogeneous verification of inner boxes, and applicability to generic problems, allowing any number of (possibly nonlinear) equality and inequality constraints. We present three key improvements of the algorithm dedicated to projection problems: (i) The verification process is enhanced in order to prove faster larger boxes in the projection space. (ii) Computational effort is saved by pruning redundant portions of the solution set that would project identically. (iii) A dedicated branching strategy allows reducing the number of treated boxes. Experimental results indicate that various applications can be modeled as projection problems and can be solved efficiently by the proposed method.