Approximation Techniques for Non-linear Problems with Continuum of Solutions
Approximation Techniques for Non-linear Problems with Continuum of Solutions
复制标题
具有连续解的非线性问题的逼近技术
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Silaghi
中科院分区：
文献类型：
--
作者：
Xuan;Djamila Sam;M. Silaghi
大多数数值约束满足问题（NCSP）的工作求解器被设计为提供具有任意精度的逐点解。当存在可行点的连续体时，这可能导致输出的表示过于冗长。在许多实际应用中，这样大的解决方案集表示需要尽可能完整地识别的同等相关的替代方案。本文的目标是表明，通过使用适当的近似技术，明确表示的解决方案集，保持准确性和完整性，仍然可以提出NCSP连续的解决方案。我们提出了一种技术，用于构建简洁的内部和外部近似作为工会的区间盒。所提出的技术结合了一种新的分裂策略与计算几何中定义的正交多面体的极端顶点表示[1，2，3]。这允许压缩近似的表示并提高效率。
Most of the working solvers for numerical constraint satisfaction problems (NCSPs) are designed to delivering point-wise solutions with an arbitrary accuracy. When there is a continuum of feasible points this might lead to prohibitively verbose representations of the output. In many practical applications, such large sets of solutions express equally relevant alternatives which need to be identified as completely as possible. The goal of this paper is to show that by using appropriate approximation techniques, explicit representations of the solution sets, preserving both accuracy and completeness, can still be proposed for NCSPs with continuum of solutions. We present a technique for constructing concise inner and outer approximations as unions of interval boxes. The proposed technique combines a new splitting strategy with the extreme vertex representation of orthogonal polyhedra [1,2,3], as defined in computational geometry. This allows for compacting the representation of the approximations and improves efficiency.