Programs to solve so-called constraint problems are complex pieces of software which require many design decisions to be made more or less arbitrarily by the implementer. These decisions affect the performance of the finished solver significantly [13]. Once a design decision has been made, it cannot easily be reversed, although a different decision may be more appropriate for a particular problem. We investigate using machine learning to make these decisions automatically depending on the problem to solve with the alldifferent constraint as an example. Our system is capable of making nontrivial, multilevel decisions that improve over always making a default choice.

We study a dominance relation for comparing outcomes based on unconditional qualitative preferences and compare it with its unconditional counterparts for TCP-nets and their variants. Dominance testing based on this relation can be carried out in polynomial time by evaluating the satisfiability of a logic formula.

In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.

In this paper, we introduce a new class of local consistencies, called df-consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition and a mapping f that provides a covering for each relation of the considered qualitative calculus. We study the connections existing between some properties of the introduced mappings and the relative inference strength of df-consistencies. The consistency obtained by the usual closure under weak composition corresponds to the weakest element of the class, whereas df-consistencies stronger than weak composition open new promising perspectives. Interestingly, the class of df-consistencies is shown to form a complete lattice where the partial order denotes the relative strength of every two consistencies. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any "well-behaved" consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.

In particular, I will explain how the complexity scheduling, planning, graph problems, among others. The landscape differs for traditional reasoning and for query most well-known constraint satisfaction problem is propositional answering, and take a brief look at computational complexity satisfiability SAT. Of particular recent interest is satisfiability issues raised by implementations of DL query answering modulo theories (SMT), where the interpretation based on standard relational database systems. Throughout of some symbols is constrained by a background theory. For the tutorial, connections to the W3C-standard OWL are example, the theory of arithmetic restricts the interpretation drawn whenever possible. of symbols such as:,, 0, and 1. SMT draws on the most prolific problems in the past century What If You Wanted Someone (Else) to Use This?

We report (to our knowledge) the first evaluation of Constraint Satisfaction as a computational framework for solving closest string problems. We show that careful consideration of symbol occurrences can provide search heuristics that provide several orders of magnitude speedup at and above the optimal distance. We also report (to our knowledge) the first analysis and evaluation -- using any technique -- of the computational difficulties involved in the identification of all closest strings for a given input set. We describe algorithms for web-scale distributed solution of closest string problems, both purely based on AI backtrack search and also hybrid numeric-AI methods.

Planning as Satisfiability is a most successful approach to optimal propositional planning. It draws its strength from the efficiency of state-of-the-art propositional satisfiability solvers, combined with the utilization of constraints that are inferred from the problem planning graph. One of the recent improvements of the framework is the addition of long-distance mutual exclusion (londex) constraints that relate facts and actions which refer to different time steps. In this paper we compare different encodings of planning as satisfiability wrt the constraint propagation they achieve in a modern SAT solver. This analysis explains some of the differences observed in the performance of different encodings, and leads to some interesting conclusions. For instance, the Blackbox encoding achieves more propagation than the one of Satplan06, and therefore is a stronger formulation of planning as satisfiability. Moreover, our investigation suggests a new more compact and stronger model for the problem. We prove that in this new formulation many of the londex constraints are redundant in the sense that they do not add anything to the constraint propagation achieved by the model. Experimental results suggest that the theoretical results obtained are practically relevant.

Efficient management and propagation of temporal constraints is important for temporal planning as well as for scheduling. During plan development, new events and temporal constraints are added and existing constraints may be tightened; the consistency of the whole temporal network is frequently checked; and results of constraint propagation guide further search. Recent work shows that enforcing partial path consistency provides an efficient means of propagating temporal information for the popular Simple Temporal Network (STN). We show that partial path consistency can be enforced incrementally, thus exploiting the similarities of the constraint network between subsequent edge tightenings. We prove that the worst-case time complexity of our algorithm can be bounded both by the number of edges in the chordal graph (which is better than the previous bound of the number of vertices squared), and by the degree of the chordal graph times the number of vertices incident on updated edges. We show that for many sparse graphs, the latter bound is better than that of the previously best-known approaches. In addition, our algorithm requires space only linear in the number of edges of the chordal graph, whereas earlier work uses space quadratic in the number of vertices. Finally, empirical results show that when incrementally solving sparse STNs, stemming from problems such as Hierarchical Task Network planning, our approach outperforms extant algorithms.

The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearls belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes.

Fatima Jinnah Women University Rawalpindi, Pakistan Abstract-Recent advancement in web services plays an important role in business to business and business to consumer interaction. Discovery mechanism is not only used to find a suitable service but also provides collaboration between service providers and consumers by using standard protocols. A static web service discovery mechanism is not only time consuming but requires continuous human interaction. This paper proposed an efficient dynamic web services discovery mechanism that can locate relevant and updated web services from service registries and repositories with timestamp based on indexing value and categorization for faster and efficient discovery of service. The proposed prototype focuses on quality of service issues and introduces concept of local cache, categorization of services, indexing mechanism, CSP (Constraint Satisfaction Problem) solver, aging and usage of translator. Performance of proposed framework is evaluated by implementing the algorithm and correctness of our method is shown. The results of proposed framework shows greater performance and accuracy in dynamic discovery mechanism of web services resolving the existing issues of flexibility, scalability, based on quality of service, and discovers updated and most relevant services with ease of usage. I. INTRODUCTION As an enabling technology, web services are software components that are used to present services on internet.