ORCID Profile
0000-0003-3131-0709
Current Organisation
CNRS
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Publisher: Springer Science and Business Media LLC
Date: 19-08-2014
Publisher: Springer International Publishing
Date: 2016
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2018
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.
Publisher: Springer International Publishing
Date: 2014
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2019
Abstract: Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs a method to produce a clausal explanation of this bound for use in a CDCL algorithm and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
Publisher: Springer Berlin Heidelberg
Date: 2004
Publisher: Springer Science and Business Media LLC
Date: 13-09-2017
Publisher: Springer International Publishing
Date: 2016
Publisher: IEEE
Date: 26-09-2019
DOI: 10.15439/2019F90
Publisher: Elsevier BV
Date: 06-2023
Publisher: Springer International Publishing
Date: 2020
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11889205_8
Publisher: AI Access Foundation
Date: 04-09-2020
DOI: 10.1613/JAIR.1.11313
Abstract: Graph coloring is an important problem in combinatorial optimization and a major component of numerous allocation and scheduling problems. In this paper we introduce a hybrid CP/SAT approach to graph coloring based on the addition-contraction recurrence of Zykov. Decisions correspond to either adding an edge between two non-adjacent vertices or contracting these two vertices, hence enforcing inequality or equality, respectively. This scheme yields a symmetry-free tree and makes learnt clauses stronger by not committing to a particular color. We introduce a new lower bound for this problem based on Mycielskian graphs a method to produce a clausal explanation of this bound for use in a CDCL algorithm a branching heuristic emulating Br´elaz’ heuristic on the Zykov tree and dedicated pruning techniques relying on marginal costs with respect to the bound and on reasoning about transitivity when unit propagating learnt clauses. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms other SAT-based approaches and Dsatur on standard benchmarks both for finding upper bounds and for proving lower bounds.
Publisher: Springer International Publishing
Date: 2014
Publisher: Springer International Publishing
Date: 2014
Publisher: Elsevier BV
Date: 07-2009
Publisher: AI Access Foundation
Date: 27-05-2011
DOI: 10.1613/JAIR.3197
Abstract: In many combinatorial problems one may need to model the ersity or similarity of assignments in a solution. For ex le, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.
Publisher: Springer International Publishing
Date: 2014
Publisher: Springer Science and Business Media LLC
Date: 26-09-2013
Publisher: Springer Berlin Heidelberg
Date: 2007
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 08-2017
Abstract: Kernelization is a powerful concept from parameterized complexity theory that captures (a certain idea of) efficient polynomial-time preprocessing for hard decision problems. However, exploiting this technique in the context of constraint programming is challenging. Building on recent results for the VertexCover constraint, we introduce novel "loss-less" kernelization variants that are tailored for constraint propagation. We showcase the theoretical interest of our ideas on two constraints, VertexCover and EdgeDominatingSet.
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Springer Berlin Heidelberg
Date: 2004
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11564751_117
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: Springer International Publishing
Date: 2014
Publisher: International Joint Conferences on Artificial Intelligence Organization
Date: 07-2018
Abstract: The maximum clique and minimum vertex cover problems are among Karp's 21 NP-complete problems, and have numerous applications: in combinatorial auctions, for computing phylogenetic trees, to predict the structure of proteins, to analyse social networks, and so forth. Currently, the best complete methods are branch & bound algorithms and rely largely on graph colouring to compute a bound. We introduce a new approach based on SAT and on the "Conflict-Driven Clause Learning" (CDCL) algorithm. We propose an efficient implementation of Babel's bound and pruning rule, as well as a novel dominance rule. Moreover, we show how to compute concise explanations for this inference. Our experimental results show that this approach is competitive and often outperforms the state of the art for finding cliques of maximum weight.
Publisher: Springer Berlin Heidelberg
Date: 2011
Publisher: Springer International Publishing
Date: 2020
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11493853_8
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Springer Berlin Heidelberg
Date: 2003
Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
Date: 04-2015
Abstract: We introduce a simple technique for disjunctive machine scheduling problems and show that this method can match or even outperform state-of-the-art algorithms on a number of problem types. Our approach combines a number of generic search techniques such as restarts, adaptive heuristics, and solution-guided branching on a simple model based on a decomposition of disjunctive constraints and on the reification of these disjuncts. This paper describes the method and its application to variants of the job shop scheduling problem (JSP). We show that our method can easily be adapted to handle additional side constraints and different objective functions, often outperforming the state-of-the-art and closing a number of open problems. Moreover, we perform in-depth analysis of the various factors that make this approach efficient. We show that, while most of the factors give moderate benefits, the variable and value ordering components are key.
Publisher: Springer Science and Business Media LLC
Date: 06-06-2010
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11564751_86
Publisher: Springer Berlin Heidelberg
Date: 2008
Publisher: Springer Science and Business Media LLC
Date: 12-2020
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: Springer Berlin Heidelberg
Date: 2010
Publisher: Springer Berlin Heidelberg
Date: 2004
Publisher: Springer Berlin Heidelberg
Date: 2004
Publisher: Springer Berlin Heidelberg
Date: 2004
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11757375_7
Publisher: Elsevier BV
Date: 02-2015
Publisher: Springer International Publishing
Date: 2017
Publisher: Springer International Publishing
Date: 2015
Publisher: Springer International Publishing
Date: 2018
Publisher: Elsevier BV
Date: 12-2016
Publisher: Springer Berlin Heidelberg
Date: 2009
Publisher: Springer International Publishing
Date: 2019
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11754602_3
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Date: 2021
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Date: 2021
Publisher: Springer Berlin Heidelberg
Date: 2012
Publisher: Springer Science and Business Media LLC
Date: 02-12-2006
Publisher: Springer Science and Business Media LLC
Date: 21-10-2006
Publisher: Springer Berlin Heidelberg
Date: 2012
Location: France
No related grants have been discovered for Emmanuel Hebrard.