Open constraint programming
Open constraint programming
复制标题
开放约束规划
DOI：
10.1016/j.artint.2004.10.005
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Santiago Macho
中科院分区：
文献类型：
--
作者：
B. Faltings;Santiago Macho
传统上，约束满足问题（CSP）假设封闭世界的情况下，所有的领域和约束是固定的从一开始。随着互联网的发展，许多传统的CSP应用程序在资源分配，调度和规划提出自己在开放世界的设置，域和约束必须从网络中的不同来源发现。为了模拟这种情况下，我们定义开放约束满足问题（OCSP）的CSP域和约束是通过网络逐渐发现。然后，我们扩展的概念，开放约束优化（OCOP）。在不完全了解变域的情况下，我们可以求解OCSP问题，并给出了完善的算法。我们表明，OCOP需要额外的假设，变量域和关系的偏好非递减顺序显示。我们提出了各种算法求解OCOP的可能性和加权模型。我们通过随机生成的问题的实验比较算法。我们表明，在某些情况下，开放约束编程可以需要显着更少的信息比传统的方法，收集信息和解决CSP是分开的。这导致网络流量和服务器负载的减少，并在分布式问题解决中提高了隐私性。
Traditionally, constraint satisfaction problems (CSP) have assumed closed-world scenarios where all domains and constraints are fixed from the beginning. With the Internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where domains and constraints must be discovered from different sources in a network. To model this scenario, we define open constraint satisfaction problems (OCSP) as CSP where domains and constraints are incrementally discovered through a network. We then extend the concept to open constraint optimization (OCOP). OCSP can be solved without complete knowledge of the variable domains, and we give sound and complete algorithms. We show that OCOP require the additional assumption that variable domains and relations are revealed in non-decreasing order of preference. We present a variety of algorithms for solving OCOP in the possibilistic and weighted model. We compare the algorithms through experiments on randomly generated problems. We show that in certain cases, open constraint programming can require significantly less information than traditional methods where gathering information and solving the CSP are separated. This leads to a reduction in network traffic and server load, and improves privacy in distributed problem solving.