Binary Encodings of Nonbinary Constraint Satisfaction Problems: Algorithms and Experimental Results


 Augusta Evans
 6 years ago
 Views:
Transcription
1 Journal of Artificial Intelligence Research 24 (2005) Submitted 04/05; published 11/05 Binary Encodings of Nonbinary Constraint Satisfaction Problems: Algorithms and Experimental Results Nikolaos Samaras Department of Applied Informatics University of Macedonia, Greece Kostas Stergiou Department of Information and Communication Systems Engineering University of the Aegean, Greece Abstract A nonbinary Constraint Satisfaction Problem (CSP) can be solved directly using extended versions of binary techniques. Alternatively, the nonbinary problem can be translated into an equivalent binary one. In this case, it is generally accepted that the translated problem can be solved by applying wellestablished techniques for binary CSPs. In this paper we evaluate the applicability of the latter approach. We demonstrate that the use of standard techniques for binary CSPs in the encodings of nonbinary problems is problematic and results in models that are very rarely competitive with the nonbinary representation. To overcome this, we propose specialized arc consistency and search algorithms for binary encodings, and we evaluate them theoretically and empirically. We consider three binary representations; the hidden variable encoding, the dual encoding, and the double encoding. Theoretical and empirical results show that, for certain classes of nonbinary constraints, binary encodings are a competitive option, and in many cases, a better one than the nonbinary representation. 1. Introduction Constraint Satisfaction Problems (CSPs) appear in many reallife applications such as scheduling, resource allocation, timetabling, vehicle routing, frequency allocation, etc. Most CSPs can be naturally and efficiently modelled using nonbinary (or nary) constraints that may involve an arbitrary number of variables. It is well known that any nonbinary CSP can be converted into an equivalent binary one. The most wellknown translations are the dual encoding (Dechter & Pearl, 1989) and the hidden variable encoding (Rossi, Petrie, & Dhar, 1990). The ability to translate any nonbinary CSP into binary has been often used in the past as a justification for restricting attention to binary CSPs. Implicitly, the assumption had been that when faced with a nonbinary CSP we can simply convert it into a binary one, and then apply wellknown generic techniques for solving the binary equivalent. In this paper we will show that this assumption is flawed because generic techniques for binary CSPs are not suitable for binary encodings of nonbinary problems. In the past few years, there have been theoretical and empirical studies on the efficiency of binary encodings and comparisons between binary encodings and the nonbinary representation (Bacchus & van Beek, 1998; Stergiou & Walsh, 1999; Mamoulis & Stergiou, 2001; Smith, 2002; Bacchus, Chen, van Beek, & Walsh, 2002). Theoretical results have showed c 2005 AI Access Foundation. All rights reserved.
2 Samaras & Stergiou that converting nonbinary CSPs into binary equivalents is a potentially efficient way to solve certain classes of nonbinary problems. However, in the (limited) empirical studies there are very few cases where this appears to be true, with Conway s game of Life (Smith, 2002) being the most notable exception. There are various reasons for this. In many cases, the extensive space requirements of the binary encodings make them infeasible. Also, in many nonbinary problems we can utilize efficient specialized propagators for certain constraints, such as the algorithm developed by Régin (1994) for the alldifferent constraint. Converting such constraints into binary is clearly impractical. Another reason, which has been overlooked, is that most (if not all) experimental studies use wellknown generic local consistency and search algorithms in the encodings. In this way they fail to exploit the structure of the constraints in the encodings, ending up with inefficient algorithms. To make the binary encodings a realistic choice of modelling and solving nonbinary CSPs, we need algorithms that can utilize their structural properties. Finally, it is important to point out that the use of a binary encoding does not necessarily mean that we have to convert all the nonbinary constraints in a problem into binary, as it is commonly perceived. If we are selective in the constraints we encode, based on properties such as arity and tightness, then we can get efficient hybrid models. To address these issues, we show that the use of specialized arc consistency and search algorithms for binary encodings of nonbinary CSPs can lead to efficient models. We consider three encodings; the dual, the hidden variable, and the double encoding. The latter, which is basically the conjunction of the other two encodings, has received little attention but may well turn out to be the most significant in practice. The aim of this study is twofold. First, to present efficient algorithms for the binary encodings and analyze them theoretically and experimentally. Second, and more importantly, to investigate if and when the use of such algorithms can help solve nonbinary problems efficiently. Towards these aims, we make the following contributions: We describe a simple algorithm that enforces arc consistency on the hidden variable encoding of an arbitrary nonbinary CSP with O(ekd k ) time complexity, where e is the number of constraints, k the maximum arity of the constraints, and d the maximum domain size. This gives an O(d) improvement compared to the asymptotic complexity of a generic arc consistency algorithm. The improved complexity is now the same as the complexity of an optimal generalized arc consistency algorithm in the nonbinary representation of the problem. We also identify a property of the arc consistency algorithm for the hidden variable encoding that can make it run faster, on arc inconsistent problems, than the generalized arc consistency algorithm. We then consider search algorithms that maintain local consistencies during search in the hidden variable encoding. We show that, like maintaining arc consistency, all the generalizations of forward checking to nonbinary CSPs can be emulated by corresponding forward checking algorithms that run in the hidden variable encoding and only instantiate original variables (i.e. the variables of the initial nonbinary problem). We show that each such algorithm and its corresponding algorithm for nonbinary constraints have the following relationships: 1) they visit the same number of search tree nodes, and 2) the asymptotic cost of each of them is within a polynomial bound of the other. 642
3 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results We describe a specialized algorithm for the dual encoding that achieves arc consistency with O(e 3 d k ) worstcase time complexity. This is significantly lower than the O(e 2 d 2k ) complexity of a generic arc consistency algorithm. The improvement in the complexity bound stems from the observation that constraints in the dual encoding have a specific structure; namely they are piecewise functional (Van Hentenryck, Deville, & Teng, 1992). Apart from applying arc consistency in the dual encoding of a nonbinary CSP, this algorithm can also be used as a specialized filtering algorithm for certain classes of nonbinary constraints. We adapt various search algorithms to run in the double encoding and compare them theoretically to similar algorithms for the hidden variable encoding and the nonbinary representation. Search algorithms that operate in the double encoding can exploit the advantages of both the hidden variable and the dual encoding. For example, we show that, under certain conditions, the asymptotic cost of the maintaining arc consistency algorithm in the double encoding can only be polynomially worse than the asymptotic cost of the corresponding algorithm in the nonbinary representation (and the hidden variable encoding), while it can be exponentially better. Finally, we make an extensive empirical study on various domains. We consider random problems as well as structured ones, like crossword puzzle generation, configuration, and frequency assignment. This study consists of two parts. In the first part, we give experimental results that demonstrate the advantages of the specialized algorithms for binary encodings compared to generic algorithms. For example, the specialized arc consistency algorithm for the dual encoding can be orders of magnitude faster than a generic arc consistency algorithm. In the second part we show that the use of binary encodings can offer significant benefits when solving certain classes of nonbinary CSPs. For example, solving the dual encoding of some configuration problems can be orders of magnitudes more efficient than solving the nonbinary representation. Also, empirical results from frequency assignment  like problems demonstrate that a binary encoding can be beneficial even for nonbinary constraints that are intentionally specified. This paper is structured as follows. In Section 2 we give the necessary definitions and background. In Section 3 we describe a specialized arc consistency algorithm for the hidden variable encoding. We also demonstrate that all the extensions of forward checking to nonbinary CSPs can be emulated by binary forward checking algorithms that run in the hidden variable encoding. In Section 4 we explain how the complexity of arc consistency in the dual encoding can be improved and describe a specialized arc consistency algorithm. Section 5 discusses algorithms for the double encoding. In Section 6 we present experimental results on random and structured problems that demonstrate the usefulness of the proposed algorithms. We also draw some conclusions regarding the applicability of the encodings, based on theoretical and experimental results. Section 7 discusses related work. Finally, in Section 8 we conclude. 643
4 Samaras & Stergiou 2. Background In this section we give some necessary definitions on CSPs, and describe the hidden variable, dual, and double encodings of nonbinary CSPs. 2.1 Basic Definitions A Constraint Satisfaction Problem (CSP), P, is defined as a tuple (X, D, C), where: X = {x 1,...,x n } is a finite set of n variables. D = {D in (x 1 ),...,D in (x n )} is a set of initial domains. For each variable x i X, D in (x i ) is the initial finite domain of its possible values. CSP algorithms remove values from the domains of variables through value assignments and propagation. For any variable x i,wedenotebyd(x i ) the current domain of x i that at any time consists of values that have not been removed from D in (x i ). We assume that for every x i X, a total ordering < d can be defined on D in (x i ). C = {c 1,...,c e } is a set of e constraints. Each constraint c i C is defined as a pair (vars(c i ),rel(c i )), where 1) vars(c i ) = {x j1,...,x jk } is an ordered subset of X called the constraint scheme, 2)rel(c i ) is a subset of the Cartesian product D in (x j1 )x...xd in (x jk ) that specifies the allowed combinations of values for the variables in vars(c i ). The size of vars(c i ) is called the arity of the constraint c i. Constraints of arity 2 are called binary. Constraints of arity greater than 2 are called nonbinary (or nary). Each tuple τ rel(c i ) is an ordered list of values (a 1,...,a k ) such that a j D in (x j ),j =1,...,k. A tuple τ =(a 1,...,a k )isvalid if a j,j 1,...,k, a j D(x j ). That is, a tuple is valid if all the values in the tuple are present in the domains of the corresponding variables. The process which verifies whether a given tuple is allowed by a constraint c i or not is called a consistency check. A constraint can be either defined extensionally by the set of allowed (or disallowed) tuples or intensionally by a predicate or arithmetic function. A binary CSP can be represented by a graph (called constraint graph) where nodes correspond to variables and edges correspond to constraints. A nonbinary CSP can be represented by a constraint hypergraph where the constraints correspond to hyperedges connecting two or more nodes. The assignment of value a to variable x i will be denoted by (x i,a). Any tuple τ = (a 1,...,a k ) can be viewed as a set of value to variable assignments {(x 1,a 1 ),...,(x k,a k )}. The set of variables over which a tuple τ is defined will be denoted by vars(τ). For any subset vars of vars(τ), τ[vars ] denotes the subtuple of τ that includes only assignments to the variables in vars. Any two tuples τ and τ of rel(c i ) can be ordered by the lexicographic ordering < lex. In this ordering, τ< lex τ iff there a exists a subset {x 1,...,x j } of c i such that τ[x 1,...,x j ]=τ [x 1,...,x j ]andτ[x j+1 ] < lex τ [x j+1 ]. An assignment τ is consistent, if for all constraints c i,wherevars(c i ) vars(τ), τ[vars(c i )] rel(c i ). A solution toacsp (X, D, C) is a consistent assignment to all variables in X. If there exists a solution for a given CSP, we say that the CSP is soluble. Otherwise, it is insoluble. A basic way of solving CSPs is by using backtracking search. This can be seen as a traversal of a search tree which comprises of the possible assignments of values to variables. 644
5 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results Each level of the tree corresponds to a variable. A node in the search tree corresponds to a tuple (i.e. an assignment of values to variables). The root of the tree corresponds to the empty tuple, the first level nodes correspond to 1tuples (an assignment of a value to one variable), the second level nodes correspond to 2tuples (assignment of values to two variables generated by extending the first level 1tuples) etc. At each stage of the search tree traversal, the variables that have been already assigned are called past variables. The most recently assigned variable is called current variable. The variables that have not been assigned yet are called future variables. In the rest of this paper we will use the notation n for the number of variables in a CSP, e for the number of constraints in the problem, d for the maximum domain size of the variables, and k for the maximum arity of the constraints Arc Consistency An important concept in CSPs is the concept of local consistency. Local consistencies are properties that can be applied in a CSP, using (typically) polynomial algorithms, to remove inconsistent values either prior to or during search. Arc consistency is the most commonly used local consistency property in the existing constraint programming engines. We now give a definition of arc consistency. Definition 2.1 Avaluea D(x j ) is consistent with a constraint c i,wherex j vars(c i )if τ rel(c i ) such that τ[x j ]=a and τ is valid. In this case we say that τ is a support of a in c i.aconstraintc i is Arc Consistent (AC) iff for each variable x j vars(c i ), a D(x j ), there exists a support for a in c i. A CSP (X, D, C) is arc consistent iff there is no empty domain in D and all the constraints in C are arc consistent. Arc consistency can be enforced on a CSP by removing all the unsupported values from the domains of variables. By enforcing arc consistency (or some local consistency property A in general) on a CSP P, we mean applying an algorithm that yields a new CSP that is arc consistent (or has the property A) and has the same set of solutions as P. The above definition of arc consistency applies to constraints of any arity. To distinguish between the binary and nonbinary cases, we will use the term arc consistency (AC) to refer to the property of arc consistency for binary constraints only. For nonbinary constraints we will use the term Generalized Arc Consistency (GAC). The usefulness of AC processing was recognized early, and as a result, various AC algorithms for binary constraints have been proposed in the literature (e.g. AC3 in Mackworth, 1977, AC4 in Mohr & Henderson, 1986, AC5 in Van Hentenryck et al., 1992, AC7 in Bessière et al., 1995, AC2001 in Bessière & Régin, 2001, AC3.1 in Zhang & Yap, 2001). Some of them have been extended to the nonbinary case (e.g. GAC4 in Mohr & Masini, 1988, GACSchema in Bessière & Régin, 1996a, GAC2001 in Bessière & Régin, 2001). AC can be enforced on a binary CSP with O(ed 2 ) optimal worstcase time complexity. The worstcase complexity of enforcing GAC on a nonbinary CSP is O(ekd k ) (Bessière & Régin, 1996a). In this paper we use algorithms AC2001 and GAC2001 for theoretical and empirical comparisons with specialized algorithms for the encodings. This is not restrictive, in the sense that any generic AC (and GAC) algorithm can be used instead. 645
6 Samaras & Stergiou Following Debruyne & Bessiére (2001), we call a local consistency property A stronger than B iff for any problem enforcing A deletes at least the same values as B, andstrictly stronger iff it is stronger and there is at least one problem where A deletes more values than B. WecallA equivalent to B iff they delete the same values for all problems. Similarly, we call a search algorithm A stronger than a search algorithm B iff for every problem A visits atmostthesamesearchtreenodesasb, and strictly stronger iff it is stronger and there is at least one problem where A visits less nodes than B. A is equivalent to B iff they visit the same nodes for all problems. Following Bacchus et al. (2002), the asymptotic cost (or just cost hereafter) of a search algorithm A is determined by the worstcase number of nodes that the algorithm has to visit to solve the CSP, and the worstcase time complexity of the algorithm at each node 1. As in the paper by Bacchus et al. (2002), we use this measure to set asymptotic bounds in the relative performance of various algorithms. For example, if two algorithms A and B always visit the same nodes and A enforces a property at each node with exponentially higher complexity than the property enforced by B, then we say that algorithm A can have an exponentially greater cost than algorithm B Functional and Piecewise Functional Constraints The specialized AC algorithms for the hidden variable and the dual encoding that we will describe in Sections 3 and 4 exploit structural properties of the encodings. As we will explain in detail later, the binary constraints in the hidden variable encoding are oneway functional, while the binary constraints in the dual encoding are piecewise functional. We now define these concepts. Definition 2.2 A binary constraint c, wherevars(c) ={x i,x j },isfunctional with respect to D(x i )andd(x j ) iff for all a D(x i )(resp. b D(x j )) there exists at most one value b D(x j )(resp.a D(x i )) such that b is a support of a in c (resp. a is a support of b). An example of a functional constraint is x i = x j. A binary constraint is oneway functional if the functionality property holds with respect to only one of the variables involved in the constraint. Informally, a piecewise functional constraint over variables x i, x j is a constraint where the domains of x i and x j can be partitioned into groups such that each group of D(x i )is supported by at most one group of D(x j ), and vice versa. To give a formal definition, we first define the concept of a piecewise decomposition. Definition 2.3 (Van Hentenryck et al., 1992) Let c be a binary constraint with vars(c) = {x i,x j }. The partitions S = {s 1,...,s m } of D(x i )ands = {s 1,...,s m } of D(x j)area piecewise decomposition of D(x i )andd(x j ) with respect to c iff for all s l S,s l S,the following property holds: either for all a s l, b s l,(a, b) rel(c), or for all a s l, b s l, (a, b) / rel(c). 1. In the paper by Bacchus et al. (2002) the cost of applying a variable ordering heuristic at each node is also taken into account. When we theoretically compare search algorithms in this paper we assume that they use the same variable ordering, so we do not take this cost into account. 646
7 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results Definition 2.4 (Van Hentenryck et al., 1992) A binary constraint c, wherevars(c) = {x i,x j },ispiecewise functional with respect to D(x i )andd(x j ) iff there exists a piecewise decomposition S = {s 1,...,s m } of D(x i )ands = {s 1,...,s m } of D(x j) with respect to c such that for all s l S (resp. s l S ), there exists at most one s l S (resp. s l S), such that for all a s l, b s l (a, b) rel(c). Example of piecewise functional constraints are the modulo (x 2 MOD x 3 = a) andinteger division (x 2 DIV x 3 = a) constraints. 2.2 Binary Encodings There are two wellknown methods for transforming a nonbinary CSP into a binary one; the dual graph encoding and the hidden variable encoding. Both encode the nonbinary constraints to variables that have as domains the valid tuples of the constraints. That is, by building a binary encoding of a nonbinary constraint we store the extensional representation of the constraint (the set of allowed tuples). A third method is the double encoding which combines the other two Dual Encoding The dual encoding (originally called dual graph encoding) was inspired by work in relational databases. In the dual encoding (DE) (Dechter & Pearl, 1989) the variables are swapped with constraints and vice versa. Each constraint c of the original nonbinary CSP is represented by a variable which we call a dual variable and denote by v c. We refer to the variables of the original nonbinary CSP as original variables. The domain of each dual variable v c consists of the set of allowed tuples in the original constraint c. Binary constraints between two dual variables v c and v c exist iff vars(c) vars(c ). That is, iff the constraints c and c share one or more original variables. If common vars is the set of original variables common to c and c then a tuple τ D(v c ) is supported in the constraint between v c and v c iff there exists a tuple τ D(v c ) such that τ[common vars] =τ [common vars]. v c1 (0,0,1) (0,1,0) (1,0,0) v c4 (0,0,0) (0,1,1) (1,0,1) (0,0,1) (1,0,0) (1,1,1) (0,1,0) (1,0,0) (1,1,0) (1,1,1) v c2 v c3 Figure 1: Dual encoding of a nonbinary CSP. 647
8 Samaras & Stergiou Consider the following example with six variables with 01 domains, and four constraints: c 1 : x 1 + x 2 + x 6 =1,c 2 : x 1 x 3 + x 4 =1,c 3 : x 4 + x 5 x 6 1, and c 4 : x 2 + x 5 x 6 = 0. The DE represents this problem with 4 dual variables, one for each constraint. The domains of these dual variables are the tuples that satisfy the respective constraint. For example, the dual variable v c3 associated with the third constraint has the domain {(0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1)} as these are the tuples of values for (x 4,x 5,x 6 )which satisfy x 4 + x 5 x 6 1. As a second example, the dual variable v c4 associated with the last constraint has the domain {(0, 0, 0), (0, 1, 1), (1, 0, 1)}. Between v c3 and v c4 there is a compatibility constraint to ensure that the two original variables in common, x 5 and x 6, have the same values. This constraint allows only those pairs of tuples which agree on the second and third elements (i.e. (1, 0, 0) for v c3 and (0, 0, 0) for v c4,or(1, 1, 1) for v c3 and (0, 1, 1) for v c4 ). The DE of the problem is shown in Figure 1. In the rest of this paper, we will sometimes denote by c vi the nonbinary constraint that is encoded by dual variable v i. For an original variable x j vars(c vi ), pos(x j,c vi ) will denote the position of x j in c vi. For instance, given a constraint c vi on variables x 1,x 2,x 3, pos(x 2,c vi )= Hidden Variable Encoding The hidden variable encoding (HVE) was inspired by the work of philosopher Peirce (1933). According to Rossi et al. (1990), Peirce first showed that binary relations have the same expressive power as nonbinary relations. In the HVE (Rossi et al., 1990), the set of variables consists of all the original variables of the nonbinary CSP plus the set of dual variables. As in the dual encoding, each dual variable v c corresponds to a constraint c of the original problem. The domain of each dual variable consists of the tuples that satisfy the original constraint. For every dual variable v c, there is a binary constraint between v c and each of the original variables x i such that x i vars(c). A tuple τ D(v c ) is supported in the constraint between v c and x i iff there exists a value a D(x i ) such that τ[x i ]=a. Consider the previous example with six variables with 01 domains, and four constraints: c 1 : x 1 + x 2 + x 6 =1,c 2 : x 1 x 3 + x 4 =1,c 3 : x 4 + x 5 x 6 1, and c 4 : x 2 + x 5 x 6 =0. In the HVE there are, in addition to the original six variables, four dual variables. As in the DE, the domains of these variables are the tuples that satisfy the respective constraint. There are now compatibility constraints between a dual variable v c and the original variables contained in constraint c. For example, there are constraints between v c3 and x 4, between v c3 and x 5 and between v c3 and x 6, as these are the variables involved in constraint c 3.The compatibility constraint between c v3 and x 4 is the relation that is true iff the first element in the tuple assigned to c v3 equals the value of x 4.TheHVEisshowninFigure Double Encoding The double encoding (Stergiou & Walsh, 1999) combines the hidden variable and the dual encoding. As in the HVE, the set of variables in the double encoding consists of all the variables of the original nonbinary CSP plus the dual variables. For every dual variable v c, there is a binary constraint between v c and each of the original variables x i involved in the corresponding nonbinary constraint c. As in the DE, there are also binary constraints 648
9 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results v c1 (0,0,1) (0,1,0) (1,0,0) v c4 (0,0,0) (0,1,1) (1,0,1) x x 2 x 3 x 4 x 5 x 6 (0,0,1) (1,0,0) (1,1,1) (0,1,0) (1,0,0) (1,1,0) (1,1,1) v c2 v c3 Figure 2: Hidden variable encoding of a nonbinary CSP. between two dual variables v c and v c more original variables. if the nonbinary constraints c and c share one or 3. Algorithms for the Hidden Variable Encoding In this section we discuss specialized algorithms for the HVE. We first describe a simple AC algorithm for the HVE that has the same worstcase time complexity as an optimal GAC algorithm for the nonbinary representation. In Appendix A, we also show that for any arc consistent CSP the proposed AC algorithm performs exactly the same number of consistency checks as the corresponding GAC algorithm. For arc inconsistent problems we show that the AC algorithm for the HVE can detect the inconsistency earlier and thus perform fewer consistency checks than the GAC algorithm. We also consider search algorithms for the HVE that maintain local consistencies during search. We show that, like maintaining arc consistency, the generalizations of forward checking to nonbinary CSPs can be emulated by corresponding binary forward checking algorithms in the HVE that only instantiate original variables. 3.1 Arc Consistency It has been proved that AC in the HVE is equivalent to GAC in the nonbinary problem (Stergiou & Walsh, 1999). Since the HVE is a binary CSP, one obvious way to apply AC is by using a generic AC algorithm. However, this results in redundant processing and an asymptotic time complexity worse than O(ekd k ). To be precise, in the HVE of a problem with k ary constraints we have ek binary constraints between dual and original variables. On such a constraint, AC can be enforced with O(dd k ) worstcase time complexity. For the wholeproblemthecomplexityiso(ekd k+1 ). Instead, we will now describe a simple AC algorithm that operates in the HVE and achieves the same worstcase time complexity as an optimal GAC algorithm applied in the nonbinary representation. We can achieve this by slightly modifying the GAC algorithm 649
10 Samaras & Stergiou of Bessiére and Régin (2001) (GAC2001). In Figure 3 we sketch the AC algorithm for the HVE, which we call HAC (Hidden AC). function HAC 1: Q 2: for each dual variable v j 3: for each variable x i where x i vars(c vj ) 4: if Revise(x i,v j )=TRUE 5: if D(x i )isemptyreturn INCONSISTENCY 6: put in Q each dual variable v l such that x i vars(c vl ) 7: return P ropagation function P ropagation 8: while Q is not empty 9: pop dual variable v j from Q 10: for each unassigned variable x i where x i vars(c vj ) 11: if Revise(x i,v j )=TRUE 12: if D(x i )isemptyreturn INCONSISTENCY 13: put in Q each dual variable v l such that x i vars(c vl ) 14: return CONSISTENCY function Revise(x i,v j ) 15: DELETION FALSE 16: for each value a D(x i ) 17: if currentsupport xi,a,v j is not valid 18: if τ( D(v j )) > lex currentsupport xi,a,v j, τ[x i ]=a and τ is valid 19: currentsupport xi,a,v j τ 20: else 21: remove a from D(x i ) 22: for each v l such that x i vars(c vl ) 23: remove from D(v l ) each tuple τ such that τ [x i ]=a 24: if D(v l )isemptyreturn INCONSISTENCY 25: DELETION TRUE 26: return DELETION Figure 3: HAC: an AC algorithm for the hidden variable encoding. The HAC algorithm uses a stack (or queue) of dual variables to propagate value deletions, and works as follows. In an initialization phase it iterates over each dual variable v j (line 2). For every original variable x i constrained with v j the algorithm revises the constraint between v j and x i. This is done by calling function Revise (line 4). During each revision, for each value a of D(x i ) we look for a tuple in the domain of v j that supports it. As in AC2001, we store currentsupport xi,a,v j : the most recent tuple we have found in D(v j ) that supports value a of variable x 2 i. If this tuple has not been deleted from D(v j ) 2. We assume, without loss of generality, that the algorithm looks for supports by checking the tuples in lexicographic order. 650
11 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results then we know that a is supported. Otherwise, we look for a new supporting tuple starting from the tuple immediately after currentsupport xi,a,v j. If no such tuple is found then a is removed from D(x i ) (line 21). In that case, all tuples that include that value are removed from the domains of the dual variables that are constrained with x i (lines 22 23). If these dual variables are not already in the stack they are added to it 3. Then, dual variables are removed from the stack sequentially. For each dual variable v j that is removed from the stack, the algorithm revises the constraint between v j and each original variable x i constrained with v j. The algorithm terminates if all the values in a domain are deleted, in which case the problem is not arc consistent, or if the stack becomes empty, in which case theproblemisarcconsistent. The main difference between HAC and GAC2001 is that GAC2001 does not include lines That is, even if the nonbinary constraints are given in extension, GAC does not remove tuples that become invalid from the lists of allowed tuples. As a result, the two algorithms check for the validity of a tuple (in lines 17 and 18) in different ways. Later on in this section we will explain this in detail. Apart from this difference, which is important because it affects their run times, the two algorithms are essentially the same. We can move from HAC to GAC2001 by removing lines and substituting any references to dual variables by references to the corresponding constraints. For example, currentsupport xi,a,v j corresponds to currentsupport xi,a,c vj in GAC2001, i.e. the last tuple in constraint c vj that supports value a of variable x i. Note that in such an implementation of GAC2001, propagation is constraintbased. That is, the algorithm utilizes a stack of constraints to perform the propagation of value deletions Complexities We now give a upper bound on the number of consistency checks performed by HAC in the worstcase. Function Revise(x i,v j ) can be called at most kd times for each dual variable v j, once for every deletion of a value from the domain of x i,wherex i is one of the k original variables constrained with v j. In each call to Revise(x i,v j ) the algorithm performs at most d checks (one for each value a D(x i )) to see if currentsupport xi,a,v j is valid (line 17). If currentsupport xi,a,v j is not valid, HAC tries to find a new supporting tuple for a in D(v j ). To check if a tuple τ that contains the assignment (x i,a) supports a we need to check if τ is valid. If a tuple is not valid then one of its values has been removed from the domain of the corresponding variable. This means that the tuple has also been removed from the domain of the dual variable. Therefore, checking the validity of a tuple can be done in constant time by looking in the domain of the dual variable. The algorithm only needs to check for support the d k 1, at maximum, tuples that contain the assignment (x i,a). Since HAC stores currentsupport xi,a,v j, at each call of Revise(x i,v j ) and for each value a D(x i ), it only checks tuples that have not been checked before. In other words, we can check each of the d k 1 tuples at most once for each value of x i. So overall, in the worst case, we have d k 1 checks plus the d checks to test the validity of the current support. For kd values the upper bound in checks performed by HAC to make one dual variable AC is 3. Note that dual variables that are already in the stack are never added to it. In this sense, the stack is implemented as a set. 651
12 Samaras & Stergiou O(kd(d+d k 1 ))=O(kd k ). For e dual variables the worstcase complexity bound is O(ekd k ), which is the same as the complexity of GAC in the nonbinary representation. The asymptotic space complexity of the HAC algorithm is dominated by the O(ed k ) space needed to store the domains of the dual variables. The algorithm also requires O(nde) space to store the current supports. Since the space required grows exponentially with the arity of the constraints, it is reasonable to assume that the HVE (and the other binary encodings) cannot be practical for constraints of large arity, unless the constraints are very tight. As mentioned, a consistency check in the nonbinary representation is done in a different way than in the HVE. Assume that GAC2001 looks for a support for value a i D(x i )in constraint c, wherevars(c) ={x 1,...,x k } and x i vars(c). A tuple τ =(a 1,...,a k ) supports a i if τ[x i ]=a i and τ is valid. To check if τ is valid, GAC2001 has to check if values a 1,...,a k (except a i ) are still in the domains of variables x 1,...,x k. Therefore, in the worst case, a consistency check by GAC2001 involves k 1 operations. In contrast, HAC checks for the validity of a tuple in constant time by looking in the domain of the corresponding dual variable to see if the tuple is still there. However, this means that the algorithm has to update the (usually) large domains of the dual variables after a value deletion from an original variable. This affects the run times of the algorithms in different problems settings. In Appendix A we show that HAC does not only have the same complexity, but it also performs exactly the same number of consistency checks as GAC2001 in arc consistent problems. We also show that in arc inconsistent problems there can be a difference in the number of checks in favor of the HVE. 3.2 Search Algorithms Search algorithms that maintain local consistencies are widely used for CSP solving. Some of them have been extended to the nonbinary case. For example, maintaining arc consistency (MAC) and forward checking (FC). It has been shown that the nonbinary version of MAC (MGAC) applied in a nonbinary CSP is equivalent to MAC applied in the HVE of the CSP when only original variables are instantiated and the same variable orderings are used (Stergiou & Walsh, 1999). We show that, like MGAC, nonbinary extensions of FC can be emulated by equivalent algorithms that run in the HVE. FC (Haralick & Elliot, 1980) was first generalized to handle nonbinary constraints by Van Hentenryck (1989). According to the definition of Van Hentenryck (1989), forward checking is performed after the k1 variables of an kary constraint have been assigned and the remaining variable is unassigned. This algorithm is called nfc0 in the paper by Bessiére, Meseguer, Freuder, & Larrosa (2002) where more, and stronger, generalizations of FC to nonbinary constraints were introduced. These generalizations differ between them in the extent of lookahead they perform after each variable instantiation. Algorithm nfc1 applies one pass of GAC on each constraint or constraint projection involving the current variable and exactly one future variable 4. Algorithm nfc2 applies GAC on the set of constraints involving the current variable and at least one future variable, in one pass. Algorithm nfc3 applies GAC to the set of constraints involving the current variable and at least one future 4. One pass means that each constraint is processed only once. 652
13 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results variable. Algorithm nfc4 applies GAC on the set of constraints involving at least one past variable and at least one future variable, in one pass. Algorithm nfc5, which is the strongest version, applies GAC to the set of constraints involving at least one past variable and at least one future variable. All the generalizations reduce to simple FC when applied to binary constraints. We will show that the various versions of nfc are equivalent, in terms of visited nodes, to binary versions of FC that run in the HVE of the problem. This holds under the assumption that the binary algorithms only assign original variables and they use the same variable and value ordering heuristics, static or dynamic, as their nonbinary counterparts. Note that if such an algorithm finds a consistent assignment for all original variables, and these assignments are propagated to the dual variables, then all the domains of the dual variables will be reduced to singletons. That is, the domain of each dual variable v c will only contain the single tuple that is consistent with the assignments of the original variables constrained with v c. Therefore, the algorithm can proceed to assign the dual variables in a backtrackfree manner. The equivalence between nfc1 and a version of FC for the HVE, called FC+ (Bacchus & van Beek, 1998), has been proved by Bessiére et al. (2002). FC+ is a specialized forward checking algorithm for the HVE. It operates like standard binary FC except that when the domain of a dual variable is pruned, FC+ removes from adjacent original variables any value which is no longer supported. Algorithms nfc2nfc5 also have equivalent algorithms that operate in the HVE. We call these algorithms hfc2 hfc5. For example, hfc5 will enforce AC on the set of dual variables, and original variables connected to them, such that each dual variable is connected to at least one past original variable and at least one future original variable. Note that nfc0 has no natural equivalent algorithm in the HVE. If we emulate it in the HVE we will get an inefficient and awkward algorithm. In the following, hfc0 will refer to the standard binary FC algorithm and hfc1 will refer to FC+. Proposition 3.1 In any nonbinary CSP, under a fixed variable and value ordering, algorithm nfci, i= 2,...5, is equivalent to algorithm hfci that operates in the hidden variable encoding of the problem. Proof: We prove this for nfc5, the strongest among the generalized FC algorithms. The proof for the other versions is similar. We only need to prove that at each node of the search tree algorithms nfc5 and hfc5 will delete exactly the same values from the domains of original variables. Assume that at some node, after instantiating the current variable, nfc5 deletes value a from a future variable x i. Then there exists some constraint c including x i and at least one past variable, and value a of x i has no supporting tuple in c. In the HVE, when hfc5 tries to make v c (the dual variable corresponding to c) ACitwill remove all tuples that assign a to x i. Hence, hfc5 will delete a from the domain of x i.now in the opposite case, if hfc5 deletes value a from an original variable x i it means that all tuples including that assignment will be removed from the domains of dual variables that include x i and at least one past variable. In the nonbinary representation of the problem, the assignment of a to x i will not have any supporting tuples in constraints that involve x i and at least one past variable. Therefore, nfc5 will delete a from the domain of x i. 653
14 Samaras & Stergiou Algorithms nfc2 nfc5 are not only equivalent in node visits with the corresponding algorithms hfc2 hfc5, but they also have the same asymptotic cost. This holds under the condition that the nonbinary algorithms use GAC2001 (or some other optimal algorithm) to enforce GAC, and the HVE versions use algorithm HAC. Proposition 3.2 In any nonbinary CSP, under a fixed variable and value ordering, algorithm nfci, i= 2,...5, has the same asymptotic cost as algorithm hfci that operates in the hidden variable encoding of the problem. Proof: In Section 3.1 we showed that we can enforce AC on the HVE of a nonbinary CSP with the same worstcase complexity as GAC in the nonbinary representation of the problem. Since algorithm nfci enforces GAC on the same part of the problem on which algorithm hfci enforces AC, and they visit the same nodes of the search tree, it follows that the two algorithm have the same asymptotic cost. In the paper by Bessiére et al. (2002), a detailed discussion on the complexities of algorithms nfc0 nfc5 is made. The worstcase complexity of nfc2 and nfc3 in one node is O( C c,f (k 1)d k 1 ), where C c,f is the number of constraints involving the current variable and at least one future variable. This is also the complexity of hfc3 and hfc4. The worstcase complexity of nfc4 and nfc5 in one node is O( C p,f (k 1)d k 1 ), where C p,f is the number of constraints involving at least one past variable and at least one future variable. This is also the complexity of hfc4 and hfc5. Assuming that nodes(alg i ) is the set of search tree nodes visited by search algorithm alg i then the following holds. Corollary 3.1 Given the hidden variable encoding of a CSP with fixed variable and value ordering schemes, the following relations hold: 1. nodes(hfc1) nodes(hfc0) 2. nodes(hfc2) nodes(hfc1) 3. nodes(hfc5) nodes(hfc3) nodes(hfc2) 4. nodes(hfc5) nodes(hfc4) nodes(hfc2) 5. nodes(mac) nodes(hfc5) Proof: The proof of 1 is straightforward, see the paper by Bacchus & van Beek (1998). Proof of 24 is a straightforward consequence of Proposition 3.1 and Corollary 2 from the paper by Bessiére et al. (2002) where the hierarchy of algorithms nfc0nfc5 in node visits is given. It is easy to see that 5 holds since hfc5 applies AC in only a part of the CSP, while MAC applies it in the whole problem. Therefore, MAC will prune at least as many values as hfc5 at any given node of the search tree. Since the same variable and value ordering heuristics are used, this means that MAC will visit at most the same number of nodes as hfc5. Note that in the paper by Bacchus & van Beek (1998) experimental results show differences between FC in the HVE and FC in the nonbinary representation. However, the 654
15 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results algorithms compared there were FC+ and nfc0, which are not equivalent. Also, it has been proved that hfc0 can have an exponentially greater cost than nfc0, and vice versa (Bacchus et al., 2002). However, these algorithms are not equivalent. As proved in Proposition 3.2, the result of Bacchus et al. (2002) does not hold when comparing equivalent algorithms. So far we have showed that solving a nonbinary CSP directly is in many ways equivalent to solving it using the HVE, assuming that only original variables are instantiated. A natural question is whether there are any search techniques which are inapplicable in the nonbinary case, but can be applied in the encoding. The answer is the ability of a search algorithm that operates on the encoding to instantiate dual variables. In the equivalent nonbinary representation this would imply instantiating values of more than one variables simultaneously. To implement such an algorithm we would have to modify standard search algorithms and heuristics or devise new ones. On the other hand, in the HVE an algorithm that instantiates dual variables can be easily implemented. 4. Algorithms for the Dual Encoding In this section we turn our attention to the DE and describe a specialized AC algorithm with significantly lower complexity than a generic algorithm. 4.1 Arc Consistency We know that AC in the DE is strictly stronger than GAC in the nonbinary representation and AC in the HVE (Stergiou & Walsh, 1999). Since the DE is a binary CSP, one obvious way to apply AC is using a generic AC algorithm. The domain size of a dual variable corresponding to a k ary constraint is d k in the worst case. Therefore, if we apply an optimal AC algorithm then we can enforce AC on one dual constraint with O(d 2k )worstcase complexity. In the DE of a CSP with e constraints of maximum arity k there are at most e(e 1)/2 binary constraints (when all pairs of dual variables share one or more original variables). Therefore, we can enforce AC in the DE of the CSP with O(e 2 d 2k )worstcase complexity. This is significantly more expensive compared to the O(ekd k )complexity bound of GAC in the nonbinary representation and AC in the HVE. Because of the very high complexity bound, AC processing in the DE is considered to be impractical, except perhaps for very tight constraints. However, we will now show that AC can be applied in the DE much more efficiently. To be precise we can enforce AC on the DE of a nonbinary CSP with O(e 3 d k ) worstcase time complexity. The improvement in the asymptotic complexity can be achieved by exploiting the structure of the DE; namely, the fact that the constraints in the DE are piecewise functional. Consider a binary constraint between dual variables v i and v j. We can create a piecewise decomposition of the tuples in the domain of either dual variable into groups such that all tuples in a group are supported by the same group of tuples in the other variable. If the nonbinary constraints corresponding to the two dual variables share f original variables x 1,...,x f of domain size d, then we can partition the tuples of v i and v j into d f groups. Each tuple in a group s includes the same subtuple of the form (a 1,...,a f ), where a 1 D(x 1 ),...,a f D(x f ). Each tuple τ in s will be supported by all tuples in a group s of 655
16 Samaras & Stergiou the other variable, where each tuple in s also includes the subtuple (a 1,...,a f ).The tuples belonging to s will be the only supports of tuple τ since any other tuple does not contain the subtuple (a 1,...,a f ). In other words, a group of tuples s in variable v i will only be supported by a corresponding group s in variable v j where the tuples in both groups have the same values for the original variables that are common to the two encoded nonbinary constraints. Therefore, the constraints in the DE are piecewise functional. Example 4.1 Assume that we have two dual variables v 1 and v 2. v 1 encodes constraint (x 1,x 2,x 3 ), and v 2 encodes constraint (x 1,x 4,x 5 ), where the original variables x 1,...,x 5 have the domain {0, 1, 2}. We can partition the tuples in each dual variable into 3 groups. The first group will include tuples of the form (0,, ), the second will include tuples of the form (1,, ), and the third will include tuples of the form (2,, ). A star ( ) means that the corresponding original variable can take any value. Each group is supported only by the corresponding group in the other variable. Note that the tuples of a variable v i are partitioned in different groups according to each constraint that involves v i. For instance, if there is another dual variable v 3 encoding constraint (x 6,x 7,x 3 ) then the partition of tuples in D(v 1 ) according to the constraint between v 1 and v 3 is into groups of the form (,, 0), (,, 1), (,, 2). Van Hentenryck, Deville & Teng (1992) have shown that AC can be achieved in a set of binary piecewise functional constraints with O(ed) worstcase time complexity, an improvement of O(d) compared to the O(ed 2 ) complexity of arbitrary binary constraints (Van Hentenryck et al., 1992). Since we showed that the constraints in the DE are piecewise functional, the result of Van Hentenryck et al. (1992) means that we can improve on the O(e 2 d 2k ) complexity of AC in the DE. In Figure 4 we sketch an AC3 like AC algorithm specifically designed for the DE, which we call PWAC (PieceWise Arc Consistency). As we will show, this algorithm has a worstcase time complexity of O(e 3 d k ). The same complexity bound can be achieved by the AC5 algorithm of Van Hentenryck et al. (1992), in its specialization to piecewise functional constraints, with the necessary adaptations to operate in the DE. As do most AC algorithms, PWAC uses a stack (or queue) to propagate deletions from the domains of variables. This stack processes groups of piecewise decompositions, instead of variables or constraints as is usual in AC algorithms. We use the following notation: S(v i,v j )={s 1 (v i,v j ),...,s m (v i,v j )} denotes the piecewise decomposition of D(v i ) with respect to the constraint between v i and v j. Each s l (v i,v j ), l =1,...,m,isa group of the partition. sup(s l (v i,v j )) denotes the group of S(v j,v i ) that can support group s l (v i,v j ) of S(v i,v j ). As discussed, this group is unique. counter(s l (v i,v j )) holds the number of valid tuples that belong to group s l (v i,v j )of decomposition S(v i,v j ). That is, at any time the value of counter(s l (v i,v j )) gives the current cardinality of the group. GroupOf(S(v i,v j ),τ) is a function that returns the group of S(v i,v j ) where tuple τ belongs. To implement this function, for each constraint between dual variables v i 656
17 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results function PW AC 1: Q 2: initialize all group counters to 0 3: for each variable v i 4: for each variable v j constrained with v i 5: for each tuple τ D(v i ) 6: counter(groupof(s(v i,v j ),τ)) counter(groupof(s(v i,v j ),τ)) + 1 7: for each variable v i 8: for each variable v j constrained with v i 9: for each group s l (v i,v j ) 10: if counter(s l (v i,v j )) = 0 11: put s l (v i,v j )inq 12: return P ropagation function P ropagation 13: while Q is not empty 14: pop group s l (v i,v j )fromq 15: δ 16: δ Revise(v i,v j,s l (v i,v j )) 17: if D(v j )isemptyreturn INCONSISTENCY 18: for each group s l (v j,v k )inδ put s l (v j,v k )inq 19: return CONSISTENCY function Revise(v i,v j,s l (v i,v j )) 20: for each tuple τ D(v j )whereτ sup(s l (v i,v j )) 21: remove τ from D(v j ) 22: for each group s l (v j,v k ) that includes τ 23: counter(s l (v j,v k )) counter(s l (v j,v k )) 1 24: if counter(s l (v j,v k )) = 0 25: add s l (v j,v k )toδ 26: return δ Figure 4: PWAC. An AC algorithm for the dual encoding. and v j we store the original variables shared by the nonbinary constraints c vi and c vj. Also, for each such original variable x l we store pos(x l,c vi )andpos(x l,c vj ). In this way the GroupOf function takes constant time. The set δ contains the groups that have their counter reduced to 0 after a call to function Revise. That is, groups such that all tuples belonging to them have been deleted. The algorithm works as follows. In an initialization phase, for each group we count the number of tuples it contains (lines 3 6). Then, for each variable v i we iterate over the 657
18 Samaras & Stergiou variables v j that are constrained with v i. For each group s l (v i,v j )ofs(v i,v j ), we check if s l (v i,v j ) is empty or not (line 10). If it is empty, it is added to the stack for propagation. In the next phase, function P ropagation is called to delete unsupported tuples and propagate the deletions (line 12). Once the previous phase has finished, the stack will contain a number of groups with 0 cardinality. For each such group s l (v i,v j )wemust remove all tuples belonging to group sup(s l (v i,v j )) since they have lost their support. This is done by successively removing a group s l (v i,v j ) from the stack and calling function Revise. Since group sup(s l (v i,v j )) has lost its support, each tuple τ D(x j ) that belongs to sup(s l (v i,v j )) is deleted (lines 20 21). Apart from sup(s l (v i,v j )), tuple τ may also belong to other groups that D(v j ) is partitioned in with respect to constraints between v j and other variables. Since τ is deleted, the counters of these groups must be updated (i.e. reduced by one). This is done in lines In the implementation we use function GroupOf to access the relevant groups. If the counter of such a group becomes 0 then the group is added to the stack for propagation (lines and 18). The process stops when either the stack or the domain of a variable becomes empty. In the former case, the DE is AC, while in the latter it is not. The following example illustrates the advantage of algorithm PWAC over both a generic AC algorithm employed in the DE, and AC in the HVE (or GAC in the nonbinary representation). Example 4.2 Consider three constraints c 1, c 2, c 3 as part of a CSP, where vars(c 1 )= {x 0,x 1,x 3 }, vars(c 2 )={x 2,x 3,x 4 }, vars(c 3 )={x 2,x 4,x 5 }. Assume that at some point the domains of the variables in the DE of the problem are as shown in Figure 5 (disregarding the original variables depicted with dashed lines). Assume that we try to enforce AC in the v c1 x x 0 x 1 x 2 x 3 x 4 3 0,0,0 0,0,0 0,1,1 0,1,0 v 0,2,1 c2 0,1,3 0,3,1 1,0,1 1,1,0 1,0,2 1,2,0 1,3,0 x 2 0,1 0,1 x 4 x 2 x 4 x 5 1,0,0 0,1,0 v c3 Figure 5: Dual encoding of a nonbinary CSP. DE using algorithm AC The algorithm will discover that the first tuple in D(v c2 ) has no support in D(v c3 )(thereisnotuplewithx 2 =0andx 4 = 0) and will delete it. Because of this deletion, the first two tuples in D(v c1 ) lose their support in D(v c2 )and AC2001 must therefore look for new supports. For each of the two tuples of D(v c1 )the algorithm will check all the 6 remaining tuples in D(v c2 ) before discovering that there is no support. As a result the two tuples will be deleted. Algorithm PWAC, on the other hand, will set the counter of the group where the first tuple of D(v c2 ) belongs (according to partition S(v c2,v c3 )) to 0 once it deletes the tuple. This will result in a call to function 5. Note that we can construct similar examples for any generic AC algorithm. 658
19 Binary Encodings of Nonbinary CSPs: Algorithms & Experimental Results Revise and an automatic deletion of the first two tuples of D(v c1 ), saving a total of 2 6 checks. Now consider the HVE of the problem. Applying AC on the HVE will have no effect because values 0 and 1 of x 2 and x 4 are both supported in D(v c2 )andd(v c3 ). Therefore there is no propagation through these variables, and as a result the two tuples of D(v c1 ) will not be deleted. Similarly, there will be no propagation if we apply GAC in the nonbinary representation of the problem. Note that the theoretical results regarding the DE presented in the rest of the paper hold if the AC5 algorithm of Van Hentenryck et al. (1992) was adapted and used the DE instead of PWAC. The two algorithms have some similarities (e.g. they both use a function to access the group of a decomposition that a certain tuple belongs to, though implemented differently), but their basic operation is different. The algorithm of Van Hentenryck et al. (1992), being an instantiation of AC5, handles a queue of triples (v i,v j,a) to implement constraint propagation, where v i and v j are two variables involved in a constraint and a is a value that has been removed from D(v j ). PWAC utilizes a queue of piecewise decompositions. Also the data structures used by the algorithms are different. PWAC checks and updates counters to perform the propagation which, as we explain below, requires space exponential in the number of common variables in the nonbinary constraints. The algorithm of Van Hentenryck et al. (1992) utilizes a more complicated data structure which requires space exponential in the arity of the nonbinary constraints. It has to be noted, however, that PWAC is specifically designed for the DE. That is, its operation, data structures, and the way it checks for consistency are based on the fact that the domains of the dual variables consist of the tuples of the original constraints extensionally stored. On the other hand, the algorithm of Van Hentenryck et al. (1992) is generic, in the sense that it can be adapted to operate on any piecewise functional constraint Complexities The PWAC algorithm consists of two phases. In the initialization phase we set up the group counters, and in the main phase we delete unsupported tuples and propagate the deletions. We now analyze the time complexity of PWAC. Note that in our complexity analysis we measure operations, such as incrementing or decrementing a counter, since PWAC does not perform consistency checks in the usual sense. Proposition 4.1 The worstcase time complexity of algorithm PWAC is O(e 3 d k ). Proof: We assume that for any constraint in the dual encoding, the nonbinary constraints corresponding to the two dual variables v i and v j share at most f original variables x 1,...,x f of domain size d. This means that each piecewise decomposition consists of at most d f groups. Obviously, f is equal to k 1, where k is the maximum arity of the constraints. In the initialization phase of lines 3 6 we iterate over all constraints, and for each constraint between variables v i and v j, we iterate over all the tuples in D(v i ). This is done with O(e 2 d k ) asymptotic time complexity. Then, all empty groups are inserted in Q (lines 7 11). This requires e 2 d f operations in the worst case. After the initialization, function P ropagation is called. A group is inserted to Q (and later removed) only when it becomes empty. This means that the while loop of P ropagation is executed at most 659
20 Samaras & Stergiou d f times for each constraint, and at most e 2 d f times in total. This is also the maximum number of times function Revise is called (once in every iteration of the loop). The cost of function Revise is computed as follows: Assuming Revise is called for a group s l (v i,v j ), we iterate over the (at most) d k f tuples of group sup(s l (v i,v j )) (line 20). In each iteration we remove a tuple τ (line 21) and we update the counters of the groups where τ belongs (lines 22 23). There are at most e such groups (in case v j is constrained with all other dual variables). Therefore, each iteration costs O(e), and as a result, each call to Revise costs O(ed k f ). Since Revise is called at most e 2 d f times, the complexity of PWAC, including the initialization step, is O(e 2 d k + e 2 d f + e 2 d f ed k f )=O(e 3 d k ). Note that PWAC can be easily used incrementally during search. In this case, the initialization phase will only be executed once. The asymptotic space complexity of PW AC, and any AC algorithm on a binary encoding, is dominated by the O(ed k ) space need to store the allowed tuples of the nonbinary constraints. Algorithm PWAC also requires O(e 2 d f ) space to store the counters for all the groups, O(e 2 d f ) space for the stack, and O(fe 2 ) space for the fast implementation of function GroupOf. 5. Algorithms for the Double Encoding The double encoding has rarely been used in experiments with binary encodings, although it combines features of the HVE and the DE, and therefore may exploit the advantages of both worlds. To be precise, the double encoding offers the following interesting potential: search algorithms can deploy dynamic variable ordering heuristics to assign values to the original variables, while constraint propagation can be implemented through the constraints between dual variables to achieve higher pruning. In this section we first briefly discuss how AC can be applied in the double encoding. We then show how various search algorithms can be adapted to operate in the double encoding. 5.1 Arc Consistency AC can be enforced on the double encoding using algorithm PWAC with the addition that each time a value a of an original variable x i loses all its supports in an adjacent dual variable, it is deleted from D(x i ). Alternatively, we can use any generic AC algorithm, such as AC Note that an AC algorithm applied in the double encoding can enforce various levels of consistency depending on which constraints it uses for propagation between dual variables. That is, propagation can be either done directly through the constraints between dual variables, or indirectly through the constraints between dual and original variables. For example, if we only use the constraints between dual and original variables then we get the same level of consistency as AC in the HVE. If propagation between dual variables is performed using the constraints of the DE then we get the same level of consistency as AC in the DE, for the dual variables, and we also prune the domains of the original variables. In between, we have the option to use different constraints for propagation in different parts of the problem. As the next example shows, AC in the double encoding can achieve a very high level of consistency compared to the nonbinary representation. In Sections 6.2 and 6.3 we will show that this can have a profound effect in practice. 660
Disjunction of NonBinary and Numeric Constraint Satisfaction Problems
Disjunction of NonBinary and Numeric Constraint Satisfaction Problems Miguel A. Salido, Federico Barber Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia Camino
More informationHeuristics for Dynamically Adapting Constraint Propagation in Constraint Programming
Heuristics for Dynamically Adapting Constraint Propagation in Constraint Programming Kostas Stergiou AI Lab University of the Aegean Greece CPAIOR 09 Workshop on Bound reduction techniques for CP and MINLP
More informationOn the Efficiency of Backtracking Algorithms for Binary Constraint Satisfaction Problems
On the Efficiency of Backtracking Algorithms for Binary Constraint Satisfaction Problems Achref El Mouelhi and Philippe Jégou and Cyril Terrioux LSIS  UMR CNRS 6168 AixMarseille Université Avenue Escadrille
More informationY. Xiang, Constraint Satisfaction Problems
Constraint Satisfaction Problems Objectives Constraint satisfaction problems Backtracking Iterative improvement Constraint propagation Reference Russell & Norvig: Chapter 5. 1 Constraints Constraints are
More informationAnt Colony Optimization and Constraint Programming
Ant Colony Optimization and Constraint Programming Christine Solnon Series Editor Narendra Jussien WILEY Table of Contents Foreword Acknowledgements xi xiii Chapter 1. Introduction 1 1.1. Overview of the
More informationSmart Graphics: Methoden 3 Suche, Constraints
Smart Graphics: Methoden 3 Suche, Constraints Vorlesung Smart Graphics LMU München Medieninformatik Butz/Boring Smart Graphics SS2007 Methoden: Suche 2 Folie 1 Themen heute Suchverfahren Hillclimbing Simulated
More informationEFFICIENT KNOWLEDGE BASE MANAGEMENT IN DCSP
EFFICIENT KNOWLEDGE BASE MANAGEMENT IN DCSP Hong Jiang Mathematics & Computer Science Department, Benedict College, USA jiangh@benedict.edu ABSTRACT DCSP (Distributed Constraint Satisfaction Problem) has
More informationMaintaining Alternative Values in ConstraintBased Configuration
Maintaining Alternative Values in ConstraintBased Configuration Caroline Becker IRIT  University of Toulouse France becker@irit.fr Hélène Fargier IRIT  University of Toulouse France fargier@irit.fr
More informationIntegrating Benders decomposition within Constraint Programming
Integrating Benders decomposition within Constraint Programming Hadrien Cambazard, Narendra Jussien email: {hcambaza,jussien}@emn.fr École des Mines de Nantes, LINA CNRS FRE 2729 4 rue Alfred Kastler BP
More informationSingleLink Failure Detection in AllOptical Networks Using Monitoring Cycles and Paths
SingleLink Failure Detection in AllOptical Networks Using Monitoring Cycles and Paths Satyajeet S. Ahuja, Srinivasan Ramasubramanian, and Marwan Krunz Department of ECE, University of Arizona, Tucson,
More informationThe Constraint Satisfaction Problem and Reformulation Techniques
Reformulating CSPs for Scalability with Application to Geospatial Reasoning Kenneth M. Bayer 1, Martin Michalowski 2, Berthe Y. Choueiry 1,2, Craig A. Knoblock 2 1 Constraint Systems Laboratory, University
More informationA search based Sudoku solver
A search based Sudoku solver Tristan Cazenave Labo IA Dept. Informatique Université Paris 8, 93526, SaintDenis, France, cazenave@ai.univparis8.fr Abstract. Sudoku is a popular puzzle. In this paper we
More informationA Constraint Programming based Column Generation Approach to Nurse Rostering Problems
Abstract A Constraint Programming based Column Generation Approach to Nurse Rostering Problems Fang He and Rong Qu The Automated Scheduling, Optimisation and Planning (ASAP) Group School of Computer Science,
More informationInformation Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay Lecture  17 ShannonFanoElias Coding and Introduction to Arithmetic Coding
More informationComputing Science TRACTABLE BENCHMARKS FOR CONSTRAINT PROGRAMMING. Justyna Petke and Peter Jeavons CSRR0907
Computing Science TRACTABLE BENCHMARKS FOR CONSTRAINT PROGRAMMING Justyna Petke and Peter Jeavons CSRR0907 Oxford University Computing Laboratory Wolfson Building, Parks Road, Oxford OX1 3QD Tractable
More informationRNCodings: New Insights and Some Applications
RNCodings: New Insights and Some Applications Abstract During any composite computation there is a constant need for rounding intermediate results before they can participate in further processing. Recently
More informationAn Improved Algorithm for Maintaining Arc Consistency in Dynamic Constraint Satisfaction Problems
An Improved Algorithm for Maintaining Arc Consistency in Dynamic Constraint Satisfaction Problems Roman Barták Charles University in Prague Malostranské nám. 2/25, Praha 1, Czech Republic roman.bartak@mff.cuni.cz
More informationLinear Codes. Chapter 3. 3.1 Basics
Chapter 3 Linear Codes In order to define codes that we can encode and decode efficiently, we add more structure to the codespace. We shall be mainly interested in linear codes. A linear code of length
More informationApproximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NPCompleteness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithms
More informationComplexity Theory. IE 661: Scheduling Theory Fall 2003 Satyaki Ghosh Dastidar
Complexity Theory IE 661: Scheduling Theory Fall 2003 Satyaki Ghosh Dastidar Outline Goals Computation of Problems Concepts and Definitions Complexity Classes and Problems Polynomial Time Reductions Examples
More informationLoad Balancing. Load Balancing 1 / 24
Load Balancing Backtracking, branch & bound and alphabeta pruning: how to assign work to idle processes without much communication? Additionally for alphabeta pruning: implementing the youngbrotherswait
More informationBounded Treewidth in Knowledge Representation and Reasoning 1
Bounded Treewidth in Knowledge Representation and Reasoning 1 Reinhard Pichler Institut für Informationssysteme Arbeitsbereich DBAI Technische Universität Wien Luminy, October 2010 1 Joint work with G.
More informationLoad Balancing and Switch Scheduling
EE384Y Project Final Report Load Balancing and Switch Scheduling Xiangheng Liu Department of Electrical Engineering Stanford University, Stanford CA 94305 Email: liuxh@systems.stanford.edu Abstract Load
More informationFactoring & Primality
Factoring & Primality Lecturer: Dimitris Papadopoulos In this lecture we will discuss the problem of integer factorization and primality testing, two problems that have been the focus of a great amount
More informationThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE/ACM TRANSACTIONS ON NETWORKING 1 A Greedy Link Scheduler for Wireless Networks With Gaussian MultipleAccess and Broadcast Channels Arun Sridharan, Student Member, IEEE, C Emre Koksal, Member, IEEE,
More informationKNOWLEDGE FACTORING USING NORMALIZATION THEORY
KNOWLEDGE FACTORING USING NORMALIZATION THEORY J. VANTHIENEN M. SNOECK Katholieke Universiteit Leuven Department of Applied Economic Sciences Dekenstraat 2, 3000 Leuven (Belgium) tel. (+32) 16 28 58 09
More informationFinite Domain Bounds Consistency Revisited
Finite Domain Bounds Consistency Revisited C.W. Choi 1, W. Harvey 2, J.H.M. Lee 1, and P.J. Stuckey 3 1 Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T.,
More informationLecture 2: Universality
CS 710: Complexity Theory 1/21/2010 Lecture 2: Universality Instructor: Dieter van Melkebeek Scribe: Tyson Williams In this lecture, we introduce the notion of a universal machine, develop efficient universal
More informationBoundedwidth QBF is PSPACEcomplete
Boundedwidth QBF is PSPACEcomplete Albert Atserias 1 and Sergi Oliva 2 1 Universitat Politècnica de Catalunya Barcelona, Spain atserias@lsi.upc.edu 2 Universitat Politècnica de Catalunya Barcelona, Spain
More informationSudoku as a SAT Problem
Sudoku as a SAT Problem Inês Lynce IST/INESCID, Technical University of Lisbon, Portugal ines@sat.inescid.pt Joël Ouaknine Oxford University Computing Laboratory, UK joel@comlab.ox.ac.uk Abstract Sudoku
More informationA Note on Maximum Independent Sets in Rectangle Intersection Graphs
A Note on Maximum Independent Sets in Rectangle Intersection Graphs Timothy M. Chan School of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1, Canada tmchan@uwaterloo.ca September 12,
More informationDiscrete Optimization
Discrete Optimization [Chen, Batson, Dang: Applied integer Programming] Chapter 3 and 4.14.3 by Johan Högdahl and Victoria Svedberg Seminar 2, 20150331 Todays presentation Chapter 3 Transforms using
More informationMeasuring the Performance of an Agent
25 Measuring the Performance of an Agent The rational agent that we are aiming at should be successful in the task it is performing To assess the success we need to have a performance measure What is rational
More informationChapter 6: Episode discovery process
Chapter 6: Episode discovery process Algorithmic Methods of Data Mining, Fall 2005, Chapter 6: Episode discovery process 1 6. Episode discovery process The knowledge discovery process KDD process of analyzing
More informationSatisfiability Checking
Satisfiability Checking SATSolving Prof. Dr. Erika Ábrahám Theory of Hybrid Systems Informatik 2 WS 10/11 Prof. Dr. Erika Ábrahám  Satisfiability Checking 1 / 40 A basic SAT algorithm Assume the CNF
More informationData Structure [Question Bank]
Unit I (Analysis of Algorithms) 1. What are algorithms and how they are useful? 2. Describe the factor on best algorithms depends on? 3. Differentiate: Correct & Incorrect Algorithms? 4. Write short note:
More informationTesting LTL Formula Translation into Büchi Automata
Testing LTL Formula Translation into Büchi Automata Heikki Tauriainen and Keijo Heljanko Helsinki University of Technology, Laboratory for Theoretical Computer Science, P. O. Box 5400, FIN02015 HUT, Finland
More informationTuring Degrees and Definability of the Jump. Theodore A. Slaman. University of California, Berkeley. CJuly, 2005
Turing Degrees and Definability of the Jump Theodore A. Slaman University of California, Berkeley CJuly, 2005 Outline Lecture 1 Forcing in arithmetic Coding and decoding theorems Automorphisms of countable
More informationThe Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }
More informationCMSC 858T: Randomized Algorithms Spring 2003 Handout 8: The Local Lemma
CMSC 858T: Randomized Algorithms Spring 2003 Handout 8: The Local Lemma Please Note: The references at the end are given for extra reading if you are interested in exploring these ideas further. You are
More informationMathematics for Computer Science/Software Engineering. Notes for the course MSM1F3 Dr. R. A. Wilson
Mathematics for Computer Science/Software Engineering Notes for the course MSM1F3 Dr. R. A. Wilson October 1996 Chapter 1 Logic Lecture no. 1. We introduce the concept of a proposition, which is a statement
More informationBranchandPrice Approach to the Vehicle Routing Problem with Time Windows
TECHNISCHE UNIVERSITEIT EINDHOVEN BranchandPrice Approach to the Vehicle Routing Problem with Time Windows Lloyd A. Fasting May 2014 Supervisors: dr. M. Firat dr.ir. M.A.A. Boon J. van Twist MSc. Contents
More informationPolicy Analysis for Administrative Role Based Access Control without Separate Administration
Policy nalysis for dministrative Role Based ccess Control without Separate dministration Ping Yang Department of Computer Science, State University of New York at Binghamton, US Mikhail I. Gofman Department
More informationFairness in Routing and Load Balancing
Fairness in Routing and Load Balancing Jon Kleinberg Yuval Rabani Éva Tardos Abstract We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteria
More informationUniversity of Potsdam Faculty of Computer Science. Clause Learning in SAT Seminar Automatic Problem Solving WS 2005/06
University of Potsdam Faculty of Computer Science Clause Learning in SAT Seminar Automatic Problem Solving WS 2005/06 Authors: Richard Tichy, Thomas Glase Date: 25th April 2006 Contents 1 Introduction
More informationeach college c i C has a capacity q i  the maximum number of students it will admit
n colleges in a set C, m applicants in a set A, where m is much larger than n. each college c i C has a capacity q i  the maximum number of students it will admit each college c i has a strict order i
More informationGlobally Optimal Crowdsourcing Quality Management
Globally Optimal Crowdsourcing Quality Management Akash Das Sarma Stanford University akashds@stanford.edu Aditya G. Parameswaran University of Illinois (UIUC) adityagp@illinois.edu Jennifer Widom Stanford
More informationDegree Hypergroupoids Associated with Hypergraphs
Filomat 8:1 (014), 119 19 DOI 10.98/FIL1401119F Published by Faculty of Sciences and Mathematics, University of Niš, Serbia Available at: http://www.pmf.ni.ac.rs/filomat Degree Hypergroupoids Associated
More informationTreerepresentation of set families and applications to combinatorial decompositions
Treerepresentation of set families and applications to combinatorial decompositions BinhMinh BuiXuan a, Michel Habib b Michaël Rao c a Department of Informatics, University of Bergen, Norway. buixuan@ii.uib.no
More informationScheduling Home Health Care with Separating Benders Cuts in Decision Diagrams
Scheduling Home Health Care with Separating Benders Cuts in Decision Diagrams André Ciré University of Toronto John Hooker Carnegie Mellon University INFORMS 2014 Home Health Care Home health care delivery
More informationIntroduction to computer science
Introduction to computer science Michael A. Nielsen University of Queensland Goals: 1. Introduce the notion of the computational complexity of a problem, and define the major computational complexity classes.
More informationThe Trip Scheduling Problem
The Trip Scheduling Problem Claudia Archetti Department of Quantitative Methods, University of Brescia Contrada Santa Chiara 50, 25122 Brescia, Italy Martin Savelsbergh School of Industrial and Systems
More informationThe Minimum Consistent Subset Cover Problem and its Applications in Data Mining
The Minimum Consistent Subset Cover Problem and its Applications in Data Mining Byron J Gao 1,2, Martin Ester 1, JinYi Cai 2, Oliver Schulte 1, and Hui Xiong 3 1 School of Computing Science, Simon Fraser
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. #approximation algorithm.
Approximation Algorithms 11 Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of three
More informationWhy? A central concept in Computer Science. Algorithms are ubiquitous.
Analysis of Algorithms: A Brief Introduction Why? A central concept in Computer Science. Algorithms are ubiquitous. Using the Internet (sending email, transferring files, use of search engines, online
More informationnpsolver A SAT Based Solver for Optimization Problems
npsolver A SAT Based Solver for Optimization Problems Norbert Manthey and Peter Steinke Knowledge Representation and Reasoning Group Technische Universität Dresden, 01062 Dresden, Germany peter@janeway.inf.tudresden.de
More informationPropagating Functional Dependencies with Conditions
Propagating Functional Dependencies with Conditions Wenfei Fan 1,2,3 Shuai Ma 1 Yanli Hu 1,5 Jie Liu 4 Yinghui Wu 1 1 University of Edinburgh 2 Bell Laboratories 3 Harbin Institute of Technologies 4 Chinese
More informationThe Basics of Graphical Models
The Basics of Graphical Models David M. Blei Columbia University October 3, 2015 Introduction These notes follow Chapter 2 of An Introduction to Probabilistic Graphical Models by Michael Jordan. Many figures
More informationGlobal Multiprocessor RealTime Scheduling as a Constraint Satisfaction Problem
Global Multiprocessor RealTime Scheduling as a Constraint Satisfaction Problem Liliana CucuGrosean & Olivier Buffet INRIA Nancy GrandEst 615 rue du Jardin Botanique 54600 VillerslèsNancy, France firstname.lastname@loria.fr
More informationA ConstraintBased Method for Project Scheduling with Time Windows
A ConstraintBased Method for Project Scheduling with Time Windows Amedeo Cesta 1 and Angelo Oddi 1 and Stephen F. Smith 2 1 ISTCCNR, National Research Council of Italy Viale Marx 15, I00137 Rome, Italy,
More informationA first step towards modeling semistructured data in hybrid multimodal logic
A first step towards modeling semistructured data in hybrid multimodal logic Nicole Bidoit * Serenella Cerrito ** Virginie Thion * * LRI UMR CNRS 8623, Université Paris 11, Centre d Orsay. ** LaMI UMR
More informationRandom vs. StructureBased Testing of AnswerSet Programs: An Experimental Comparison
Random vs. StructureBased Testing of AnswerSet Programs: An Experimental Comparison Tomi Janhunen 1, Ilkka Niemelä 1, Johannes Oetsch 2, Jörg Pührer 2, and Hans Tompits 2 1 Aalto University, Department
More informationEnergyefficient communication in multiinterface wireless networks
Energyefficient communication in multiinterface wireless networks Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis, and Evi Papaioannou Research Academic Computer Technology Institute
More informationScheduling Shop Scheduling. Tim Nieberg
Scheduling Shop Scheduling Tim Nieberg Shop models: General Introduction Remark: Consider non preemptive problems with regular objectives Notation Shop Problems: m machines, n jobs 1,..., n operations
More informationLecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs
CSE599s: Extremal Combinatorics November 21, 2011 Lecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs Lecturer: Anup Rao 1 An Arithmetic Circuit Lower Bound An arithmetic circuit is just like
More informationDESIGN AND DEVELOPMENT OF CSP TECHNIQUES FOR FINDING ROBUST SOLUTIONS IN JOBSHOP SCHEDULING PROBLEMS WITH OPERATORS
UNIVERSIDAD POLITÉCNICA DE VALENCIA DEPARTAMENTO DE SISTEMAS INFORMÁTICOS Y COMPUTACIÓN DESIGN AND DEVELOPMENT OF CSP TECHNIQUES FOR FINDING ROBUST SOLUTIONS IN JOBSHOP SCHEDULING PROBLEMS WITH OPERATORS
More informationEfficiency of algorithms. Algorithms. Efficiency of algorithms. Binary search and linear search. Best, worst and average case.
Algorithms Efficiency of algorithms Computational resources: time and space Best, worst and average case performance How to compare algorithms: machineindependent measure of efficiency Growth rate Complexity
More informationReliability Guarantees in Automata Based Scheduling for Embedded Control Software
1 Reliability Guarantees in Automata Based Scheduling for Embedded Control Software Santhosh Prabhu, Aritra Hazra, Pallab Dasgupta Department of CSE, IIT Kharagpur West Bengal, India  721302. Email: {santhosh.prabhu,
More informationSolving WCSP by Extraction of Minimal Unsatisfiable Cores
Solving WCSP by Extraction of Minimal Unsatisfiable Cores Christophe Lecoutre Nicolas Paris Olivier Roussel Sébastien Tabary CRIL  CNRS, UMR 8188 Université LilleNord de France, Artois rue de l université,
More informationInteractive Timetabling
Interactive Timetabling Tomáš Müller, Roman Barták * Charles University Department of Theoretical Computer Science Malostranské náměstí 2/25, Praha 1, Czech Republic tomas.muller@st.mff.cuni.cz bartak@kti.mff.cuni.cz
More informationChapter 21: The Discounted Utility Model
Chapter 21: The Discounted Utility Model 21.1: Introduction This is an important chapter in that it introduces, and explores the implications of, an empirically relevant utility function representing intertemporal
More informationCompact Representations and Approximations for Compuation in Games
Compact Representations and Approximations for Compuation in Games Kevin Swersky April 23, 2008 Abstract Compact representations have recently been developed as a way of both encoding the strategic interactions
More informationThe Relative Worst Order Ratio for OnLine Algorithms
The Relative Worst Order Ratio for OnLine Algorithms Joan Boyar 1 and Lene M. Favrholdt 2 1 Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark, joan@imada.sdu.dk
More informationIntroduction to Algorithms. Part 3: P, NP Hard Problems
Introduction to Algorithms Part 3: P, NP Hard Problems 1) Polynomial Time: P and NP 2) NPCompleteness 3) Dealing with Hard Problems 4) Lower Bounds 5) Books c Wayne Goddard, Clemson University, 2004 Chapter
More informationChapter ML:IV. IV. Statistical Learning. Probability Basics Bayes Classification Maximum aposteriori Hypotheses
Chapter ML:IV IV. Statistical Learning Probability Basics Bayes Classification Maximum aposteriori Hypotheses ML:IV1 Statistical Learning STEIN 20052015 Area Overview Mathematics Statistics...... Stochastics
More informationGenerating models of a matched formula with a polynomial delay
Generating models of a matched formula with a polynomial delay Petr Savicky Institute of Computer Science, Academy of Sciences of Czech Republic, Pod Vodárenskou Věží 2, 182 07 Praha 8, Czech Republic
More informationDistributed Computing over Communication Networks: Maximal Independent Set
Distributed Computing over Communication Networks: Maximal Independent Set What is a MIS? MIS An independent set (IS) of an undirected graph is a subset U of nodes such that no two nodes in U are adjacent.
More informationscheduling maintenance of electric power units Daniel Frost and Rina Dechter ffrost, dechterg@ics.uci.edu Abstract
Optimizing with constraints: a case study in scheduling maintenance of electric power units Daniel Frost and Rina Dechter Dept. of Information and Computer Science, University of California, Irvine, CA
More informationChapter 11. 11.1 Load Balancing. Approximation Algorithms. Load Balancing. Load Balancing on 2 Machines. Load Balancing: Greedy Scheduling
Approximation Algorithms Chapter Approximation Algorithms Q. Suppose I need to solve an NPhard problem. What should I do? A. Theory says you're unlikely to find a polytime algorithm. Must sacrifice one
More informationMultilayer Structure of Data Center Based on Steiner Triple System
Journal of Computational Information Systems 9: 11 (2013) 4371 4378 Available at http://www.jofcis.com Multilayer Structure of Data Center Based on Steiner Triple System Jianfei ZHANG 1, Zhiyi FANG 1,
More informationThe UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge,
The UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge, cheapest first, we had to determine whether its two endpoints
More informationSimulationBased Security with Inexhaustible Interactive Turing Machines
SimulationBased Security with Inexhaustible Interactive Turing Machines Ralf Küsters Institut für Informatik ChristianAlbrechtsUniversität zu Kiel 24098 Kiel, Germany kuesters@ti.informatik.unikiel.de
More informationTHE SEARCH FOR NATURAL DEFINABILITY IN THE TURING DEGREES
THE SEARCH FOR NATURAL DEFINABILITY IN THE TURING DEGREES ANDREW E.M. LEWIS 1. Introduction This will be a course on the Turing degrees. We shall assume very little background knowledge: familiarity with
More informationINTEGER PROGRAMMING. Integer Programming. Prototype example. BIP model. BIP models
Integer Programming INTEGER PROGRAMMING In many problems the decision variables must have integer values. Example: assign people, machines, and vehicles to activities in integer quantities. If this is
More informationIntegration of ACO in a Constraint Programming Language
Integration of ACO in a Constraint Programming Language Madjid Khichane 12, Patrick Albert 1, and Christine Solnon 2 1 ILOG 2 LIRIS, UMR 5205 CNRS / University of Lyon ANTS 08 Motivations Ant Colony Optimization
More informationConstraint Optimization for Highly Constrained Logistic Problems
Constraint Optimization for Highly Constrained Logistic Problems Maria Kinga Mochnacs Meang Akira Tanaka Anders Nyborg Rune Møller Jensen IT University Technical Report Series TR20072008104 ISSN 1600
More informationOHJ2306 Introduction to Theoretical Computer Science, Fall 2012 8.11.2012
276 The P vs. NP problem is a major unsolved problem in computer science It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a $ 1,000,000 prize for the
More informationTypes of Degrees in Bipolar Fuzzy Graphs
pplied Mathematical Sciences, Vol. 7, 2013, no. 98, 48574866 HIKRI Ltd, www.mhikari.com http://dx.doi.org/10.12988/ams.2013.37389 Types of Degrees in Bipolar Fuzzy Graphs Basheer hamed Mohideen Department
More informationComputational Methods for Database Repair by Signed Formulae
Computational Methods for Database Repair by Signed Formulae Ofer Arieli (oarieli@mta.ac.il) Department of Computer Science, The Academic College of TelAviv, 4 Antokolski street, TelAviv 61161, Israel.
More informationScheduling Realtime Tasks: Algorithms and Complexity
Scheduling Realtime Tasks: Algorithms and Complexity Sanjoy Baruah The University of North Carolina at Chapel Hill Email: baruah@cs.unc.edu Joël Goossens Université Libre de Bruxelles Email: joel.goossens@ulb.ac.be
More informationTHE last two decades have witnessed an exponential
IEEE JSAC  SAMPLING 2006 1 Practical Beacon Placement for Link Monitoring Using Network Tomography Ritesh Kumar and Jasleen Kaur Abstract Recent interest in using tomography for network monitoring has
More informationBig Data & Scripting Part II Streaming Algorithms
Big Data & Scripting Part II Streaming Algorithms 1, Counting Distinct Elements 2, 3, counting distinct elements problem formalization input: stream of elements o from some universe U e.g. ids from a set
More informationAnalysis of Algorithms I: Binary Search Trees
Analysis of Algorithms I: Binary Search Trees Xi Chen Columbia University Hash table: A data structure that maintains a subset of keys from a universe set U = {0, 1,..., p 1} and supports all three dictionary
More informationArtificial Intelligence
Artificial Intelligence ICS461 Fall 2010 1 Lecture #12B More Representations Outline Logics Rules Frames Nancy E. Reed nreed@hawaii.edu 2 Representation Agents deal with knowledge (data) Facts (believe
More informationVisualization for Structured Constraint Satisfaction Problems
Visualization for Structured Constraint Satisfaction Problems Xingjian Li and Susan L. Epstein,2 Department of Computer Science The Graduate Center and 2 Hunter College of The City University of New York
More informationSchool Timetabling in Theory and Practice
School Timetabling in Theory and Practice Irving van Heuven van Staereling VU University, Amsterdam Faculty of Sciences December 24, 2012 Preface At almost every secondary school and university, some
More informationHow To Solve The Stable Roommates Problem
THE ROOMMATES PROBLEM DISCUSSED NATHAN SCHULZ Abstract. The stable roommates problem as originally posed by Gale and Shapley [1] in 1962 involves a single set of even cardinality 2n, each member of which
More informationDiscuss the size of the instance for the minimum spanning tree problem.
3.1 Algorithm complexity The algorithms A, B are given. The former has complexity O(n 2 ), the latter O(2 n ), where n is the size of the instance. Let n A 0 be the size of the largest instance that can
More informationAnalysis of Algorithms I: Optimal Binary Search Trees
Analysis of Algorithms I: Optimal Binary Search Trees Xi Chen Columbia University Given a set of n keys K = {k 1,..., k n } in sorted order: k 1 < k 2 < < k n we wish to build an optimal binary search
More informationCost Models for Vehicle Routing Problems. 8850 Stanford Boulevard, Suite 260 R. H. Smith School of Business
0769514359/02 $17.00 (c) 2002 IEEE 1 Cost Models for Vehicle Routing Problems John Sniezek Lawerence Bodin RouteSmart Technologies Decision and Information Technologies 8850 Stanford Boulevard, Suite
More information