--- title: "Reasoning about NP-complete Constraints" authors: - "Emmanuel Hebrard" doi: "10.24963/ijcai.2018/807" url: "https://ijcai.org/proceedings/2018/807" pdf: "https://ijcai.org/proceedings/2018/0807.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "5672-5676" track: "Early Career" keywords: - "Constraints and SAT: Constraint Satisfaction" - "Knowledge Representation and Reasoning: Computational Complexity of Reasoning" - "Constraints and SAT: Global Constraints" --- # Reasoning about NP-complete Constraints Emmanuel Hebrard *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 5672-5676. DOI: [10.24963/ijcai.2018/807](https://doi.org/10.24963/ijcai.2018/807) ## Abstract The concept of local consistency – making global deductions from local infeasibility – is central to constraint programming. When reasoning about NP-complete constraints, however, since achieving a ``complete'' form of local consistency is often considered too hard, we need other tools to design and analyze propagation algorithms. In this paper, we argue that NP-complete constraints are an essential part of constraint programming, that designing dedicated methods has lead to, and will bring, significant breakthroughs, and that we need to carefully investigate methods to deal about a necessarily incomplete inference. In particular, we advocate the use of fixed-parameter tractability and kernelization to this purpose. ## Full text ## 1 Introduction Constraint programming (CP) has been a very successful framework for modeling and solving hard combinatorial problems. Many problems are naturally framed as constraint satisfaction or optimization problems, where a set of discrete valued variables is to be assigned while satisfying a set of constraints. For instance, CP has been successfully applied to managing the aftermath of natural disasters [Hentenryck, 2013], optimizing the delivery of radiotherapy in cancer treatment [Cambazard et al., 2012] or scheduling the exploration of a comet [Simonin et al., 2012]. A first strength of CP often put forward, is its declarative aspect. Another essential feature is the modularity and versatility of the inference mechanisms. The key principle is the notion of local consistency: if we can deduce that some assignments are locally infeasible, for instance with respect to a single constraint, then the same deduction holds globally. In particular, a constraint network is said domain 1 consistent [Waltz, 1975] when there is no further deduction to be made, with respect to any single constraint, about the possible values that its variables can take. It was shown that maintaining this level of consistency during search was often a good choice [Sabin and Freuder, 1994] and most constraint solvers are designed according to this principle. 1 Or equivalently arc consistent The notion of global constraint makes this type of reasoning extremely powerful. A constraint is said global when it corresponds to a class of relations on an arbitrary number of variables. For instance, the constraint ALLDIFFERENT ensures that a set of variables take all pairwise distinct values. Given a recurring subproblem for which there exists an efficient algorithm, it is natural to derive the corresponding constraint, that is, design a propagation algorithm responsible for making deduction locally to that constraint. For instance, the propagation algorithm for the ALLDIFFERENT constraint [R´egin, 1994] is based on Hopcroft and Karp's maximum matching algorithm [Hopcroft and Karp, 1973]. Similarly, a number of constraints are propagated using results from flow theory [van Hoeve et al., 2006] or dynamic programming [Pesant, 2004; Hebrard et al., 2009]. Since constraints must be easily checkable, they lie within the complexity class NP. However, many recurring subproblems that might qualify as constraints are NPcomplete [Bessiere et al., 2006b]. Examples of NP-complete constraints are numerous. For instance for ensuring that a set of Boolean variables represent a clique of a certain size [Fahle, 2002; R´egin, 2003]; that integer variables representing vertices of a graph are given a value corresponding to an isomorphic vertex in a larger graph [R´egin, 1995]; that the least and highest number of occurrences of any value is within some bounds [Schaus et al., 2007]; that two overlapping sets of variables both have all pairwise distinct values [Kutz et al., 2008]; that there is an upper bound on the cardinality of the set of assigned values [Bessiere et al., 2006a]; that a sequence of variables encode the successors of an Hamiltonian circuit of bounded length in a graph [Ducomman et al., 2016]; or that a set of tasks share a disjunctive [Baptiste and Le Pape, 1995] or cumulative resource [Baptiste and Le Pape, 1997]. However, whereas one can enforce domain consistency on polynomial constraints, it is often necessary to find a compromise between inference strength and computational effort on NP-complete constraints. In this paper, we advocate the design of propagation algorithms for NP-complete constraints. Furthermore, we argue that there is a need for a theoretical characterization of the consistency enforced by these algorithms. We show that fixed-parameter tractability [Downey et al., 1999], and in particular the notion of kernel are extremely relevant in this context and that the latter can be extended to fill this role of measure of propagation strength. ## 2 NP-complete Constraints A constraint network is a triple (X, U, C) where X is a totally ordered set of variables, the universe U is a finite set of values and C is a set of constraints. A constraint C is a pair (SC,RC) where the scope SC is a subset of X and RC is a relation on U of arity |SC|. The Constraint Satisfaction Problem (CSP) asks whether a constraint network (X, U, C) has a solution, that is, a |X|-tuple σ ∈ U |X| such that for each C ∈ C, the projection σ(SC) of σ onto SC is in RC. A global constraint is a class of relations, one for each possible value of its parameters. The most common parameter is the number of constrained variables. For instance we can define the NVALUE [Pachet and Roy, 1999] constraint with one relation per integer n given by the following predicate: Definition 1 (NVALUE). During search, in order to store the decisions and deductions, we use a special type of relation over X , the domain D. There is not a unique type of relation used for that purpose, for instance the search space can be encoded as a Boolean Decision Diagram [Hadzic and Hooker, 2007]. However we consider here the canonical finite discrete domain where the D relation is restricted to conjunctions of finite unary relations, one for every variable x ∈ X , which we denote D(x). We write D′ ⊆ D as a shortcut for ∀x ∈ X D′ (x) ⊆ D(x). Definition 2. A constraint C is said domain consistent on a finite discrete domain D if and only if The problem of achieving domain consistency of a domain D with respect to a constraint C consists in finding the largest domain D′ ⊆ D such that C is arc consistent on D′ . There is a unique largest arc consistent closure of a finite discrete domain D with respect to a constraint C. Notice that achieving domain consistency is polynomially reducible to checking the satisfiability of a constraint, i.e., finding a tuple τ ∈ D ∩ C. Given an algorithm for checking satisfiability, for every variable x and every value v ∈ D(x) one can check the satisfiability of C w.r.t. D′ where D′ (x) = {v} and D′ = D otherwise. If the constraint is not satisfiable, then the domain consistent closure of D is such that v ̸∈ D(x) and we can change D accordingly. Otherwise the domain consistent closure is such that v ∈ D(x) and we leave D unchanged. This procedure terminates after ∑x∈SC |D(x)| steps. The converse is trivial, since a constraint is satisfiable if and only if its domain consistent closure is not empty. We therefore say that a constraint is NP-complete if checking its satisfiability is NP-complete, even though achieving domain consistency is not a decision problem. The constraint NVALUE is NP-complete since checking if there exists a tuple in a domain D such that |{τ(xi) | 1 ≤ i ≤ n}| ≤ y is equivalent to finding a hitting set of the collection {D(x1), . . . ,D(xn)} of size maxD(y) [Bessiere et al., 2006a]. Therefore, achieving the domain consistent closure is often considered too costly for this constraint. For NVALUE and other NP-complete constraints incomplete approaches are used instead. Relaxing the domain: A common way to reduce the complexity of propagating a constraint is to relax the domain relation D. For instance, the notion of bounds consistency is widely used in this situation. Let interval domains be the class of relations restricted to conjunctions of finite unary relations, one for every variable x ∈ X , of the form l ≤ x ≤ u. Bounds consistency is the property obtained by applying Definition 2 to interval, instead of discrete, domains. The hitting set problem has a polynomial algorithm when the sets are discrete intervals. Therefore, the relaxtion from finite discrete domains to interval domains make satisfiability checking and thus bounds consistency polynomial. The best algorithm achieves both in O(|X| log |X|) [Beldiceanu, 2001]. This is true for many NP-complete global constraints. For instance the constraint GCC, which channels the number of occurrences of values in a set of variables X to another set of variables Y is NP-complete for discrete domains [Quimper et al., 2004], but polynomial if the domain relation is relaxed to intervals for the variables Y [R´egin, 1996]. Decomposing the constraint: Another common way to deal with NP-completeness is to decompose the constraint. A constraint network I = (X,D, C) is a decomposition of a constraint C if and only if SC ⊆ X and σ is a solution of I if and only if σ(SC) ∈ RC. In other words, it is a constraint network on a superset of SC such that its set of solutions, when projected onto SC is exactly the set of tuples in RC. Decompositions are used in countless constraint programming approaches. A lot of effort has been put into the study of decompositions and in particular when it is or when it is not possible to emulate algorithms through decompositions, both for polynomial and NP-complete constraints [Narodytska, 2011]. For instance, it was shown that propagation algorithms for the NVALUE constraint can be emulated for the same time complexity, however at the cost of a much higher space complexity [Bessiere et al., 2010]. Moreover, decompositions are sometimes used as a way to relax the problem of achieving the domain consistent closure, even though an efficient dedicated algorithm is then proposed to compute the closure. For instance the O(n logn) "Timetabling" method for reasoning about a set of n tasks consumming energy from a cumulative resource [Le Pape, 1988; Beldiceanu and Carlsson, 2001] over time can be seen as achieving bounds consistency on a decomposition involving Boolean variables xij standing for whether task i is processed at time j, however with a far lower time complexity. Similarly, "Edge Finding" algorithms [Nuijten and Aarts, 1994; Vil´ım, 2009] achieve bounds consistency (in polynomial time) on a decomposition (of exponential size). Lastly, Ouellet and Quimper's algorithm [Ouellet and Quimper, 2013] achieves bounds consistency on the conjunction of these two decompositions in O(kn logn) time with k the number of different tasks' consumptions. Approximation: Often, NP-complete constraints on a set of variables X can be easily seen as enforcing that an |X|-ary cost function π : D|X| ↦→ Q ∪ {∞,-∞} is non-positive. 2 For instance, the constraint NVALUE corresponds to the following cost function: |{xi | 1 ≤ i ≤ n}|-y. The intersection graph of {D(x1), . . . , D(xn)} is the graph with one vertex vi for i ∈ [1, n] and an edge (vi, vj) iff D(xi)∩D(xj) ̸= ∅. The independence number of this graph is larger than or equal to the minimum hitting set of the collection. Therefore, this is a valid upper lower bound for y [Bessiere et al., 2006a]. In this case, the approximation offers no guarantee, yet it is a relatively effective method in practice, often outperforming the bounds consistency approach. 2 This is not restrictive as any relation maps tuples to 0/1. More generally, when a method with a guaranteed approximation ratio exists for a cost function π, this method provides both a primal and a dual bound which is extremely valuable. In general, however, approximation results are still largely underused within the context of constraint propagation. ## 3 Propagation via Kernels The complexity of a problem can be more finely characterized by considering parameters besides the size of the input. Parameterized complexity aims at understanding which parameters are relevant to explain the hardness of a problem. Given a problem P and a parameter p, (P, p) is in the FPT class if there exists an algorithm that can decide an instance I of P in time f(p)|I|O(1) where f is a computable function. A previous study [Bessiere et al., 2008] of the parameterized complexity of global constraints, and of their relevant parameters, showed that this approach was promising. In particular, the NVALUE constraint is FPT when the parameter is the number of "holes" in the domains [Bessiere et al., 2008]. Moreover, it is often possible to compute kernels of FPT problems, which are extremely relevant in this context. Definition 3. A kernelization for a problem P and a parameter p is a polynomial-time computable function that maps each instance x and parameter value k to an instance x′ and parameter k′ of the same problem such that x is a yesinstance if and only x′ is, |x′ | ≤ f(k), and k′ ≤ g(k) for some computable functions f, g. There is intense research both on FPT algorithms and kernelization methods [Cygan et al., 2015]. Characterizing a kernel is a very significant step in understanding the combinatorial structure and efficiently reasoning about a constraint. Intuitively, the difference between the original instance and the kernel is composed of inconsistent (or entailed) values. Consider for instance the vertex cover problem, asking whether there is a subset of at most k vertices of a graph G, such that every edge has at least one extremity in the cover. The Buss rule consists in adding vertices of degree k+1 to the cover, since otherwise their neighbors would be in the cover. This very simple propagation rule yields a kernel of size k2 . However, classical kernels are not always correct propagation. For instance, the smallest kernels for the vertex cover problem [Abu-Khzam et al., 2007; Nemhauser and Trotter Jr, 1975] are based on crown decompositions of the graph. Definition 4. A crown decomposition of a graph G is a partition (H,W, I) of V such that vertices in I have an edge only with vertices in W and there is a matching of size |W| between W and I. The size of a vertex cover can never be increased by removing all vertices from I and adding all vertices from W. However, this is a correct dominance rule, but not a correct propagation rule: feasible or even minimal solutions might involve vertices from I. Similarly, an efficient kernelization using dominance was proposed for the NVALUE constraint [Gaspers and Szeider, 2011]. For the same reason, this method is to be used within the probing procedure described in Section 2 to achieve domain consistency through satisfiability checks: for every variable-value pair, the problem of deciding if the constraint is satisfiable when restricting the domain accordingly is solved on the kernel. In other words, several exponential satisfiability checks have to be performed. In [Carbonnel and Hebrard, 2016; 2017] we proposed an approach to propagating NP-complete constraints based on a new definition of "loss-less" kernelization tailored for constraint propagation. Intuitively, z-loss-less kernels are kernels with an extra loss-lessness property: Whereas solving a classical kernel is sufficient to solve the original instance, achieving domain consistency on a loss-less kernel is sufficient to achieve domain consistency on the original instance. In other words, there exists a polynomial algorithm, which, given the domain consistent closure of the loss-less kernel, computes it for the original instance. This is much more consistent with the spirit of kernelization, extends smoothly constraints with polynomial-time propagators and yields a propagation algorithm with running time O(g(p) + |I|O(1) pO(1) ), instead of O(|I|O(1) g(p)) for probing plus classical kernelization. There is caveat, however. Consider again constraints defined as minimizing a cost function, for instance the NVALUE constraint which ensures that the cardinality of the set of values taken by the variables x1, . . . , xn is at most y. As long as the domain of y contains high values, the constraint is unlikely to propagate much. In fact, if n ∈ D(y) then the constraint is completely inoperant. More generally, kernels whose size decrease when the constraint get tighter should be priotirized since they are the most useful with respect to propagation. When defining constraints as minimizing a cost function such as the NVALUE constraint, the tightness is very clearly related to the gap z from 0 to the minimum of πD(X) under the current domain D. We therefore use this extra parameter z in the definition of loss-less kernels: Definition 5. Let Π be a set of cost functions, and C a global constraint defined as the relations π(X) ≤ 0 for π ∈ Π. A z-loss-less kernelization of C with parameter p is a polynomial-time computable function mapping each instance (π,X,D) and parameter value k to an instance (π′ ,X ′ ,D′ ) and parameter k′ of the same constraint such that if -min(πD(X)) ≤ z, then there is a polynomial algorithm achieving domain consistenty of D w.r.t. π(X) ≤ 0 given the the domain consistent closure of D′ w.r.t. π′ (X ′ ) ≤ 0, |π′ | + |D′ | + |X ′ | ≤ f(k), and k′ ≤ g(k) for some computable functions f, g. The results in [Carbonnel and Hebrard, 2017] show that loss-less kernels exist: There is a (z + 2)k z-loss-less kernel for the vertex cover problem parameterized by the size k of the cover, thus matching the result of Nemhauser [Nemhauser and Trotter Jr, 1975] for z = 0.Similarly, there is a ∞-lossless kernel max(6k, k2 /2 + 7k/2) kernel for the edge dominating set parameterized by the size of the dominating set, thus matching the result of Hagerup [Hagerup, 2012]. Moreover, they are not mere theoretical curiosities: kernelbased propagation was successfully applied to a constrained vertex cover problem [Carbonnel and Hebrard, 2016]. ## 4 Conclusions In this paper we have surveyed different approaches to propagating NP-complete constraints and argued that designing dedicated methods is extremely valuable. Moreover, among the possible ways of tackling the propagation of NP-complete constraints (approximation, relaxation, decomposition, etc.) we argue that fixed parameterized complexity and in particular kernelization offers several extremely relevant features: Firstly, the value of the parameter, as well as the size of the gap z, changes during search. Therefore, it is possible to target when kernelization is most likely to being beneficial and thus use it in an opportunistic way. Secondly, loss-less kernels are designed to achieve domain consistency of the full instance with a single call to a possibly exponential algorithm to compute the closure of the kernel. However, in practice, the kernelization procedure in itself makes some incomplete inference while being polynomial. The kernelization process in itself can therefore be used as a polynomial propagation procedure. Finally, the guarantee on the size of the kernels entails a guarantee on the strength of this inference. In other words, the size of the kernel is a valuable criterion to compare the achieved level of consistency. ## References 1. [Abu-Khzam et al., 2007] Faisal N Abu-Khzam, Michael R Fellows, Michael A Langston, and W Henry Suters. Crown Structures for Vertex Cover Kernelization. Theory of Computing Systems, 41(3):411-430, 2007. 2. [Baptiste and Le Pape, 1995] Philippe Baptiste and Claude Le Pape. A Theoretical and Experimental Compari- son of Constraint Propagation Techniques for Disjunc- tive Scheduling. In Proceedings of the 14th International Joint Conference on Artificial Intelligence, pages 600- 606, 1995. 3. [Baptiste and Le Pape, 1997] Philippe Baptiste and Claude Le Pape. Constraint propagation and decomposition tech- niques for highly disjunctive and highly cumulative project scheduling problems. In Proceedings of the 3rd Inter- national Conference on Principles and Practice of Con- straint Programming, pages 375-389, 1997. 4. [Beldiceanu and Carlsson, 2001] Nicolas Beldiceanu and Mats Carlsson. Sweep as a Generic Pruning Technique Applied to the Non-overlapping Rectangles Constraint. In Proceedings of the 7th International Conference on Prin- ciples and Practice of Constraint Programming, pages 377-391, 2001. 5. [Beldiceanu, 2001] Nicolas Beldiceanu. Pruning for the Minimum Constraint Family and for the Number of Dis- tinct Values Constraint Family. In Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, pages 211-224, 2001. 6. [Bessiere et al., 2006a] Christian Bessiere, Emmanuel He- brard, Brahim Hnich, Zeynep Kiziltan, and Toby Walsh. Filtering Algorithms for the NValue Constraint. Con- straints, 11(4):271-293, 2006. 7. [Bessiere et al., 2006b] Christian Bessiere, Emmanuel He- brard, Brahim Hnich, and Toby Walsh. The Complex- ity of Reasoning with Global Constraints. Constraints, 12(2):239-259, 2006. 8. [Bessiere et al., 2008] Christian Bessiere, Emmanuel He- brard, Brahim Hnich, Zeynep Kiziltan, Claude-Guy Quim- per, and Toby Walsh. The Parameterized Complexity of Global Constraints. In Proceedings of the 23rd Na- tional Conference on Artificial Intelligence, pages 235- 240, 2008. 9. [Bessiere et al., 2010] Christian Bessiere, George Katsire- los, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Decomposition of the NValue Constraint. In Pro- ceedings of the 16th International Conference on Princi- ples and Practice of Constraint Programming, pages 114- 128, 2010. 10. [Cambazard et al., 2012] Hadrien Cambazard, Eoin O'Mahony, and Barry O'Sullivan. A Shortest Path- based Approach to the Multileaf Collimator Sequencing Problem. Discrete Applied Mathematics, 160(1-2):81-99, 2012. 11. [Carbonnel and Hebrard, 2016] Clément Carbonnel and Em- manuel Hebrard. Propagation via Kernelization: the Ver- tex Cover Constraint. In Proceedings of the 22nd Inter- national Conference on Principles and Practice of Con- straint Programming, pages 147-156, 2016. 12. [Carbonnel and Hebrard, 2017] Clément Carbonnel and Em- manuel Hebrard. On the kernelization of global con- straints. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 578-584, 2017. 13. [Cygan et al., 2015] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parame- terized algorithms. Springer, 2015. 14. [Downey et al., 1999] Rod G. Downey, Michael R. Fellows, and Ulrike Stege. Parameterized Ccomplexity: A Frame- work for Systematically Confronting Computational In- tractability. Contemporary Trends in Discrete Mathemat- ics: From DIMACS and DIMATIA to the Future, pages 49-99, 1999. 15. [Ducomman et al., 2016] Sylvain Ducomman, Hadrien Cambazard, and Bernard Penz. Alternative Filtering for the Weighted Circuit Constraint: Comparing Lower Bounds for the TSP and Solving TSPTW. In Proceedings of the 30th National Conference on Artificial Intelligence, pages 3390-3396, 2016. 16. [Fahle, 2002] Thorsten Fahle. Integrating concepts from constraint programming and operations research algo- rithms. PhD thesis, University of Paderborn, 2002. 17. [Gaspers and Szeider, 2011] Serge Gaspers and Stefan Szei- der. Kernels for Global Constraints. In Proceedings of the 22nd International Joint Conference on Artificial Intelli- gence, pages 540-545, 2011. 18. [Hadzic and Hooker, 2007] Tarik Hadzic and John N. Hooker. Cost-Bounded Binary Decision Diagrams for 0-1 Programming. In Proceedings of the 4th International Conference on Integration of AI and OR Techniques in CP, pages 84-98, 2007. 19. [Hagerup, 2012] Torben Hagerup. Kernels for Edge Domi- nating Set: Simpler or Smaller. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, pages 491-502, 2012. 20. [Hebrard et al., 2009] Emmanuel Hebrard, Daniel Marx, Barry O'Sullivan, and Igor Razgon. Constraints of Dif- ference and Equality: A Complete Taxonomic Character- isation. In Proceedings of the 15th International Confer- ence on Principles and Practice of Constraint Program- ming, pages 424-438, 2009. 21. [Hentenryck, 2013] Pascal Van Hentenryck. Computational Disaster Management. In Proceedings of the 23rd Inter- national Joint Conference on Artificial Intelligence, 2013. 22. [Hopcroft and Karp, 1973] John E. Hopcroft and Richard M. Karp. An n 5/2 Algorithm for Maximum Matchings in Bi- partite Graphs. SIAM J. Comput., 2(4):225-231, 1973. 23. [Kutz et al., 2008] Martin Kutz, Khaled M. Elbassioni, Irit Katriel, and Meena Mahajan. Simultaneous matchings: Hardness and approximation. J. Comput. Syst. Sci., 74(5):884-897, 2008. 24. [Le Pape, 1988] Claude Le Pape. Des systèmes d'ordonnancement flexibles et opportunistes. PhD thesis, Université Paris XI, 1988. 25. [Narodytska, 2011] Nina Narodytska. Reformulation of global constraints. PhD thesis, University of New South Wales, Sydney, Australia, 2011. 26. [Nemhauser and Trotter Jr, 1975] George L Nemhauser and Leslie E Trotter Jr. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1):232- 248, 1975. 27. [Nuijten and Aarts, 1994] Wim Nuijten and Emile Aarts. Constraint satisfaction for multiple capacitated job shop scheduling. In Proceedings of the 11th European Confer- ence on Artificial Intelligence, pages 635-639, 1994. 28. [Ouellet and Quimper, 2013] Pierre Ouellet and Claude-Guy Quimper. Time-Table Extended-Edge-Finding for the Cu- mulative Constraint. In Proceedings of the 19th Inter- national Conference on Principles and Practice of Con- straint Programming, pages 562-577, 2013. 29. [Pachet and Roy, 1999] Franc ¸ois Pachet and Pierre Roy. Au- tomatic Generation of Music Programs. In Proceedings of the 5th International Conference on Principles and Prac- tice of Constraint Programming, pages 331-345, 1999. 30. [Pesant, 2004] G. Pesant. A Regular Language Membership Constraint for Finite Sequences of Variables. In Proceed- ings of the 10th International Conference on Principles and Practice of Constraint Programming, pages 482-495, 2004. 31. [Quimper et al., 2004] Claude-Guy Quimper, Alejandro López-Ortiz, Peter van Beek, and Alexander Golyn- ski. Improved Algorithms for the Global Cardinality Constraint. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, pages 542-556, 2004. 32. [Régin, 1994] Jean-Charles Régin. A Filtering Algorithm for Constraints of Difference in CSPs. In Proceedings of the 12th National Conference on Artificial Intelligence, pages 362-367, 1994. 33. [Régin, 1995] Jean-Charles Régin. Développement d'outils algorithmiques pour l'Intelligence Artificielle. Application à la chimie organique. PhD thesis, Université Montpellier II, 1995. 34. [Régin, 1996] Jean-Charles Régin. Generalized Arc Consis- tency for Global Cardinality Constraint. In Proceedings of the 13th National Conference on Artificial Intelligence, pages 209-215, 1996. 35. [Régin, 2003] Jean-Charles Régin. Using Constraint Pro- gramming to Solve the Maximum Clique Problem. In Pro- ceedings of the 9th International Conference on Principles and Practice of Constraint Programming, pages 634-648, 2003. 36. [Sabin and Freuder, 1994] Daniel Sabin and Eugene C. Freuder. Contradicting conventional wisdom in constraint satisfaction. In Alan Borning, editor, Proceedings of the 2nd Workshop on Principles and Practice of Constraint Programming, pages 10-20, 1994. 37. [Schaus et al., 2007] Pierre Schaus, Yves Deville, and Pierre Dupont. Bound-Consistent Deviation Constraint. In Pro- ceedings of the 13th International Conference on Princi- ples and Practice of Constraint Programming, pages 620- 634, 2007. 38. [Simonin et al., 2012] Gilles Simonin, Christian Artigues, Emmanuel Hebrard, and Pierre Lopez. Scheduling Scien- tific Experiments on the Rosetta/Philae Mission. In Pro- ceedings of the 18th International Conference on Princi- ples and Practice of Constraint Programming, pages 23- 37, 2012. 39. [van Hoeve et al., 2006] Willem-Jan van Hoeve, Gilles Pe- sant, and Louis-Martin Rousseau. On Global Warming: Flow-Based Soft Global Constraints. Journal of Heuris- tics, 12(4-5):347-373, 2006. 40. [Vilím, 2009] Petr Vilím. Max Energy Filtering Algorithm for Discrete Cumulative Resources. In Proceedings of the 6th International Conference on Integration of AI and OR Techniques in CP, pages 294-308, 2009. 41. [Waltz, 1975] David Waltz. Understanding Line Drawings of Scenes with Shadows. In The Psychology of Computer Vision, pages 19-91.