Solving quantified constraint satisfaction problems

We make a number of contributions to the study of the Quantified Constraint Satisfaction Problem (QCSP). The QCSP is an extension of the constraint satisfaction problem that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. In this paper we report significant contributions to two very different methods for solving QCSPs. The first approach is to implement special purpose algorithms for QCSPs; and the second is to encode QCSPs as Quantified Boolean Formulas and then use specialized QBF solvers. The discovery of particularly effective encodings influenced the design of more effective algorithms: by analyzing the properties of these encodings, we identify the features in QBF solvers responsible for their efficiency. This enables us to devise analogues of these features in QCSPs, and implement them in special purpose algorithms, yielding an effective special purpose solver, QCSP-Solve. Experiments show that this solver and a highly optimized QBF encoding are several orders of magnitude more efficient than the initially developed algorithms. A final, but significant, contribution is the identification of flaws in simple methods of generating random QCSP instances, and a means of generating instances which are not known to be flawed.     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

Low-level dichotomy for quantified constraint satisfaction problems

Building on a result of Larose and Tesson for constraint satisfaction problems (CSPs), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime.We show that the class of B such that CSP(B) is first-order expressible (indeed trivial) is a microcosm for all QCSPs. Specifically, for any B there exists a C — generally not a core — such that CSP(C) is trivial, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions.     

基于禁忌搜索算法求解随机约束满足问题

为了求解具有增长取值域的随机约束满足问题（CSP）,提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。     

Solving constraint satisfaction problems with SAT modulo theories

Due to significant advances in SAT technology in the last years, its use for solving constraint satisfaction problems has been gaining wide acceptance. Solvers for satisfiability modulo theories (SMT) generalize SAT solving by adding the ability to handle arithmetic and other theories. Although there are results pointing out the adequacy of SMT solvers for solving CSPs, there are no available tools to extensively explore such adequacy. For this reason, in this paper we introduce a tool for translating FLATZINC (MINIZINC intermediate code) instances of CSPs to the standard SMT-LIB language. We provide extensive performance comparisons between state-of-the-art SMT solvers and most of the available FLATZINC solvers on standard FLATZINC problems. The obtained results suggest that state-of-the-art SMT solvers can be effectively used to solve CSPs.     

Solving constraint satisfaction problems using hybrid evolutionarysearch

We combine the concept of evolutionary search with the systematic search concepts of arc revision and hill climbing to form a hybrid system that quickly finds solutions to static and dynamic constraint satisfaction problems (CSPs). Furthermore, we present the results of two experiments. In the first experiment, we show that our evolutionary hybrid outperforms a well-known hill climber, the iterative descent method (IDM), on a test suite of 750 randomly generated static CSPs. These results show the existence of a “mushy region” which contains a phase transition between CSPs that are based on constraint networks that have one or more solutions and those based on networks that have no solution. In the second experiment, we use a test suite of 250 additional randomly generated CSPs to compare two approaches for solving CSPs. In the first method, all the constraints of a CSP are known by the hybrid at run-time. We refer to this method as the static method for solving CSPs. In the second method, only half of the constraints of a CSPs are known at run-time. Each time that our hybrid system discovers a solution that satisfies all of the constraints of the current network, one additional constraint is added. This process of incrementally adding constraints is continued until all the constraints of a CSP are known by the algorithm or until the maximum number of individuals has been created. We refer to this second method as the dynamic method for solving CSPs. Our results show hybrid evolutionary search performs exceptionally well in the presence of dynamic (incremental) constraints, then also illuminate a potential hazard with solving dynamic CSPs     

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。     

Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules

In this paper, the product configuration problems that are characterized by cardinality-based configuration rules are dealt with. Novel configuration rules including FI and EI rules are presented to clarify the semantics of inclusion rules when cardinalities and hierarchies of products are encountered. Then, a configuration graph is proposed to visualize structural rules and configuration rules in product configuration problem. An encoding approach is elaborated to transform the configuration graph as a CSP (Constraint Satisfaction Problem). As a consequence, existing CSP solver, i.e. JCL (Java Constraint Library), is employed to implement the configuration system for product configuration problem with cardinality-related configuration rules. A case study of a bus configuration is used throughout this paper to illustrate the effectiveness of the presented approach.     

适应模糊QoS约束优化的Web服务选择技术研究

基于QoS优化的全局Web服务选择涉及多目标和多阶段的服务合成,以及各种QoS属性的折衷,如可信性、可用性和声望等,因此提出了适当的基因算法来处理服务选择问题。由于发现质量驱动的Web服务选择是一个NP-hard问题,实际的多目标或QoS标准并不总是明确的,常常包含模糊元素。着重研究多目标Web服务选择过程中模糊QoS属性和适应进化函数之间的关系,以及如何调节个体模糊QoS属性以实现整个种群进化的问题。     

Musical constraint satisfaction problems solved with adaptive search

Constraint Programming (CP) allows to model and solve combinatory problems by specifying some partial information on variables, unknowns of the problem. We have studied musical constraint problems, either stated by contemporary composers, or of musical analysis, or instrumentation, in collaboration with IRCAM (french Institute for Research and Coordination Acoustics / Music). Fourteen such problems have been modeled and solved, which allowed to give a detailed typology. This has been used to conceive and implement OMClouds, a library in the Computer Assisted Composition environment OpenMusic. It is based on a local search algorithm called adaptive search. Its architecture allows in particular to define a constraint problem visually, to solve it, and eventually to edit partial or approached results during the resolution process.     

Relaxations of semiring constraint satisfaction problems

The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. Bistarelli et al. [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraint solving and optimization, Journal of the ACM 44 (2) (1997) 201-236] defines a maximal solution to a SCSP as the best set of solution tuples for the variables in the problem. Sometimes this maximal solution may not be good enough, and in this case we want to change the constraints so that we solve a problem that is slightly different from the original problem but has an acceptable solution. We propose a relaxation of a SCSP, and use a semiring to give a measure of the difference between the original SCSP and the relaxed SCSP. We introduce a relaxation scheme but do not address the computational aspects.     

Backjump-based backtracking for constraint satisfaction problems

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.     

Reoptimization of constraint satisfaction problems with approximation resistant predicates

If k = O(log n) and a predicate P is approximation resistant for the reoptimization of the Max-EkCSP-P problem, then, after inserting a truth-value into the predicate and imposing some constraint, there exists a polynomial algorithm with the approximation ratio q(P) = \frac12 - d(P) q(P) = \frac{1}{{2 - d(P)}} , where d(P) = 2 ^{- k}| P ^{- 1}(1) | d(P) = {2^{ - k}}\left| {{P^{ - 1}}(1)} \right| is a “random” threshold approximation ratio of the predicate P. The ratio q(P) is a threshold approximation ratio.     

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.     

Solving nesting problems with non-convex polygons by constraint logic programming

In this paper an application of constraint logic programming (CLP) to the resolution of nesting problems is presented. Nesting problems are a special case of the cutting and packing problems, in which the pieces generally have non‐convex shapes. Because of their combinatorial optimization nature, nesting problems have traditionally been tackled by heuristics and in the recent past by meta‐heuristics. When trying to formulate nesting problems as linear programming models, to achieve global optimal solutions, the difficulty of dealing with the disjunction of constraints arises. On the contrary, CLP deals easily with this type of relationships among constraints. A CLP implementation for the nesting problem is described for convex and non‐convex shapes. The concept of nofit polygon is used to deal with the geometric constraints inherent to all cutting and packing problems. Computational results are presented.     

随机约束满足问题相变研究综述

随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。     

A new tractable class of constraint satisfaction problems

In this paper we consider constraint satisfaction problems where the set of constraint relations is fixed. Feder and Vardi (1998) identified three families of constraint satisfaction problems containing all known polynomially solvable problems. We introduce a new class of problems called para-primal problems, incomparable with the families identified by Feder and Vardi (1998) and we prove that any constraint problem in this class is decidable in polynomial time. As an application of this result we prove a complete classification for the complexity of constraint satisfaction problems under the assumption that the basis contains all the permutation relations. In the proofs, we make an intensive use of algebraic results from clone theory about the structure of para-primal and homogeneous algebras. AMS subject classification 08A70     

Solving shortest path problems with a weight constraint and replenishment arcs

This paper tackles a generalization of the weight constrained shortest path problem (WCSPP) in a directed network with replenishment arcs that reset the accumulated weight along the path to zero. Such situations arise, for example, in airline crew pairing applications, where the weight represents duty hours, and replenishment arcs represent crew overnight rests; and also in aircraft routing, where the weight represents time elapsed, or flight time, and replenishment arcs represent maintenance events. In this paper, we review the weight constrained shortest path problem with replenishment (WCSPP-R), develop preprocessing methods, extend existing WCSPP algorithms, and present new algorithms that exploit the inter-replenishment path structure. We present the results of computational experiments investigating the benefits of preprocessing and comparing several variants of each algorithm, on both randomly generated data, and data derived from airline crew scheduling applications.