Efficient handling of universally quantified inequalities

This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology. We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that our algorithm outperforms the state of the art methods based on constraint techniques. This paper is an extended version of a paper published at the SAC 2008 conference [15].     

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     

Combining restarts,nogoods and bag-connected decompositions for solving CSPs

From a theoretical viewpoint, the (tree-)decomposition methods offer a good approach for solving Constraint Satisfaction Problems (CSPs) when their (tree)-width is small. In this case, they have often shown their practical interest. So, the literature (coming from Mathematics, OR or AI) has concentrated its efforts on the minimization of a single parameter, namely the tree-width. Nevertheless, experimental studies have shown that this parameter is not always the most relevant to consider when solving CSPs. So, in this paper, we highlight two fundamental problems related to the use of tree-decomposition and for which we offer two particularly appropriate solutions. First, we experimentally show that the decomposition algorithms of the state of the art produce clusters (a tree-decomposition is a rooted tree of clusters) having several connected components. We highlight the fact that such clusters create a real disadvantage which affects significantly the efficiency of solving methods. To avoid this problem, we consider here a new graph decomposition called Bag-Connected Tree-Decomposition, which considers only tree-decompositions such that each cluster is connected. We analyze such decompositions from an algorithmic point of view, especially in order to propose a first polynomial time algorithm to compute them. Moreover, even if we consider a very well suited decomposition, it is well known that sometimes, a bad choice for the root cluster may significantly degrade the performance of the solving. We highlight an explanation of this degradation and we propose a solution based on restart techniques. Then, we present a new version of the BTD algorithm (for Backtracking with Tree-Decomposition Jégou and Terrioux, Artificial Intelligence, 146 43–75 28) integrating restart techniques. From a theoretical viewpoint, we prove that reduced nld-nogoods can be safely recorded during the search and that their size is smaller than ones recorded by MAC+RST+NG (Lecoutre et al., JSAT, 1(3–4) 147–167 34). We also show how structural (no)goods may be exploited when the search restarts from a new root cluster. Finally, from a practical viewpoint, we show experimentally the benefits of using independently bag-connected tree-decompositions and restart techniques for solving CSPs by decomposition methods. Above all, we experimentally highlight the advantages brought by exploiting jointly these improvements in order to respond to two major problems generally encountered when solving CSPs by decomposition methods.     

Solving Mixed and Conditional Constraint Satisfaction Problems

Constraints are a powerful general paradigm for representing knowledge in intelligent systems. The standard constraint satisfaction paradigm involves variables over a discrete value domain and constraints which restrict the solutions to allowed value combinations. This standard paradigm is inapplicable to problems which are either:(a) mixed, involving both numeric and discrete variables, or(b) conditional,¹ containing variables whose existence depends on the values chosen for other variables, or(c) both, conditional and mixed.We present a general formalism which handles both exceptions in an integral search framework. We solve conditional problems by analyzing dependencies between constraints that enable us to directly compute all possible configurations of the CSP rather than discovering them during search. For mixed problems, we present an enumeration scheme that integrates numeric variables with discrete ones in a single search process. Both techniques take advantage of enhanced propagation rule for numeric variables that results in tighter labelings than the algorithms commonly used. From real world examples in configuration and design, we identify several types of mixed constraints, i.e. constraints defined over numeric and discrete variables, and propose new propagation rules in order to take advantage of these constraints during problem solving.     

An interval algorithm for multi-objective optimization

This paper presents an interval algorithm for solving multi-objective optimization problems. Similar to other interval optimization techniques, [see Hansen and Walster (2004)], the interval algorithm presented here is guaranteed to capture all solutions, namely all points on the Pareto front. This algorithm is a hybrid method consisting of local gradient-based and global direct comparison components. A series of example problems covering convex, nonconvex, and multimodal Pareto fronts is used to demonstrate the method.     

一个基于模拟退火的多主体模型及其应用

近些年,多主体系统的理论及应用得到了人们的广泛关注,并得以迅速发展.研究者提出了很多基于多主体系统理论的模型,用于求解各种问题.AER(Agent-environment-rules)模型正是一个用于求解约束满足问题较为成功的例子.但是,主体的静态策略选择在一定程度上限制了模型的求解性能.将模拟退火算法与多主体系统思想相结合,并赋予主体更为高效的动态策略选择的能力,提出了SAAER模型(simulated annealing based AER model).基于约束满足问题经典实例--N-Queen问题和染色问题的实验表明,改进后的模型较之原模型获得了更高的效率和稳定性.对于N=10000的大规模N-Queen问题,能在200s左右的时间求得精确解.     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure

Computing the minimal representation of a given set of constraints (a CSP) over the Point Algebra (PA) is a fundamental temporal reasoning problem. The main property of a minimal CSP over PA is that the strongest entailed relation between any pair of variables in the CSP can be derived in constant time. We study some new methods for solving this problem which exploit and extend two prominent graph-based representations of a CSP over PA: the timegraph and the series-parallel (SP) metagraph. Essentially, these are graphs partitioned into sets of chains and series-parallel subgraphs, respectively, on which the search is supported by a metagraph data structure. The proposed approach is based on computing the metagraph closure for these representations, which can be accomplished by some methods studied in the paper.In comparison with the known techniques based on enforcing path consistency, under certain conditions about the structure of the input CSP and the size of the generated metagraph, the proposed metagraph closure approach has better worst-case time and space complexity. Moreover, for every sparse CSP over the convex PA, the time complexity is reduced to O(n²) from O(n³), where n is the number of variables involved in the CSP.An extensive experimental analysis presented in the paper compares the proposed techniques and other known algorithms. These experimental results identify the best performing methods and show that, in practice, for CSPs exhibiting chain or SP-graph structure and randomly generated (both sparse and dense) CSPs, the metagraph closure approach is significantly faster than the approach based on enforcing path consistency.     

A new approach to partial constraint satisfaction problems

A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems.

In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n ² d ²) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ?n(n???2)(d???2)/(d???1)?.     

On the need for a different backtracking rule when dealing with late evaluation

Constraint Satisfaction Problems (CSPs) represent a widely used framework for many real-life problems. Constraint Logic Programming (CLP) languages are an effective tool for modeling problems in terms of CSPs and solving them efficiently.Lazy domain evaluation is a solving technique that has proven effective for solving CSPs, allowing the minimization of the number of constraint checks. However, exploiting lazy domain evaluation in CLP is not very effective, mainly because of the chronological backtracking rule used in CLP. After each backtracking step, in fact, all the obtained results are lost, even if they had nothing to do with the culprit of the failure. The intelligent backtracking rule widely studied in the past does not solve the problem either.In this paper, we propose a backtracking rule useful for dealing efficiently and declaratively with lazy domain evaluation in CLP, and we show a simple implementation of a metainterpreter providing the depicted functionality.     

Hybrid backtracking bounded by tree-decomposition of constraint networks

We propose a framework for solving CSPs based both on backtracking techniques and on the notion of tree-decomposition of the constraint networks. This mixed approach permits us to define a new framework for the enumeration, which we expect that it will benefit from the advantages of two approaches: a practical efficiency of enumerative algorithms and a warranty of a limited time complexity by an approximation of the tree-width of the constraint networks. Finally, experimental results allow us to show the advantages of this approach.     

DEM generation from lidar data in wooded mountain areas by cross-section-plane analysis

Ground filtering for airborne lidar data is a challenging task for the generation of digital terrain models (DTMs) in wooded mountain areas. To solve this problem, this article, based on cross-section-plane (CSP) analysis, presents a CSP-based stepwise filtering strategy that can automatically separate terrain from non-terrain points. The filtering strategy consists of four main computing steps: (a) ‘split’ – the raw lidar data are partitioned into 3D cells, in each of which multi-directional CSPs are generated at multiple directions; (b) ‘filter’ – the potential terrain points are selected for each CSP according to lidar data characteristics, such as multi-returns, intensity, and height; (c) ‘detect’ – the initial terrain points are detected for each CSP by exploring distances and slopes between nearby points; and (d) ‘adjust-and-refine’ – the terrain points are extracted from all initial terrain points of all CSPs by a merging-or-intersecting strategy and a five-point refinement. The extensive experiments using three lidar data sets demonstrated that the CSP-based stepwise filtering method is capable of producing reliable DTMs in densely forested mountain areas.     

Concurrent product configuration and process planning: Some optimization experimental results

In nowadays industrial competition, optimizing concurrently the configured product and the planning of its production process becomes a key issue in order to achieve mass customization development. However, if many studies have addressed these two problems separately, very few have considered them concurrently. We therefore consider in this article a multi-criteria optimization problem that follows an interactive configuration and planning process. The configuration and planning problems are considered as constraint satisfaction problems (CSPs). After some recalls about this two-step approach, we propose to evaluate a recent evolutionary optimization algorithm called CFB-EA (for constraint filtering based evolutionary algorithm). CFB-EA, specially designed to handle constrained problems, is compared with an exact branch and bound approach on small problem instances and with another evolutionary approach carefully selected for larger instances. Various experiments, with solutions spaces up to 10¹⁷, permit us to conclude that CFB-EA sounds very promising for the concurrent optimization of a configured product and its production process.     

Ants can solve constraint satisfaction problems

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems     

A quantitative framework for security assurance evaluation and selection of cloud services: a case study

Due to the high adoption of cloud services, the protection of data and information is critical. Cloud service customers (CSCs) need help to obtain the authoritative assurances required for the cloud services and negotiate the cloud service contract based on the terms and conditions set by cloud service providers (CSPs). Several standards and guidelines are available for assessing cloud security. However, most of these standards and guidelines are complex and time-consuming to select a service or make an informed decision for CSCs. Moreover, the existing methods are insufficient to solve this problem because they are process-oriented, neglect the importance of stakeholder requirements, and lack a comprehensive and rigid analytic method that can aid decision-makers in making the right decisions. In this paper, we developed two evaluation techniques: (i) a quantitative cloud security assurance method to assess the security level of cloud services by measuring the critical security properties and (ii) a novel and rigid categorical analytical method that enables CSPs to identify the major problems in the system and assess how much gain can be achieved by solving each of them. The cloud security assurance method is based on two important metrics: security requirement and vulnerability. It assists CSCs in avoiding severe mistakes and making informed decisions while selecting a cloud service. Moreover, these methods support CSPs in improving the security level of cloud services and meet customer requirements. The proposed methods are validated using different case scenarios on a private cloud platform.

     

A graph-based immune-inspired constraint satisfaction search

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.     

Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison

In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in ijcai95,jacm and schiex-ijcai95.     

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.     

Issues in the performance measurement of constraint-satisfaction techniques

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate.Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.