Optimization-Oriented Global Constraints

In this paper, we propose a way of exploiting Operations Research techniques within global constraints for cost-based domain filtering. In Constraint Programming, constraint propagation is aimed at removing from variable domains combinations of values which are proven infeasible. Pruning derives from feasibility reasoning. When coping with optimization problems, pruning can be performed also on the basis of costs, i.e., optimality reasoning. Cost-based filtering removes combination of values which are proven sub-optimal. For this purpose, we encapsulate in global constraints optimization components representing suitable relaxations of the constraint itself. These components embed efficient Operations Research algorithms computing the optimal solution of the relaxed problem and a gradient function representing the estimated cost of each variable-value assignment. We exploit these pieces of information for pruning and for guiding the search. We have applied these techniques to a couple of ILOG Solver global constraints (a constraint of difference and a path constraint) and tested the approach on a variety of combinatorial optimization problems such as Timetabling, Travelling Salesman Problems and Scheduling Problems with sequence dependent setup times. Comparisons with pure Constraint Programming approaches and related literature clearly show the benefits of the proposed approach.     

Cost-Based Arc Consistency for Global Cardinality Constraints

A global cardinality constraint (gcc) is specified in terms of a set of variables X={x ₁,...,x _p} which take their values in a subset of V={v ₁,...,v _d}. It constrains the number of times each value v _iV is assigned to a variable in X to be in an interval [l _i,u _i]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm.     

Mixed Global Constraints and Inference in Hybrid CLP–IP Solvers

The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through these constraints. Together with new search strategies for hybrid solvers and cut-generating mixed global constraints, solution speed is improved over both traditional IP codes and newer mixed solvers.     

Value Constraints in the CLP Scheme

We define value constraints, a method for incorporating constraint propagation into logic programming. It is a subscheme of the CLP scheme and is applicable wherever one has an efficient method for representing sets of possible values. As examples we present: small finite sets, sets of ground instances of a term, and intervals of reals with floating-point numbers as bounds. Value constraints are defined by distinguishing two storage management strategies in the CLP scheme. In value constraints the infer step of the CLP scheme is implemented by Waltz filtering. We give a semantics for value constraints in terms of set algebra that gives algebraic characterizations of local and global consistency. The existing extremal fixpoint characterization of chaotic iteration is shown to be applicable to prove convergence of Waltz filtering.     

装配位置约束建模及求解

以基本几何约束组合统一表达装配约束,为提高求解效率,研究了姿态约束和位置约束的可解耦情况下位置约束的解析求解.将基本位置约束映射为移动空间并以参数方程表达,通过移动空间的增量解析求交,满足约束;在姿态约束和位置约束的不可解耦情况,联立基本约束进行整体数值法求解.文中方法保持了基本约束表达的独立性,适合于欠约束系统和完整约束系统.     

三维服装CAD中几何约束表达及其求解技术研究

从人体及服装的特点出发,提出三维服装几何元素的概念．采用样条曲线作为基本几何元素,归纳出服装的三种约束关系,即共点、对称和自对称关系;成为约束关系形成的基础．以三种约束关系为基础,建立了面向服装的几何约束图,有效地表达了三维服装几何元素及其相互关系;实现了一种基于约束图的约束求解方法。从而完成了构造服装及对服装的交互参数化修改,文中给出了应用实例,并将参数化方法向高层次图素如样条曲线、曲面作了推广,成功地应用于以样条曲线为几何元素的参数化服装CAD系统中,运行效果良好。     

一类闭环约束的装配约束问题求解

分析了一种可以拆分为等价的开环约束的装配闭环约束问题.给出了等价性的定义,并提出一种该类闭环约束拆分为等价开环约束的方法.首先确定装配几何约束图上的闭环,然后对该闭环利用自由度归约加扰动判定是否从某一条边拆开.该方法能够较好的简化CAD软件中用户添加的装配约束,避免了因闭环约束造成的求解复杂度增加的情况,同时可以更好的表达实际装配的过程.     

一种求解混合约束问题的快速完备算法

布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了数值与区间分析相结合进行数值约束求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效、快速、完备地求解非线性混合约束问题.     

Complete Bound Consistency for the Global Cardinality Constraint

We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n′) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n′ is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.Partially supported by DFG grant SA 933/1-1.Partially supported by the EU IST Programme, IST-1999-14186 (ALCOM-FT).     

一种约束求解的两级规划方法

提出了一个基于图构造的几何约束求解方法。基于自由度分析的理论,把整个约束图分解为多个约束子图,各个约束子图之间的共享结点形成一个全局的共享结点集,当共享结点集中的结点确定下来时,相关的约束子图中的结点也相应被确定下来。通过这样的全局到局部的两级求解规划的构造,缩小了约束问题的规模,提高了求解效率。     

三维几何约束求解的自由度归约算法

三维几何约束求解在装配设计、几何造型和动力学分析等领域有着广泛的应用．在分析基本几何元素间的约束关系对刚体自由度状态影响的基础上,提出刚体自由度的归约算法,以求得满足约束后刚体的自由度状态空间;以刚体自由度状态空间分析为基础,实现对合理约束的推理求解和约束一致性维护,该算法解决了三维几何约束求解中自由度计算问题,同时避免了一些推理求解算法中出现的“组合爆炸”问题．     

Solving Various Weighted Matching Problems with Constraints

This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint ( WeightedMatching), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CP is shown not to be competitive with specialized polynomial algorithms for pure matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the Traveling Salesman Problems [5], which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a WeightedMatching constraint. This is an extension to the weighted case of the work of Régin [19], which we show to bring significant improvements on a timetabling example.     

求解布尔与非线性数值约束相混合的约束问题

布尔与数值变量相混合的约束问题有着广泛的应用,但是当约束中的数值变量间存在非线性关系时该问题求解起来十分困难.目前的许多求解方法都是不完备的,即这些方法不能完全肯定某些包含非线性数值表达式的约束是否能够成立.针对这种问题,提出了将非线性数值约束转化为特殊形式的优化问题,采用全局优化算法对其进行求解的方法.已经实现了一个基于此方法的原型工具.实验结果表明,该方法能够有效地求解非线性混合约束问题,并且总能够得到该约束条件是否可满足的结果.     

基于优先表的工程约束求解算法研究

文章分析了工程设计中约束问题的特点和规律,阐明了工程约束与几何约束在工程CAD领域中的表现形式,提出了符合工程特点的“多元约束图”的约束表示模型和约束传播层的设计思想．为了有效地结合设计领域的特点,文章还提出了具有工程特性的“基于优先表的改进算法”．基于此思想,多种启发式的工程经验可以被加入其中,使处理速度大为提高．该研究已应用于工厂钢结构的系统设计中,取得了良好的效果．     

Multiconsistency and Robustness with Global Constraints

We propose a natural generalization of arc-consistency, which we call multiconsistency: a value v in the domain of a variable x is k-multiconsistent with respect to a constraint C if there are at least k solutions to C in which x is assigned the value v. We present algorithms that determine which variable-value pairs are k-multiconsistent with respect to several well known global constraints. In addition, we show that finding super solutions is sometimes strictly harder than finding arbitrary solutions for these constraints and suggest multiconsistency as an alternative way to search for robust solutions.Supported by the Danish Research Agency (grant # 272-05-0081).Basic Research in Computer Science, funded by the Danish National Research Foundation.     

User studies of knowledge acquisition tools: methodology and lessons learned

Knowledge acquisition research concerned with the development of knowledge acquisition tools is in need of a methodological approach to evaluation. This paper describes experimental methodology to conduct studies and experiments of users modifying knowledge bases with knowledge acquisition tools. The paper also reports on the lessons learned from several experiments that have been performed using this methodology. The hope is that it will help others design user evaluations of knowledge acquisition tools. Ideas are discussed for improving the current methodology and some open issues that remain.     

非二元约束满足问题求解

在约束满足问题(CSP)的研究中，大部分工作集中在二元约束，但处理实际问题时，常常会遇到非二元约束的情况．该文在概要地讨论了两类求解非二元约束问题方法的基础上，研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法，并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法，以典型例子给出了实现系统的运行结果．     

用圆锥曲线求解几何约束问题

几何约束求解广泛应用于机械设计,化学分子形成,几何定理证明和勘探等诸多领域,用于求解几何约束问题主要有3种方法：数值方法,符号方法和构造法,构造法用于具有简单易行的特点,因此被大多数的参数化机械设计系统作为求解几何约束问题的基本方法,针对构造法中只采用直线和圆,即直尺和圆规,来作为基本的作图工具,引进了一种新的作图工具,圆锥曲线,并且证明了在引进圆锥曲线以后,作图的范围明显大于只用直尺和圆规作图的范围;证明了一个图形能用圆锥曲线作出的充分必要条件是这个图形可以用一个三角化的次数小于等于4的方程组来描述;由于三次和四次方程的解可以显式地表示出来,所以引进圆锥曲线作为一个新的作图工具仍然可以保持原来尺规作图的简洁性和完整性。     

一种基于免疫原理求解TSP问题的模型

基于人工免疫原理,建立了一个基于免疫机制求解TSP问题的数学模型。在该模型中,定义了TSP问题中的抗原和抗体,描述了记忆细胞动态进化过程,并借鉴遗传算法中基因变异思想,提出了优势基因进化的GFE算法,结合生物免疫系统抗体浓度稳定原理,在克隆选择过程中实现了抗体集合的进化计算,快速有效地求解出问题的全局近似最优解。实验结果表明该算法对解决组合优化问题不仅可行,而且有较快的收敛速度和较强的全局搜索能力。