Scheduling Sport Tournaments using Constraint Logic Programming

We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is an assignment problem and it is solved using a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language \eclipse. Experimental results show that, in practical cases, the optimal solution of the assignment problem (which is not necessarily optimal for the overall problem) can be found in reasonable time, despite the fact that the problem is NP-complete. In addition, a local search procedure has been developed in order to provide, when necessary, an approximate solution in shorter time.     

Constraint Programming in Sweden

The authors survey the research and development in Sweden in constraint programming, which is rapidly becoming the method of choice for some kinds of constraint problems, such as scheduling and configuration.     

Stochastic Concurrent Constraint Programming

We present a stochastic version of Concurrent Constraint Programming (CCP), where we associate a rate to each basic instruction that interacts with the constraint store. We give an operational semantic that can be provided either with a discrete or a continuous model of time. The notion of observables is discussed, both for the discrete and the continuous version, and a connection between the two is given. Finally, a possible application for modeling biological networks is presented.     

Some Challenges for Constraint Programming

We propose a number of challenges for future constraint programming systems, including improvements in implementation technology (using global analysis based optimization and parallelism), debugging facilities, and the extension of the application domain to distributed, global programming. We also briefly discuss how we are exploring techniques to meet these challenges in the context of the development of the CIAO constraint logic programming system.     

基于代数格的软约束程序设计框架

1引言 约束程序设计(Constraint Programming,CP)是一种新兴的软件技术,具体应用时,分为约束建模和约束求解两个阶段.实践已经证明95%以上的实际约束问题都是有限论域上的约束满足问题(Constraint Satisfaction Problems,CSP),因而CSP问题建模技术和相关的求解方法已经成为CP中的核心技术,同时CSP也是人工智能领域最为成功的技术之一,在处理配置、调度、规划等实际问题显示出强大的能力[1,2].     

Constraint Programming in Structural Bioinformatics

Bioinformatics aims at applying computer science methods to the wealth of data collected in a variety of experiments in life sciences (e.g. cell and molecular biology, biochemistry, medicine, etc.) in order to help analysing such data and eliciting new knowledge from it. In addition to string processing bioinformatics is often identified with machine learning used for mining the large banks of bio-data available in electronic format, namely in a number of web servers. Nevertheless, there are opportunities of applying other computational techniques in some bioinformatics applications. In this paper, we report the application of constraint programming to address two structural bioinformatics problems, protein structure prediction and protein interaction (docking). The efficient application of constraint programming requires innovative modelling of these problems, as well as the development of advanced propagation techniques (e.g. global reasoning and propagation), which were adopted in Chemera, a system that is currently used to support biochemists in their research.     

约束归纳逻辑程序设计系统

提出了一种新的约束归纳逻辑程序设计方法，并初步实现了一个自顶向下的约束归纳逻辑程序原型系统。该系统能够导出不受变量个数限制的多种形式的线性约束，得出覆盖正例而排斥负例的含约束的Hom子句程序。     

SC-PROLOG解释系统中的约束逻辑程序设计方法

约束逻辑程序设计（ＣＬＰ）方法是提高ＰＲＯＬＯＧ语言效率的一种崭新方法，本文针对ＳＣ┐ＰＲＯＬＯＧ解释系统的实现介绍其相应设计思想，从域变量含义入手，提出了域及约束的存储方法以及约束机制的实现算法，是对逻辑设计方法研究的一点体会     

Using Constraint Programming in Selection Operators for Constraint Databases

Constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and constraint data representation.     

约束编程与约束满足在产品装配中的应用

约束编程与约束满足问题是近三十年来在人工智能领域发展起来的一个研究方向。产品配置器近十几年来发展起来的一项技术。文中介绍约束编程及约束满足问题在按订单装配型产品配置器中的应用，并通过讨论说明了相对于传统配置方案求解过程，应用约束满足的优越性。     

Incremental search in Constraint Logic Programming

Incremental search consists of adding new constraints or deleting old ones once a solution to a search problem has been found. Although incremental search is of primary importance in application areas such as scheduling, planning, trouble shooting, and interactive problem-solving, it is not presently supported by logic programming languages and little research has been devoted to this topic. This paper presents a scheme to deal efficiently with incremental search problems. The scheme allows the incremental addition and deletion of constraints and is based on re-execution, using parts of computation paths stored during previous computations. The scheme has been implemented as part of the constraint logic programming language CHIP and applied to practical problems. It has shown arbitrarily large (i.e. unbounded) speedups compared with previous approaches on practical problems.     

一种可扩展型CLP系统的统一建模方法

约束推理是人工智能中主要组成部分之一,可以解决实际优化调度和规划过程中的约束求解问题。这里在解释了约束逻辑程序设计的原理和过程基础上,打破封闭式约束逻辑程序设计系统,从软件工程上采用统一建模语言,提出一种新的开放的可扩展型约束逻辑程序设计结构系统。为实现可扩展的约束推理搜索系统,引进UML建模语言中用例图、类图和协作图。在建模基础上详细说明了可扩展约束逻辑程序设计中数学模型,搜索引擎和搜索驱动三者间的关系以及它们内部的工作内容。最后在描述系统结构后,提出了可扩展的内容。根据扩展因素,外界为满足更多的需要可扩展本系统的约束过滤器。     

分布式并行约束归纳逻辑程序设计研究

CILP是关系数据挖掘的主要技术之一。为提高CILP系统的效率,提出了一种基于C3模型,元学习技术和主从式静态负载平衡策略的分布式并行CILP算法,并实现了一个基于COW机群结构的分布式并行CILP原型系统。实验表明该算法是高效的,能获得较好的负载平衡,较高的加速比和并行效率。     

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

约束逻辑程序设计综述

一、引言 约束逻辑程序设计(Constraint Logic Program-ming．CLP)是基于人工智能(AI)中约束满足问题(Constraint Satisfaction Problem．CSP)模型的一种程序设计风范。CLP是逻辑程序设计(LP)的一种推广,是八十年代发展起来的一种新的逻辑程序设计方法。由于它继承了LP简单易懂的说明性描述方法并结合了CSP在求解问题时的效率,使它在解决很多AI问题(如组合问题、资源分配、事务安排等)时有不凡的表现。更由于AI领域中绝大多数问题可以用CLP来表示,所以这一方法已引起了人们的广泛注意,并在八十年代后期得以迅速发展。     

Fast Theta-Subsumption with Constraint Satisfaction Algorithms

Relational learning and Inductive Logic Programming (ILP) commonly use as covering test the -subsumption test defined by Plotkin. Based on a reformulation of -subsumption as a binary constraint satisfaction problem, this paper describes a novel -subsumption algorithm named Django,¹ which combines well-known CSP procedures and -subsumption-specific data structures. Django is validated using the stochastic complexity framework developed in CSPs, and imported in ILP by Giordana et Saitta. Principled and extensive experiments within this framework show that Django improves on earlier -subsumption algorithms by several orders of magnitude, and that different procedures are better at different regions of the stochastic complexity landscape. These experiments allow for building a control layer over Django, termed Meta-Django, which determines the best procedures to use depending on the order parameters of the -subsumption problem instance. The performance gains and good scalability of Django and Meta-Django are finally demonstrated on a real-world ILP task (emulating the search for frequent clauses in the mutagenesis domain) though the smaller size of the problems results in smaller gain factors (ranging from 2.5 to 30).