Production management as a constraint satisfaction problem

Production management problems can be quite straightforwardly presented as constraint satisfaction problems, where values for some variables are searched for under a set of constraints. A combination of an operation and a resource is usually interpreted as the variable, and a time window is usually interpreted as the value to be searched for. This convention is challenged. A case is considered where the most appropriate interpretation treats the combination of a resource and a time window as the variable, and an operation as the value. A third possible interpretation is also briefly covered, where the combination of an operation and a time window is the variable, and the resource is the value.     

不同紧度下约束满足问题的相变现象

提出了一个基于RB模型的随机约束满足问题即◢p◣-RB模型。该模型考虑了约束紧度的多样性,将所有约束按照不同的权重分成若干组,同一组具有相同的约束紧度,而相异组具有不同的约束紧度。用二阶矩方法严格证明了随着控制参数的不断增加,◢p◣-RB模型发生了精确的可满足性相变现象。数值实验表明该模型的有解概率经历了从1到0的突然转变,同时求解难度在相变区域达到高峰,表明该模型在相变区域能产生大量的难解实例。     

Hierarchical arc consistency: exploiting structured domains in constraint satisfaction problems

Constraint satisfaction problems can be solved by network consistency algorithms that eliminate local inconsistencies before constructing global solutions. We describe a new algorithm that is useful when the variable domains can be structured hierarchically into recursive subsets with common properties and common relationships to subsets of the domain values for related variables. The algorithm, HAC, uses a technique known as hierarchical arc consistency. Its performance is analyzed theoretically and the conditions under which it is an improvement are outlined. The use of HAC in a program for understanding sketch maps, Mapsee3, is briefly discussed and experimental results consistent with the theory are reported.     

基于约束满足的测试计划方法

测试经理在制定测试计划时,往往只能依靠个人经验,缺乏理论方法的指导,面对复杂软件系统时难以全面考虑测试模块间关系及测试人员能力等复杂因素,往往使得测试效果并不令人满意.将约束规划技术引入测试领域,结合测试计划自身特点,提出了一种全新的基于约束满足的测试计划方法.方法将软件产品划分为测试模块,通过确定各模块测试过程及过程间顺序约束、资源能力约束,对测试计划问题进行了约束建模和求解.并以项目管理软件SoftPM的测试过程为例,对方法的具体应用进行了介绍.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Argumentation frameworks as constraint satisfaction problems

Argumentation is a promising approach for defeasible reasoning. It consists of justifying each plausible conclusion by arguments. Since the available information may be inconsistent, a conclusion and its negation may both be justified. The arguments are thus said to be conflicting. The main issue is how to evaluate the arguments. Several semantics were proposed for that purpose. The most important ones are: stable, preferred, complete, grounded and admissible. A semantics is a set of criteria that should be satisfied by a set of arguments, called extension, in order to be acceptable. Different decision problems related to these semantics were defined (like whether an argumentation framework has a stable extension). It was also shown that most of these problems are intractable. Consequently, developing algorithms for these problems is not trivial and thus the implementation of argumentation systems not obvious. Recently, some solutions to this problem were found. The idea is to use a reduction method where a given problem is translated in another one like SAT or ASP. This paper follows this line of research. It studies how to encode the problem of computing the extensions of an argumentation framework (under each of the previous semantics) as a constraint satisfaction problem (CSP). Such encoding is of great importance since it makes it possible to use the very efficient solvers (developed by the CSP community) for computing the extensions. Our encodings take advantage of existing reductions to SAT problems in the case of Dung’s abstract framework. Among the various ways of translating a SAT problem into a CSP one, we propose the most appropriate one in the argumentation context. We also provide encodings in case two other families of argumentation frameworks: the constrained version of Dung’s abstract framework and preference-based argumentation framework.     

Interactive scheduling as a constraint satisfiability problem

A constraint satisfiability problem consists of a set of variables, their associated domains (i.e., the set of values the variable can take) and a set of constraints on these variables. A solution to the CSP is an instantiation (or labeling) of all the variables which does not violate any of the constraints. Since constraint satisfiability problems are, in general, NP-complete, it is of interest to compare the effectiveness and efficiency of heuristic algorithms as applied, in particular, to our application. Our research effort attempts to determine which algorithms perform best in solving the student scheduling problem (SSP) and under what conditions. We also investigate the probabilistic techniques of Nudel for finding a near-optimal instantiation order for search algorithms, and develop our own modifications which can yield a significant improvement in efficiency for the SSP. Experimental results have been collected and are reported here. Our system was developed for and used at Bar-Ilan University during the registration period, being available for students to construct their timetables.     

The complexity of some polynomial network consistency algorithms for constraint satisfaction problems

Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. We analyze the time complexity of several node, arc and path consistency algorithms and prove that arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables.     

An Iterative local-search framework for solving constraint satisfaction problem

In this article, we introduce a new solving framework based on using alternatively two local-search algorithms to solve constraint satisfaction and optimization problems. The technique presented is based on the integration of local-search algorithm as a mechanism to diversify the search instead of using a build on diversification mechanisms. Thus, we avoid tuning the multiple parameters to escape from a local optimum. This technique improves the existing methods: it is generic especially when the given problem can be expressed as a constraint satisfaction problem. We present the way the local-search algorithm can be used to diversify the search in order to solve real examination timetabling problems. We describe how the local-search algorithm can be used to assist any other specific local-search algorithm to escape from local optimality. We showed that such framework is efficient on real benchmarks for timetabling problems.     

Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

We consider a random constraint satisfaction problem named model RB, which exhibits a sharp satisfiability phase-transition phenomenon when the control parameters pass through the critical values denoted by rcr and pcr. Using finite-size scaling analysis, we bound the width of the transition region for finite problem size n, which might be the first rigorous study on the threshold behaviors of NP-complete problems.     

A constraint satisfaction problem algorithm for large-scale multi-panel composite structures

Structural and Multidisciplinary Optimization - This paper proposes a constraint satisfaction problem algorithm based on implicit decision trees and dynamic programming for the design of multiple...     

求解入库堆垛问题的改进约束满足算法

入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长（重）的货物置于较短（轻）的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

An ILP representation of a DAG scheduling problem

Real-Time Systems - The use of integer linear programs for solving complex real-time scheduling problems is investigated. The problem of scheduling a workload represented as a directed acyclic...     

Approximated consistency for the automatic recording constraint

We introduce the automatic recording constraint (ARC) that can be used to model and solve scheduling problems where tasks may not overlap in time and the tasks linearly exhaust some resource. Since achieving generalized arc-consistency for the ARC is NP-hard, we develop a filtering algorithm that achieves approximated consistency only. Numerical results show the benefits of the new constraint on three out of four different types of benchmark sets for the automatic recording problem. On these instances, run-times can be achieved that are orders of magnitude better than those of the best previous constraint programming approach.     

分布式约束满足问题及其在MAS任务分配中的应用*

针对多智能体系统(MAS)任务分配问题中多个任务与MAS两者的分布式特征,将任务分配问题形式化为分布式约束满足问题(DCSP)进行求解,分别建立了以任务为中心和以agent为中心两种MAS任务分配模型,基于改进的DCSP分布式并行求解算法,提出了基于DCSP的MAS任务分配问题求解框架。该方法适合求解agent间通信有随机延迟以及agent间存在多约束的问题,应用实例的求解表明了其实用性与有效性。     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。     

基于UML与CCSP的产品配置方法

为了有效开发易维护可重用的产品配置模型以及实现配置问题的快速求解,提出了结合面向对象建模技术与条件约束满足问题理论的产品配置方法。给出了条件约束满足问题理论模型;提出了基于统一建模语言和条件约束满足问题的产品配置建模与求解方法;通过定义统一建模语言表示的产品配置概念模型与条件约束满足问题之间的映射规则集,建立了基于条件约束满足问题的产品配置模型。以某可配置医用监测器为应用实例,阐述了所提方法应用于配置模型构建与求解的可行性和有效性。