Communicating sequential processes for distributed constraint satisfaction

CSPCONS is a programming language that supports program execution over multiple Prolog processes with constraints. The language is an extended version of Csp-ii, a version of Prolog that supports channel-based communicating processes and TCP/IP communication, that is based on the CSP model introduced by Hoare. Cspcons inherits all the advanced features of Csp-ii and extends it by introducing constraint solving capabilities to the processes. In Cspcons each Prolog process has one or more solvers attached and each solver is independent from the others, following the original Csp-ii model, thus resulting to a communicating sequential constraint logic programming system. Such a model can facilitate greatly the implementation of distributed CLP applications. This paper describes the original Csp-ii system along with details of the extensions that resulted to the Cspcons system and presents an example demonstrating the applicability of the system to distributed constraint satisfaction problems.     

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.     

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

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

Formulating the template ILP consistency problem as a constraint satisfaction problem

Inductive Logic Programming (ILP) deals with the problem of finding a hypothesis covering positive examples and excluding negative examples, where both hypotheses and examples are expressed in first-order logic. In this paper we employ constraint satisfaction techniques to model and solve a problem known as template ILP consistency, which assumes that the structure of a hypothesis is known and the task is to find unification of the contained variables. In particular, we present a constraint model with index variables accompanied by a Boolean model to strengthen inference and hence improve efficiency. The efficiency of models is demonstrated experimentally.     

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.     

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...     

The complexity of soft constraint satisfaction

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of constraints to a corresponding set of algebraic operations, known as polymorphisms.In this paper we extend the analysis of complexity to the more general framework of combinatorial optimisation problems expressed using various forms of soft constraints. We launch a systematic investigation of the complexity of these problems by extending the notion of a polymorphism to a more general algebraic operation, which we call a multimorphism. We show that many tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. We also show that a simple set of NP-hard constraints has very restricted multimorphisms. Finally, we use the notion of multimorphism to give a complete classification of complexity for the Boolean case which extends several earlier classification results for particular special cases.     

A formalization of geometric constraint systems and their decomposition

For more than a decade, the trend in geometric constraint systems solving has been to use a geometric decomposition/recombination approach. These methods are generally grounded on the invariance of systems under rigid motions. In order to decompose further, other invariance groups (e.g., scalings) have recently been considered. Geometric decomposition is grounded on the possibility to replace a solved subsystem with a smaller system called boundary. This article shows the central property that justifies decomposition, without assuming specific types of constraints or invariance groups. The exact nature of the boundary system is given. This formalization brings out the elements of a general and modular implementation.     

Protein structure prediction problem: formalization using quaternions

The authors discuss the formalization of protein tertiary structure prediction problem based on Dill’s HP-model. Three-dimensional discrete lattices and different approaches to representing paths on them are the subjects of investigation. Two ways of path encoding are proposed and formalized, one of which is based on quaternions.     

Conservative constraint satisfaction re-revisited

Conservative constraint satisfaction problems (CSPs) constitute an important particular case of the general CSP, in which the allowed values of each variable can be restricted in an arbitrary way. Problems of this type are well studied for graph homomorphisms. A dichotomy theorem characterizing conservative CSPs solvable in polynomial time and proving that the remaining ones are NP-complete was proved by Bulatov (2003) in [4]. Its proof, however, is quite long and technical. A shorter proof of this result based on the absorbing subuniverses technique was suggested by Barto (2011) in [1]. In this paper we give a short elementary proof of the dichotomy theorem for conservative CSPs.     

Relatively quantified constraint satisfaction

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.     

Lexicographically-ordered constraint satisfaction problems

We describe a simple CSP formalism for handling multi-attribute preference problems with hard constraints, one that combines hard constraints and preferences so the two are easily distinguished conceptually and for purposes of problem solving. Preferences are represented as a lexicographic order over complete assignments based on variable importance and rankings of values in each domain. Feasibility constraints are treated in the usual manner. Since the preference representation is ordinal in character, these problems can be solved with algorithms that do not require evaluations to be represented explicitly. This includes ordinary CSP algorithms, although these cannot stop searching until all solutions have been checked, with the important exception of heuristics that follow the preference order (lexical variable and value ordering). We describe relations between lexicographic CSPs and more general soft constraint formalisms and show how a full lexicographic ordering can be expressed in the latter. We discuss relations with (T)CP-nets, highlighting the advantages of the present formulation, and we discuss the use of lexicographic ordering in multiobjective optimisation. We also consider strengths and limitations of this form of representation with respect to expressiveness and usability. We then show how the simple structure of lexicographic CSPs can support specialised algorithms: a branch and bound algorithm with an implicit cost function, and an iterative algorithm that obtains optimal values for successive variables in the importance ordering, both of which can be combined with appropriate variable ordering heuristics to improve performance. We show experimentally that with these procedures a variety of problems can be solved efficiently, including some for which the basic lexically ordered search is infeasible in practice.     

Multi-agent oriented constraint satisfaction

This paper presents a multi-agent oriented method for solving CSPs (Constraint Satisfaction Problems). In this method, distributed agents represent variables and a two-dimensional grid-like environment in which the agents inhabit corresponds to the domains of the variables. Thus, the positions of the agents in such an environment constitute the solution to a CSP. In order to reach a solution state, the agents will rely on predefined local reactive behaviors; namely, better-move, least-move, and random-move. While presenting the formalisms and algorithm, we will analyze the correctness and complexity of the algorithm, and demonstrate the proposed method with two benchmark CSPs, i.e., n-queen problems and coloring problems. In order to further determine the effectiveness of different reactive behaviors, we will examine the performance of this method in deriving solutions based on behavior prioritization and different selection probabilities.     

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.     

CONSAT: A parallel constraint satisfaction system

In this paper we describe the parallelization of a medium-size symbolic fixed-point computation, CONSAT. CONSAT is a constraint satisfaction system that computes globally consistent solutions. The parallel version of CONSAT is implemented using abstractions from a parallel programming toolbox we developed. The toolbox is intended for novice parallel programmers, and programs based on abstractions from this toolbox may be executed on both uniprocessors and shared-memory multiprocessors without modifications. We explain how parallelism is introduced, and how concurrent accesses to shared data structures are handled. We will also describe the performance of CONSAT on sample inputs.     

The complexity of constraint satisfaction games and QCSP

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain to the variables, in a specified order. The first player tries to satisfy all constraints, while the other tries to break at least one constraint; the goal is to decide whether the first player has a winning strategy. We show that such games can be conveniently represented by a logical form of quantified constraint satisfaction, where an instance is given by a first-order sentence in which quantifiers alternate and the quantifier-free part is a conjunction of (positive) atomic formulas; the goal is to decide whether the sentence is true.While the problem of deciding such a game is PSPACE-complete in general, by restricting the set of allowed constraint predicates, one can obtain infinite classes of constraint satisfaction games of lower complexity. We use the quantified constraint satisfaction framework to study how the complexity of deciding such a game depends on the parameter set of allowed predicates. With every predicate, one can associate certain predicate-preserving operations, called polymorphisms. We show that the complexity of our games is determined by the surjective polymorphisms of the constraint predicates. We illustrate how this result can be used by identifying the complexity of a wide variety of constraint satisfaction games.     

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

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

Backtracking and random constraint satisfaction

The average running time used by backtracking on random constraint satisfaction problems is studied. This time is polynomial when the ratio of constraints to variables is large, and it is exponential when the ratio is small. When the number of variables goes to infinity, whether the average time is exponential or polynomial depends on the number of variables per constraint, the number of values per variable, and the probability that a random setting of variables satisfies a constraint. A method for computing the curve that separates polynomial from exponential time and several methods for approximating the curve are given. The version of backtracking studied finds all solutions to a problem, so the running time is exponential when the number of solutions per problem is exponential. For small values of the probability, the curve that separates exponential and polynomial average running time coincides with the curve that separates an exponential average number of solutions from a polynomial number. For larger probabilities the two curves diverge. Random problems similar to those that arise in understanding line drawings with shadows require a time that is mildly exponential when they are solved by simple backtracking. Slightly more sophisticated algorithms (such as constraint propagation combined with backtracking) should be able to solve these rapidly. This revised version was published online in June 2006 with corrections to the Cover Date.     

Solving set-valued constraint satisfaction problems

In this paper, we consider the resolution of constraint satisfaction problems in the case where the variables of the problem are subsets of ${\mathbb{R}^{n}}$ . In order to use a constraint propagation approach, we introduce set intervals (named i-sets), which are sets of subsets of ${\mathbb{R}^{n}}$ with a lower bound and an upper bound with respect to the inclusion. Then, we propose basic operations for i-sets. This makes possible to build contractors that are then used by the propagation to solve problem involving sets as unknown variables. In order to illustrate the principle and the efficiency of the approach, a testcase is provided.