A new search algorithm for solving distributed constraint satisfaction problems ({\em DisCSP}s) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking algorithm ({\em AFC}) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven.

The sequential assignment method of $AFC$ leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics are evaluated and shown to improve the performance of $AFC$ with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking ($ABT$) on randomly generated DisCSPs is also presented. $AFC$ with ordering heuristics outperforms $ABT$ by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of non-concurrent constraints checks and number of messages sent.

CP04 Tutorial: Distributed Constraints Satisfaction Algorithms, Performance, Communication
Amnon Meisels
Constraints Programming 2004, Toronto, September 2004   Presentation (ppt)

Distributed constraints satisfaction problems (DisCSPs) have been studied for over a decade. The first distributed search algorithm was asynchronous backtracking, which is still the most studied. In the last few years, several new families of distributed search algorithms have been investigated and comparative experimental studies are encouraging. A natural extension to distributed constraints satisfaction is distributed constraints optimization. Stochastic search algorithms for solving DisCSPs, such as Distributed Breakout, have appeared a few years ago. Distributed stochastic search algorithms are naturally suitable for solving distributed optimization. In contrast, asynchronous search algorithms for distributed optimization have been proposed in recent years. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of algorithms on DisCSPs. This has been shown in an experimental study that induced random delays on messages sent among agents. In order to study the impact of message delays on DisCSP search, a model of delays in terms of concurrent performance measures is needed. Within such a model, the behavior of families of search algorithms in the presence of delays is varied and interesting. An important feature of the distribution of the problem among agents is their ability to maintain some privacy. Agents may not want to share their values with other agents, and they may wish to keep constraints as private as possible. Some recent work has resulted in versions of asynchronous backtracking that maintain both privacy of values and privacy of constraints. Other investigations of privacy in DisCSPs focused on the analysis of information gain by studying a welldefined problem, that of scheduling meetings of agents.

Message delay and DisCSP search algorithms
Roie Zivan and Amnon Meisels
Proceedings 5th Workshop on Distributed Constraints Reasoning, DCR-04, Toronto, September 2004

Using additional information in DisCSPs search
Amnon Meisels and Oz Lavee
Proceedings 5th Workshop on Distributed Constraints Reasoning, DCR-04, Toronto, September 2004

Roie Zivan and Amnon Meisels
Proceedings FLAIRS-2004, pp. 776-81, Miami-Beach, May 2004.

Asynchronous Forward-checking on DisCSPs
Amnon Meisels  and Roie Zivan
Proc. Workshop on Distributed Constraints (DCR-03), Acapulco, August 2003.

Distributed Forward Checking with Dynamic Ordering

Amnon Meisels and Igor Razgon
Submitted to Constraints Journal November 2002

Distributed Constraints Satisfaction Problems (DisCSPs) are composed of a set of Agents, each having its set of variables and their domains of values. Variables of different agents are connected by constraints, forming a global constraints network. In a
distributed algorithm for solving DisCSPs, agents cooperate in searching for a consistent assignment, to all variables of all
agents, that satisfies all of the constraints.

A distributed forward checking DisCSP algorithm is presented. The proposed algorithm includes dynamic variable ordering in a natural way making cooperative decisions. A correctness proof for the new algorithm is presented. Experiments comparing the behavior of the proposed dynamically ordered distributed forward checking (DODFC) algorithm with asynchronous backtracking algorithms, are reported. The proposed DODFC outperforms ABT and DDBT on hard instances of randomly generated DisCSPs. DODFC supports privacy of values and privacy of constraints simultaneously. 

Scheduling Agents - Distributed Timetabling Problems (DisTTP)
Amnon Meisels and Eliezer Kaplansky
Proc. PATAT-2002, pp. 166-80, Ghent, July 2002 (LNCS #2740).

 Many real world \emph{Timetabling Problems} (TTPs) are composed of organizational parts that need to timetable their staff in an independent way, while adhering to some global constraints. Later the departmental timetables are combined to yield a coherent, consistent solution. This last phase involves negotiations with the various agents and requests for changes in their own solutions.
 Most of the real world distributed timetabling problems that fall under this class have global constraints that involve many of the agents in the system. Models that use networks of binary constraints are inadequate. As a result, this paper proposes a new model that contains only one additional agent - the Central agent (CA) that coordinates the search process of all Scheduling Agents (SAs).

Preliminary experiments show that a sophisticated heuristic is needed for the CA to effectively interact with its scheduling agents  in order to find an optimal solution. The approach and the results reported in this paper are an initial attempt to investigate possible solution methods for networks of SAs.A parallel algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. DisCSPs are composed of agents, each holding a local network of constraints, where all agents are connected by constraints.

Comparing Performance of Distributed Constraints Processing Algorithms

Amnon Meisels, Eliezer Kaplansky, Igor Razgon and Roie Zivan
Proc. Workshop on Distributed Constraint Reasoning, in AAMAS-2002, pp. 86-93, Bologna (July 2002)

Search algorithms on distributed constraints satisfaction problems, DisCSPs, are composed of agents performing computations concurrently.
The most common abstract performance measurement that has been universally adopted for centralized CSPs algorithms is the number of constraints checks performed. However, when it comes to distributed search, constraints checks are performed concurrently by all agents on the network
and therefore a simple measurement of constraints checks is not adequate any more. In order to be able to compare the behavior
of different algorithms, there is a need for a new distributed method to measure the search effort of a DisCSP algorithm.

A model for measuring concurrent constraints checks on distributed constraints satisfaction problems (DisCSPs) is presented.
The advantages of the proposed model are clarified by a series of simple constraints network examples. An algorithm for computing the
proposed measure, the {\em cumulative cost algorithm  (CCA)}, is presented. A formal correctness proof of the CCA algorithm, according to the proposed model for concurrent constraints checks (CCCs) is presented.
 

Parallel Backtrack Search on DisCSPs
Roie Zivan and Amnon Meisels
Proc. Workshop on Distributed Constraint Reasoning, in AAMAS-2002, pp. 202-208, Bologna (July 2002)

A parallel algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. DisCSPs are composed of agents, each holding a local network of constraints, where all agents are connected by constraints.
The parallel backtracking algorithm (PBT) initiates multiple search processes (SPs) that operate in parallel. Parallel search processes scan different parts of the search tree, each represented by a data structure that is circulated
among the different agents.

The PBT algorithm is presented in its simplest form - generating search processes that are simple backtracking procedures. It is shown to be correct and complete and its implementation is streightforward. The degree of concurrency achieved in experiments on random DisCSPs is very encouraging. Load balancing for parallel backtracking can be achieved by adding concurrent search trees dynamically. Versions of PBT, based on the same protocol of the current partial assignment (CPA), perform re-splitting of the search space. A preliminary experimental evaluation of the algorithm, on randomly generated DisCSPs, is presented.
 

Amnon Meisels and Igor Razgon
Proc. workshop on collective search algorithms - CP01 (November  2001)

Distributed Constraints Networks (DCNs) are composed of a set of Agents, each having its set of variables and their domains of values. Variables of different Agents are connected by constraints, forming a global constraints network. In a distributed algorithm for solving a DCN, all agents cooperate in searching for a consistent assignment, to all variables of all agents, that satisfies all of the constraints.

 A distributed forward checking algorithm for distributed constraint networks (DCNs) is presented. The algorithm solves DCNs in which agents include partial networks (i.e. multiple variables). The proposed algorithm includes dynamic variable ordering in a natural way making cooperative decisions. This is in contrast to former distributed search algorithms that relied for their correctness on static (i.e. predefined) order of their variables. An outline of a correctness proof for the new algorithm is presented and the main differences in its cooperative search behavior from former algorithms is explained.

 Experiments comparing the behavior of the proposed dynamically ordered distributed forward checking (DODFC) algorithm with either centralized forward checking or the weak-commitment asynchronous search algorithm of Yokoo, were performed on randomly generated constraints networks. For the most difficult problems, the proposed DODFC performs better than either Yokoo's algorithm or a centralized version of FC.
 

Modelling and Solving Employee Timetabling Problems

Amnon Meisels and Andrea Schaerf
Annal. Math. and AI, Vol. 39, pp. 41-59, 2003.

    Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time, typically a week.  We present a general definition of employee timetabling problems (ETPs) that captures many real-world problem formulations and includes complex constraints. The proposed model of ETPs can be represented in a tabular form that is both intuitive and efficient for constraint representation and processing. The constraint networks of ETPs include non-binary constraints and are difficult to formulate in terms of simple constraint solvers.  We investigate the use of local search techniques for solving ETPs.  In particular, we propose several versions of hill-climbing that make use of a novel search space that includes also partial assignments.

  We show that, on large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest instances. According to our experimental results on various techniques, a simple version of hill climbing based on random moves is the best method for solving large ETP instances.

   Restart techniques for randomizing complete search algorithms were proposed recently by Selman and Gomes, for solving hard combinatorial problems. A new iterative algorithm that uses restart techniques is proposed, and its behavior analyzed on random timetabling problems. Employee timetabling problems (ETPs) can naturally represented by constraints networks for real world instances which are large and difficult. Complete search algorithms, even with good heuristics are unable to solve large enough instances of ETPs. In fact, several local search techniques have been proposed in the past decade for solving timetabling problems. In particular, it has been shown that local search can efficiently solve large ETPs.

   Random instances of ETPs that was generated based on real world ETPs are used to test the proposed iterative restart algorithm - GIRA. The two main parameters of GIRA are pointed out and investigated: the initial cutoff value for restart and the number of idle iterations. For random sets of a large range of hardness of ETPs, the successful values of these two parameters tend to be surprisingly low. We conclude by recommending an optimal range of values for the initial cutoff and demonstrate experimentally that the number of idle iterations is of little consequence.

Resource allocation problems are naturaly represented as constraint networks (CN), with constraints of inequality among activities that compete for the same resources at the same time [Faltings and Choueiry 94]. A new algorithm for solving networks of RAPs is described and its detailed behavior is presented on a small example and on a real world problem. The proposed algorithm delays assignments of resources to selected activities and processes the network during the assignment procedure, to select delays and values. The proposed algorithm is an enhancement to standard intelligent backtracking algorithms [Prosser 93], is complete and performs better than two former approaches to solving constraints networks of resource allocation (cf. [Regin 94,Faltings and Choueiry 94a+b]). One way to view the new resource assignment algorithm (RAA) is in the form of a dynamic variable ordering heuristic. The differences between RAA and former preprocessing heuristic methods for resource allocation problems is discussed in the context of a simple example and a realistic problem of employee assignment.

 The problem of counting the number of solutions to a constraint network (CN) (also called constraint satisfaction problems, CSPs) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree-structured CNs. For other CNs, it is less optimistic than a spanning-tree approximation suggested in prior work. Experiments show that the Bayes nets estimation is more accurate on the average, compared to competing methods (the spanning-tree, as well as a scheme based on a product of all compatible pairs of values). We present empirical evidence that our approximation may also be a useful (value ordering) search heuristic for finding a single solution to a constraint satisfaction problem.

Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time. We present a general definition of employee timetabling problems (ETPs) that captures many real world problem formulations and includes complex constraints. We investigate the use of several local search techniques for solving ETPs. In particular, we propose a generalization of local search that makes use of a novel search space that includes also partial assignments. We describe the distinguishing features of this generalized local search that allows it to navigate the search space effectively. On large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest instances. According to our experimental results on various local search techniques, generalized local search is the best method for solving large ETP instances.

CSPs with Counters: a Likelihood-Based Heuristic.

Numerous applications of constraint satisfaction problems (CSP) exhibit global constraints. Such constraints abound in resource-allocation-type problems, as well as in other domains. The form of global constraint we consider are {\em counter constraints}, which limit the number of variables that may be assigned particular values. This paper integrates counter constraints with the constraint satisfaction problem (CSP) paradigm in a novel manner. Counter constraints are problematic for most heuristics, which are local in scope. We suggest a useful heuristic for value ordering during search, based on estimated likelihood of solution, and show its advantages empirically. The heuristic is useful for standard CSPs, as well as ones with counter constraints, where it approximates the number of solutions for a particular value assignment to a variable. Counter constraints can be represented in standard CSPs, at a cost. We analyze the cost, show how a counter can be represented as a linear number of binary constraints, and show experimentally that even with the optimal reduction it is better to represent counters explicitly rather than as a set of local constraints.

The general timetabling problem is an assignment of activities to fixed time intervals, adhering to a predefined set of resource availabilities. Timetabling problems are difficult to solve and can be extremely time-consuming without some computer assistance. In this paper the application of constraint-based reasoning to timetable generation is examined. Specifically, we consider how a timetabling problem can be represented as a Constraint Satisfaction Problem (CSP), and propose an algorithm for its solution which improves upon the basic idea of backtracking. Normally, when a backtracking routine fails to find a solution, there is nothing of value returned to the user; however, our algorithm extends this process by iteratively adding constraints to the CSP representation. A generalized random model of timetabling problems is proposed. This model creates a diverse range of problem instances, which are used to verify our search algorithm and identify the characteristics of difficult timetabling problems.

FlexiMine - A Flexible Platform for KDD Research and Application Development
R. Ben-Eliyahu-Zohary, C. Domshlak, E. Gudes, N. Liusternik, A. Meisels, T. Rosen, S. E. Shimony .
a revised version from Proceedings of KDD-98 New York, August 1998

FlexiMine is a KDD system designed as a testbed for data-mining research, as well as a generic knowledge discovery tool for varied database domains. Flexibility is achieved by an open-ended design that enables integration of existing data-mining algorithms, new locally developed algorithms, and utility functions such as visualization and preprocessing. The system interfaces an INFORMIX database server via SQL queries and thus support for new databases is simple and clean. With a view of serving remote, as well as local, users, internet availability was a design goal. Fleximine is implemented in Java and hence we can run the user-end of the system either as a Java applications or (with some limitations on the user) as a Java applet. This paper reviews the architecture, design and operation of FlexiMine and presents new ideas incorporated in the data-mining algorithms (Association rules, Decision trees, Bayesian knowledge-bases and Meta-queries).

Experiments on Networks of Employee Timetabling Problems.
Amnon Meisels and Natalia Lusternik.
Proc. PATAT97, Toronto, August 1997 (LNCS  # 1408 pp. 130-142)

Constraint networks (CN) that represent employee timetabling problems (ETP) are described and a testbed of random ETP CNs is designed. The natural representation of ETPs as CNs has variables representing working shifts and values representing employees that are assigned to work-shifts. In this representation, ETPs have binary constraints of non-equality (mutual exclusion), the networks are non uniform, and variables have different domains of values. There is also a typical family of non-binary constraints that represent finite capacity limits. The random testbed of ETPs includes all of the above features and is solved by standard constraint processing techniques, such as forward checking (FC) and conflict directed backjumping (CBJ). The set of ETP CNs is characterized by the average intersection of domains, together with the usual parameters of CNs (i.e. the density and tightness of constraints $p_{1}, p_{2}$). One major result is that the ETPs exhibit a strong change in difficulty (as measured by consistency checks) for small values of intersection among domains of variables. Non binary constraints of finite capacity are part of the experimental testbed. An enhanced FC-CBJ search algorithm is used to test these random networks and the experimental results are presented.

A canonical model for distributed constraint satisfaction problems (DCSP) is presented and algorithms for processing constraints on a DCSP are described. The central idea behind a constraint network that is {\em given} as a DCSP is the existence of large differences between the cost of {\em message passing} among different components of a DCSP and the cost of local consistency checks {\em within} each component. Therefore, algorithms which operate in a multi-agent environment to solve these problems are required to take into consideration these differences. Four basic algorithms for solving DCSPs that are sound and complete are proposed. Two of these algorithms are sequential and two algorithms operate in parallel and are inherently distributed. The behavior of the proposed algorithms was tested by generating and solving a set of random DCSPs (for a variety of parameters of density and homogeneity ). The results show the superiority of the parallel algorithms when the cost variances are large. A series of enhancements of the basic algorithms are presented. These enhancements permit both to extend the scope of the algorithms and their performances. To motivate and test the approach we present a real life problem dealing with Nurses timetabling and transportation in a large multi-department hospital. We compare the results of solving this problem by using the basic algorithms, the enhanced algorithms, and the sequential CSP algorithms.

 Employee Timetabling Problems (ETP) are all around us. One possible approach for solving ETPs is to use constraint processing techniques. Another approach is to model human knowledge which is commonly used for solving such problems into knowledge-based systems for timetabling. It is difficult to represent the complex constraints of timetabling explicitly in constraint networks. On the other hand, knowledge-based representations of constraints are implicit and cannot support most of the heuristics of constraint based processing that have been developed over the last decade. The present paper presents an approach to representing and processing employee timetabling problems by a combination of explicit representations of some constraints in the network and rule-based processing in which heuristics for generic constraints of ETPs are embedded. This mixed-mode approach has been implemented in the form of a software package for defining and solving real world ETPs. A general description of the design and organization of this software tool is given. %Examples of a family %of real world ETPs are followed all through the presentation and are quantitatively %used to explore the constraint network (CN) parameters of these problems. Results for solving a typical real world employee timetabling problem is presented and a comparison with the use of standard CSP techniques is made.