Constraint Satisfaction for Configuration: Logical Fundamentals,Algorithms, and Complexity

该项目处理配置问题。产品和服务定制化的灵活性和效率--而不是系列化生产--已成为后工业经济中竞争力的关键因素。配置开发是人工智能方法的一个很好的应用领域，特别是在约束满足方面。开发产品配置系统在许多方面都是一项具有挑战性的任务。产品配置工具应该被设计成对来自领域专家的复杂知识进行编码，例如定制所涉及的不同组件的特征以及对这些组件如何相互组合的限制。然而，这可能是非常困难的，因为定制是一个生成性过程，其中涉及的组件的数量和组件本身的类型在一开始可能都是未知的。构建自动配置器的第二个挑战涉及支持定制的算法的效率。事实上，真实场景中的产品配置可能涉及多个组件和数百个关联变量，这些变量的值必须根据客户的需求动态确定。例如，电话交换系统通常由数百个机架、数千个机架和数万个模块组成。考虑到要改进的问题的巨大规模，一个主要要求是集成高效的算法，以构建最符合客户需求的配置，并检查给定的配置是否满足行业的技术要求。为了取得重大进展，我们将首先研究现有的方法，并进行正式比较，并征求工业咨询委员会的反馈。我们建议研究一种适合于应对上述挑战的形式化方法，称为可扩展约束满足问题(ECSP)。我们将研究与这种形式主义相关的决策和计算问题的表现力和复杂性。我们还建议研究在存在价值生成约束的情况下的复杂性问题，这是数据库理论中使用的一种众所周知的约束类型，但到目前为止还没有在CSP的背景下进行研究。一旦部署了可扩展CSP的框架，我们的计划是研究分解技术，找到易处理的ECSP子类。最后，我们将基于我们的框架，使用我们的分解算法，实现并测试一个配置器系统。该项目分为四个主要工作包。WP1通过正式比较文献中的现有方法和接受产业咨询委员会的反馈，系统地研究了与配置相关的问题。WP2主要研究可扩展约束满足问题(ECSP)。将特别注重相关决策和计算问题的复杂性分析。WP3包括对适用于ECSP的分解方法的全面研究，以确定易处理的子类。在WP4中，我们将基于ECSP和WP3中开发的分解方法实现并测试配置系统的概念验证原型。科学项目人员将包括一名博士后和一名博士后。预计这名学生将与博士后密切合作。我们计划在顶级人工智能杂志和领先的国际会议上发表研究结果。

The project deals with configuration problems. Flexibility and efficiency in the customization of products and services --rather than series production-- has become a key factor of competitiveness in the post-industrial economy. Configuration development is an excellent application area for artificial intelligence methods and for constraint satisfaction, in particular.Developing a product configuration system is a challenging task in many ways. Product configuration tools should be designed to encode the complex knowledge from domain experts, such as the characteristics of the different components involved in thecustomization and the restriction on how these components can be combined with each other. However, this might be very difficult in general, because customization is a generative process, where both the number of the involved components and the types of components themselves may be unknown at the beginning.The second challenge in building automatic configurators concerns the efficiency of the algorithms supporting the customization. In fact, product configuration in real scenarios is likely to involve several components and hundreds of associated variables, whosevalues have to be dynamically determined based on the customer's needs. For instance, telephone switching systems often consisting of several hundreds of racks, thousands of frames, and dozens of thousands modules. Given the huge size of the problems to betreated, a major requirement is to integrate efficient algorithms to both building the configuration that best matches with the customer's desires and checking whether a given configuration satisfies the technological requirements from the industry.In order to achieve significant progress, we will first study existing approaches and compare them formally and request feedback from the industrial advisory board. We propose to investigate a formalism suited to the cope with the above mentioned challenges, called the extensible constraint satisfaction problem (ECSP). Wewill study the expressive power and the complexity of decision and computational problems related to this formalism. We also propose to investigate the complexity issues in the presence of value-generating constraints, which is a well-known type ofconstraints used in database theory, but has not been investigated in the context of CSPs so far. Once the framework for extensible CSPs has been layed out, our plan is to investigate decomposition techniques, to find tractable subclasses of ECSPs. Finally, we will implement and test a configurator system, based on our framework,and using our decomposition algorithms. The project is organised into four main work packages. WP1 systematically studies the relevant problems to configuration, both by formally comparing existing approaches in the literature and by receiving feedback from the industrial advisory board. WP2 focuseson the extensible constraint satisfaction problems (ECSPs). Particular focus will be given to complexity analysis of the relevant decision and computational problems. WP3 consists of a comprehensive study of decomposition methods suitable to ECSPs toidentify tractable subclasses. In WP4, we will implement and test a proof-of-concept prototype of configuration system, based on ECSP and on the decomposition methods developed in WP3.The scientific project staff will consist of one post-doc, and one doctoral student. The student is expected to intensively co-operate with the post-doc.We plan to publish the results in top artificial intelligence journals and at leading international conferences.