The Experts below are selected from a list of 5451 Experts worldwide ranked by ideXlab platform

Thomas Schiex - One of the best experts on this subject based on the ideXlab platform.

  • Maintaining Virtual Arc Consistency Dynamically during SeArch
    2014
    Co-Authors: Hiep Nguyen, Thomas Schiex, Simon De Givry, Christian Bessière
    Abstract:

    Virtual Arc Consistency (VAC) is a recent local Consistency for processing cost function networks (aka weighted constraint networks) that exploits a simple but powerful connection with standard constraint networks. It has allowed to close hard frequency assignment benchmarks and is capable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of standard constraint networks. This algorithm has been improved by exploiting the idea of dynamic Arc Consistency between each iteration, leading to the dynamic VAC algorithm. When VAC is maintained during seArch, the difference between two adjacent nodes in the seArch tree is also limited. In this paper, we show that the incrementality of Dynamic VAC can also be useful when maintaining VAC during seArch and we present results showing that maintaining dynamic VAC during seArch can effectively accelerate seArch.

  • Dynamic Virtual Arc Consistency
    2013
    Co-Authors: Christian Bessière, Thomas Schiex, Hiep Nguyen
    Abstract:

    Virtual Arc Consistency (VAC) is a recent local Consistency for processing Cost Function Networks (or Weighted Con- straint Networks) that exploits a simple but powerful con- nection with classical Constraint Networks. It has allowed to close hard frequency assignment benchmarks and is ca- pable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of classical Constraint Networks. In this work, we show that Dynamic Arc Consistency algorithms can be suitably injected in the virtual Arc Consistency itera- tive algorithm, providing noticeable speedups.

  • Soft Arc Consistency revisited
    Artificial Intelligence, 2010
    Co-Authors: Martin C. Cooper, Thomas Schiex, Simon De Givry, Marti Sanchez, Matthias Zytnicki, Tomas Werner
    Abstract:

    The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations ReseArch, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local Consistency filtering are used for pruning inside Branch and Bound seArch. In this paper, we extend the notion of Arc Consistency by allowing fractional weights and by allowing several Arc Consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal Arc Consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC). To reach a more practical algorithm, we show that the existence of a sequence of Arc Consistency operations which increases the lower bound can be detected by establishing Arc Consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft Arc Consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.

  • Bounds Arc Consistency for weighted CSPs
    Journal of Artificial Intelligence Research, 2009
    Co-Authors: Matthias Zytnicki, Christine Gaspin, Simon De Givry, Thomas Schiex
    Abstract:

    The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been ap- plied to various problems, including resource allocation, bioinformatics, scheduling, etc. To solve such problems, solvers usually rely on branch-and-bound algorithms equipped with local Consistency filtering, mostly soft Arc Consistency. However, these techniques are not well suited to solve problems with very large domains. Motivated by the resolution of an RNA gene localization problem inside large genomic sequences, and in the spirit of bounds Consistency for large domains in crisp CSPs, we introduce soft bounds Arc Consistency, a new weighted local Consistency specifically designed for WCSP with very large domains. Compared to soft Arc Consistency, BAC provides significantly improved time and space asymptotic complexity. In this paper, we show how the semantics of cost functions can be exploited to further improve the time complexity of BAC. We also compare both in theory and in practice the efficiency of BAC on a WCSP with bounds Consistency enforced on a crisp CSP using cost variables. On two different real problems modeled as WCSP, including our RNA gene localization problem, we observe that maintaining bounds Arc con- sistency outperforms Arc Consistency and also improves over bounds Consistency enforced on a constraint model with cost variables.

  • virtual Arc Consistency for weighted csp
    National Conference on Artificial Intelligence, 2008
    Co-Authors: Martin C. Cooper, Thomas Schiex, Simon De Givry, Marti Sanchez, Matthias Zytnicki
    Abstract:

    Optimizing a combination of local cost functions on discrete variables is a central problem in many formalisms such as in probabilistic networks, maximum satisfiability, weighted CSP or factor graphs. Recent results have shown that maintaining a form of local Consistency in a Branch and Bound seArch provides bounds that are strong enough to solve many practical instances. In this paper, we introduce Virtual Arc Consistency (VAC) which iteratively identifies and applies sequences of cost propagation over rational costs that are guaranteed to transform a WCSP in another WCSP with an improved constant cost. Although not as strong as Optimal Soft Arc Consistency, VAC is faster and powerful enough to solve submodular problems. Maintaining VAC inside branch and bound leads to important improvements in efficiency on large difficult problems and allowed us to close two famous frequency assignment problem instances.

Christian Bessière - One of the best experts on this subject based on the ideXlab platform.

  • Maintaining Virtual Arc Consistency Dynamically during SeArch
    2014
    Co-Authors: Hiep Nguyen, Thomas Schiex, Simon De Givry, Christian Bessière
    Abstract:

    Virtual Arc Consistency (VAC) is a recent local Consistency for processing cost function networks (aka weighted constraint networks) that exploits a simple but powerful connection with standard constraint networks. It has allowed to close hard frequency assignment benchmarks and is capable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of standard constraint networks. This algorithm has been improved by exploiting the idea of dynamic Arc Consistency between each iteration, leading to the dynamic VAC algorithm. When VAC is maintained during seArch, the difference between two adjacent nodes in the seArch tree is also limited. In this paper, we show that the incrementality of Dynamic VAC can also be useful when maintaining VAC during seArch and we present results showing that maintaining dynamic VAC during seArch can effectively accelerate seArch.

  • Dynamic Virtual Arc Consistency
    2013
    Co-Authors: Christian Bessière, Thomas Schiex, Hiep Nguyen
    Abstract:

    Virtual Arc Consistency (VAC) is a recent local Consistency for processing Cost Function Networks (or Weighted Con- straint Networks) that exploits a simple but powerful con- nection with classical Constraint Networks. It has allowed to close hard frequency assignment benchmarks and is ca- pable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of classical Constraint Networks. In this work, we show that Dynamic Arc Consistency algorithms can be suitably injected in the virtual Arc Consistency itera- tive algorithm, providing noticeable speedups.

  • Efficient algorithms for singleton Arc Consistency
    Constraints, 2011
    Co-Authors: Christian Bessière, Stéphane Cardon, Romuald Debruyne, Christophe Lecoutre
    Abstract:

    In this paper, we propose two original and efficient approaches for enforcing singleton Arc Consistency. In the first one, the data structures used to enforce Arc Consistency are shared between all subproblems where a domain is reduced to a singleton. This new algorithm is not optimal but it requires far less space and is often more efficient in practice than the optimal algorithm SAC-Opt. In the second approach, we perform several runs of a greedy seArch (where at each step, Arc Consistency is maintained), possibly detecting the singleton Arc Consistency of several values in one run. It is an original illustration of applying inference (i.e., establishing singleton Arc Consistency) by seArch. Using a greedy seArch allows benefiting from the incrementality of Arc Consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. We present extensive experiments that show the benefit of our two approaches.

  • Making Bound Consistency as Effective as Arc Consistency
    2009
    Co-Authors: Christian Bessière, Thierry Petit, Bruno Zanuttini
    Abstract:

    We study under what conditions bound Consistency (BC) and Arc Consistency (AC), two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.

  • Theoretical analysis of singleton Arc Consistency and its extensions
    Artificial Intelligence, 2008
    Co-Authors: Christian Bessière, Romuald Debruyne
    Abstract:

    Singleton Arc Consistency (SAC) is a Consistency property that is simple to specify and is stronger than Arc Consistency. Algorithms have already been proposed to enforce SAC, but they have a high time complexity. In this paper, we give a lower bound to the worst-case time complexity of enforcing SAC on binary constraints. We discuss two interesting features of SAC. The first feature leads us to propose an algorithm for SAC that has optimal time complexity when restricted to binary constraints. The second feature leads us to extend SAC to a stronger level of local Consistency that we call Bidirectional SAC (BiSAC). We also show the relationship between SAC and the propagation of disjunctive constraints.

Martin C. Cooper - One of the best experts on this subject based on the ideXlab platform.

  • On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
    Algorithmica, 2019
    Co-Authors: Clément Carbonnel, Martin C. Cooper, David A. Cohen, Stanislav Živný
    Abstract:

    Singleton Arc Consistency is an important type of local Consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton Arc Consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton Arc Consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.

  • Soft Arc Consistency revisited
    Artificial Intelligence, 2010
    Co-Authors: Martin C. Cooper, Thomas Schiex, Simon De Givry, Marti Sanchez, Matthias Zytnicki, Tomas Werner
    Abstract:

    The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations ReseArch, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local Consistency filtering are used for pruning inside Branch and Bound seArch. In this paper, we extend the notion of Arc Consistency by allowing fractional weights and by allowing several Arc Consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal Arc Consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC). To reach a more practical algorithm, we show that the existence of a sequence of Arc Consistency operations which increases the lower bound can be detected by establishing Arc Consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft Arc Consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions. These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.

  • Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency
    Constraints, 2008
    Co-Authors: Martin C. Cooper
    Abstract:

    Submodular function minimization is a polynomially solvable combinatorial problem. Unfortunately the best known general-purpose algorithms have high-order polynomial time complexity. In many applications the objective function is locally defined in that it is the sum of cost functions (also known as soft or valued constraints) whose arities are bounded by a constant. We prove that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Such an equivalent instance is the result of establishing optimal soft Arc Consistency and can hence be found by solving a linear program. From a practical point of view, this provides us with an alternative algorithm for minimizing locally defined submodular functions. From a theoretical point of view, this brings to light a previously unknown connection between submodularity and soft Arc Consistency.

  • virtual Arc Consistency for weighted csp
    National Conference on Artificial Intelligence, 2008
    Co-Authors: Martin C. Cooper, Thomas Schiex, Simon De Givry, Marti Sanchez, Matthias Zytnicki
    Abstract:

    Optimizing a combination of local cost functions on discrete variables is a central problem in many formalisms such as in probabilistic networks, maximum satisfiability, weighted CSP or factor graphs. Recent results have shown that maintaining a form of local Consistency in a Branch and Bound seArch provides bounds that are strong enough to solve many practical instances. In this paper, we introduce Virtual Arc Consistency (VAC) which iteratively identifies and applies sequences of cost propagation over rational costs that are guaranteed to transform a WCSP in another WCSP with an improved constant cost. Although not as strong as Optimal Soft Arc Consistency, VAC is faster and powerful enough to solve submodular problems. Maintaining VAC inside branch and bound leads to important improvements in efficiency on large difficult problems and allowed us to close two famous frequency assignment problem instances.

  • optimal soft Arc Consistency
    International Joint Conference on Artificial Intelligence, 2007
    Co-Authors: Martin C. Cooper, Simon De Givry, Thomas Schiex
    Abstract:

    The Valued (VCSP) framework is a generic optimization framework with a wide range of applications. Soft Arc Consistency operations transform a VCSP into an equivalent problem by shifting weights between cost functions. The principal aim is to produce a good lower bound on the cost of solutions, an essential ingredient of a branch and bound seArch. But soft AC is much more complex than traditional AC: there may be several closures (fixpoints) and finding the closure with a maximum lower bound has been shown to be NP-hard for integer costs [Cooper and Schiex, 2004]. We introduce a relaxed variant of soft Arc Consistency using rational costs. In this case, an optimal closure can be found in polynomial time. Furthermore, for finite rational costs, the associated lower bound is shown to provide an optimal Arc consistent reformulation of the initial problem. Preliminary experiments on random and structured problems are reported, showing the strength of the lower bound produced.

Romuald Debruyne - One of the best experts on this subject based on the ideXlab platform.

  • Efficient algorithms for singleton Arc Consistency
    Constraints, 2011
    Co-Authors: Christian Bessière, Stéphane Cardon, Romuald Debruyne, Christophe Lecoutre
    Abstract:

    In this paper, we propose two original and efficient approaches for enforcing singleton Arc Consistency. In the first one, the data structures used to enforce Arc Consistency are shared between all subproblems where a domain is reduced to a singleton. This new algorithm is not optimal but it requires far less space and is often more efficient in practice than the optimal algorithm SAC-Opt. In the second approach, we perform several runs of a greedy seArch (where at each step, Arc Consistency is maintained), possibly detecting the singleton Arc Consistency of several values in one run. It is an original illustration of applying inference (i.e., establishing singleton Arc Consistency) by seArch. Using a greedy seArch allows benefiting from the incrementality of Arc Consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. We present extensive experiments that show the benefit of our two approaches.

  • Theoretical analysis of singleton Arc Consistency and its extensions
    Artificial Intelligence, 2008
    Co-Authors: Christian Bessière, Romuald Debruyne
    Abstract:

    Singleton Arc Consistency (SAC) is a Consistency property that is simple to specify and is stronger than Arc Consistency. Algorithms have already been proposed to enforce SAC, but they have a high time complexity. In this paper, we give a lower bound to the worst-case time complexity of enforcing SAC on binary constraints. We discuss two interesting features of SAC. The first feature leads us to propose an algorithm for SAC that has optimal time complexity when restricted to binary constraints. The second feature leads us to extend SAC to a stronger level of local Consistency that we call Bidirectional SAC (BiSAC). We also show the relationship between SAC and the propagation of disjunctive constraints.

  • optimal and suboptimal singleton Arc Consistency algorithms
    International Joint Conference on Artificial Intelligence, 2005
    Co-Authors: Christian Bessière, Romuald Debruyne
    Abstract:

    Singleton Arc Consistency (SAC) enhances the pruning capability of Arc Consistency by ensuring that the network cannot become Arc inconsistent after the assignment of a value to a variable. Algorithms have already been proposed to enforce SAC, but they are far from optimal time complexity. We give a lower bound to the time complexity of enforcing SAC, and we propose an algorithm that achieves this complexity, thus being optimal. However, it can be costly in space on large problems. We then propose another SAC algorithm that trades time optimality for a better space complexity. Nevertheless, this last algorithm has a better worst-case time complexity than previously published SAC algorithms. An experimental study shows the good performance of the new algorithms.

  • theoretical analysis of singleton Arc Consistency
    2004
    Co-Authors: Christian Bessière, Romuald Debruyne
    Abstract:

    Singleton Arc Consistency (SAC) is a local Consistency that enhances the pruning capability of Arc Consistency by ensuring that the network can be made Arc consistent after any assignment of a value to a variable. While some algorithms have been proposed in the literature to enforce SAC, a more in-depth theoretical analysis of this local Consistency has never been published. In this paper, we give a lower bound to the time complexity of enforcing SAC, and we propose an algorithm that achieves this complexity, thus being optimal. We characterize some properties of SAC which are unusual for a local Consistency. Based on some of these properties, we extend SAC to a more powerful local Consistency that we compare to the existing local consistencies.

  • maintaining Arc Consistency within dynamic backtracking
    Lecture Notes in Computer Science, 2000
    Co-Authors: Narendra Jussien, Romuald Debruyne, Patrice Boizumault
    Abstract:

    Most of complete seArch algorithms over Constraint Satisfaction Problems (csP) are based on Standard Backtracking. Two main enhancements of this basic scheme have been studied: first, to integrate constraint propagation as mac which maintains Arc Consistency during seArch; second, intelligent backtrackers which avoid repeatedly falling in the same dead-ends by recording nogoods as Conflict-directed BackJumping (cbj) or Dynamic Backtracking (dbt). Integrations of constraint propagation within intelligent backtrackers have been done as mac-cbj which maintains Arc Consistency in cbj. However, Bessiere and Regin have shown that mac-cbj was very rarely better than mac. However, the inadequacy of mac-cbj is more related to the fact that cbj does not avoid thrashing than to the cost of the management of nogoods. This paper describes and evaluates mac-dbt which maintains Arc-Consistency in dbt. Experiments show that mac-dbt is able to solve very large problems and that it remains very stable as the size of the problems increases. Moreover, mac-dbt outperforms mac on the structured problems we have randomly generated.

Christophe Lecoutre - One of the best experts on this subject based on the ideXlab platform.

  • domain k wise Consistency made as simple as generalized Arc Consistency
    Integration of AI and OR Techniques in Constraint Programming, 2014
    Co-Authors: Jeanbaptiste Mairy, Y. Deville, Christophe Lecoutre
    Abstract:

    In Constraint Programming (CP), Generalized Arc Consistency (GAC) is the central property used for making inferences when solving Constraint Satisfaction Problems (CSPs). Developing simple and practical filtering algorithms based on consistencies stronger than GAC is a challenge for the CP community. In this paper, we propose to combine k-Wise Consistency (kWC) with GAC, where kWC states that every tuple in a constraint can be extended to every set of k − 1 additional constraints. Our contribution is as follows. First, we derive a domain-filtering Consistency, called Domain k-Wise Consistency (DkWC), from the combination of kWC and GAC. Roughly speaking, this property corresponds to the pruning of values of GAC, when enforced on a CSP previously made kWC. Second, we propose a procedure to enforce DkWC, relying on an encoding of kWC to generate a modified CSP called k-interleaved CSP. Formally, we prove that enforcing GAC on the k-interleaved CSP corresponds to enforcing DkWC on the initial CSP. Consequently, we show that the strong DkWC can be enforced very easily in constraint solvers since the k-interleaved CSP is rather immediate to generate and only existing GAC propagators are required: in a nutshell, DkWC is made as simple and practical as GAC. Our experimental results show the benefits of our approach on a variety of benchmarks.

  • Efficient algorithms for singleton Arc Consistency
    Constraints, 2011
    Co-Authors: Christian Bessière, Stéphane Cardon, Romuald Debruyne, Christophe Lecoutre
    Abstract:

    In this paper, we propose two original and efficient approaches for enforcing singleton Arc Consistency. In the first one, the data structures used to enforce Arc Consistency are shared between all subproblems where a domain is reduced to a singleton. This new algorithm is not optimal but it requires far less space and is often more efficient in practice than the optimal algorithm SAC-Opt. In the second approach, we perform several runs of a greedy seArch (where at each step, Arc Consistency is maintained), possibly detecting the singleton Arc Consistency of several values in one run. It is an original illustration of applying inference (i.e., establishing singleton Arc Consistency) by seArch. Using a greedy seArch allows benefiting from the incrementality of Arc Consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. We present extensive experiments that show the benefit of our two approaches.

  • maintaining Arc Consistency with multiple residues
    Default journal, 2008
    Co-Authors: Christophe Lecoutre, Roland H C Yap, Chavalit Likitvivatanavong, Scott Shannon, Crilcnrs Fre, Yuanlin Zhang
    Abstract:

    Exploiting residual supports (or residues) has proved to be one of the most cost-effective approaches for Maintaining Arc Consistency during seArch (MAC). While MAC based on optimal AC algorithm may have better theoretical time complexity in some cases, in practice the overhead for maintaining required data structure during seArch outweighs the benefit, not to mention the more complicated implementation. Implementing MAC with residues, on the other hand, is trivial. In this paper we extend previous work on residues and investigate the use of multiple residues during seArch. We first give a theoretical analysis of residu e-based algorithms that explains their good practical performance. We then propose several heuristics on how to deal with multiple residues. Finally, our empirical study shows that with a proper and limited number of residues, many constraint checks can be saved. When the constraint check is expensive or a problem is hard, the multiple residues approach is competitive in both the number of constraint checks and cpu time.

  • a study of residual supports in Arc Consistency
    International Joint Conference on Artificial Intelligence, 2007
    Co-Authors: Christophe Lecoutre, Fred Hemery
    Abstract:

    In an Arc Consistency (AC) algorithm, a residual support, or residue, is a support that has been stored during a previous execution of the procedure which determines if a value is supported by a constraint. The point is that a residue is not guaranteed to represent a lower bound of the smallest current support of a value. In this paper, we study the theoretical impact of exploiting residues with respect to the basic algorithm AC3. First, we prove that AC3rm (AC3 with multi-directional residues) is optimal for low and high constraint tightness. Second, we show that when AC has to be maintained during a backtracking seArch, MAC2001 presents, with respect to MAC3rm, an overhead in O(µed) per branch of the binary tree built by MAC, where µ denotes the number of refutations of the branch, e the number of constraints and d the greatest domain size of the constraint network. One consequence is that MAC3rm admits a better worst-case time complexity than MAC2001 for a branch involving µ refutations when either µ > d2 or µ > d and the tightness of any constraint is either low or high. Our experimental results clearly show that exploiting residues allows enhancing MAC and SAC algorithms.

  • enforcing Arc Consistency using bitwise operations
    Constraint Programming Letters (CPL), 2007
    Co-Authors: Christophe Lecoutre, Julien Vion, Cnrs Fre
    Abstract:

    In this paper, we propose to exploit bitwise operations to speed up some important computations such as looking for a support of a value in a constraint, or determining if a value is substitutable by another one. Considering a computer equipped with a x-bit CPU, one can then expect an increase of the performance by a coefficient up to x (which may be important, since x is equal to 32 or 64 in many current central units). To show the interest of enforcing Arc Consistency using bitwise operations, we introduce a new variant of AC3, denoted by AC3 bit , which can be used when constraints are (or can be) represented in extension. This new algorithm when embedded in MAC, is approximately two times more efficient than AC3 rm . Note that AC3 rm is a variant of AC3 which