Daniel Singer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Daniel Singer has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
Zineb Habbas
LCOMS EA 7306, Université de Lorraine, Metz, France
5 shared publications- Francine Herrmann
Université de Lorraine
3 shared publications - Kamal Amroun
University of Bejaia
3 shared publications - Michaël Krajecki
University of Reims Champagne-Ardenne
3 shared publications Z. Habbas
2 shared publicationsAlain Vagner
Université Paul Verlaine de Metz, UFR MIM
1 shared publication
Latest Publications
- 21 March 2016
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 50 (2) , 241-267
Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints
Many real-world problems can be modelled as Constraint Satisfaction Problems (CSPs). Although CSP is NP-complete, it has been proved that non binary CSP instances may be efficiently solved if they are representable as Generalized Hypertree Decomposition (GHD) with small width. Algorithms for solving CSPs based on a GHD consider an extensional representation of constraints together with join and semi-join operations giving rise to new large constraint tables (or relations) needed to be temporarily saved. Extensional representation of constraints is quite natural and adapted to the specification of real problems but unfortunately limits significantly the practical performance of these algorithms. The present work tackles this problem using a compact representation of constraint tables. Consequently, to make algorithms compatible with this compact representation, new “compressed join” and “compressed semi-join” operations have to be defined. This last step constitutes our main contribution which, as far as we know, has never been presented. The correctness of this approach is proved and validated on multiple benchmarks. Experimental results show that using compressed relations and compressed operations improves significantly the practical performance of the basic algorithm proposed by Gottlob et al. for solving non binary CSPs with a Generalized Hypertree Decomposition.
- 21 March 2016
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 50 (2) , 241-267
Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints
Many real-world problems can be modelled as Constraint Satisfaction Problems (CSPs). Although CSP is NP-complete, it has been proved that non binary CSP instances may be efficiently solved if they are representable as Generalized Hypertree Decomposition (GHD) with small width. Algorithms for solving CSPs based on a GHD consider an extensional representation of constraints together with join and semi-join operations giving rise to new large constraint tables (or relations) needed to be temporarily saved. Extensional representation of constraints is quite natural and adapted to the specification of real problems but unfortunately limits significantly the practical performance of these algorithms. The present work tackles this problem using a compact representation of constraint tables. Consequently, to make algorithms compatible with this compact representation, new “compressed join” and “compressed semi-join” operations have to be defined. This last step constitutes our main contribution which, as far as we know, has never been presented. The correctness of this approach is proved and validated on multiple benchmarks. Experimental results show that using compressed relations and compressed operations improves significantly the practical performance of the basic algorithm proposed by Gottlob et al. for solving non binary CSPs with a Generalized Hypertree Decomposition.
- 24 February 2015
- Published by Taylor & Francis in Journal of Experimental & Theoretical Artificial Intelligence
- Vol. 27 (5) , 649-671
A Forward-Checking algorithm based on a Generalised Hypertree Decomposition for solving non-binary constraint satisfaction problems
Methods exploiting hypertree decompositions are considered as the best approach for solving extensional constraint satisfaction problems (CSPs) on finite domains, with regard to theoretical time complexity when fixed widths are considered. However, this result has not been confirmed in practice because of the memory explosion problem. In this article, a new approach for efficient solving extensional non-binary CSPs is proposed. It is a combination of an enumerative search algorithm which is memory efficient and a Generalised Hypertree Decomposition (GHD) that is time efficient. This new approach is a cluster-oriented Forward-Checking algorithm. It considers the solutions of the subproblems deriving from the decomposition, as the values to be assigned rather than the values associated with the variables of the initial problem. In addition, the algorithm is guided by an order induced by the clusters deriving from the GHD. Moreover, two improved versions of this algorithm are proposed. The first version uses nogoods and the second one improves it again by a dynamic reordering of subtrees. All these algorithms have been implemented and the experimental results are promising.
- 24 February 2015
- Published by Taylor & Francis in Journal of Experimental & Theoretical Artificial Intelligence
- Vol. 27 (5) , 649-671
A Forward-Checking algorithm based on a Generalised Hypertree Decomposition for solving non-binary constraint satisfaction problems
Methods exploiting hypertree decompositions are considered as the best approach for solving extensional constraint satisfaction problems (CSPs) on finite domains, with regard to theoretical time complexity when fixed widths are considered. However, this result has not been confirmed in practice because of the memory explosion problem. In this article, a new approach for efficient solving extensional non-binary CSPs is proposed. It is a combination of an enumerative search algorithm which is memory efficient and a Generalised Hypertree Decomposition (GHD) that is time efficient. This new approach is a cluster-oriented Forward-Checking algorithm. It considers the solutions of the subproblems deriving from the decomposition, as the values to be assigned rather than the values associated with the variables of the initial problem. In addition, the algorithm is guided by an order induced by the clusters deriving from the GHD. Moreover, two improved versions of this algorithm are proposed. The first version uses nogoods and the second one improves it again by a dynamic reordering of subtrees. All these algorithms have been implemented and the experimental results are promising.
- 1 January 2014
- Published by INSTICC
- p. 477-484
Decomposition Tehniques for Solving Frequency Assigment Problems (FAP) - A Top-Down Approach
The SCITEPRESS Digital Library offers online access to all papers presented at INSTICC conferences, as well as a few conferences organized by others.
- 1 January 2014
- Published by INSTICC
- p. 477-484
Decomposition Tehniques for Solving Frequency Assigment Problems (FAP) - A Top-Down Approach
The SCITEPRESS Digital Library offers online access to all papers presented at INSTICC conferences, as well as a few conferences organized by others.
- 1 January 2011
- Published by INSTICC
- p. 146-156
SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION
- 1 January 2011
- Published by INSTICC
- p. 146-156
SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION
- 28 May 2008
- Published by Springer Nature
- p. 249-258
JaCk-SAT: A New Parallel Scheme to Solve the Satisfiability Problem (SAT) Based on Join-and-Check
- 28 May 2008
- Published by Springer Nature
- p. 249-258
JaCk-SAT: A New Parallel Scheme to Solve the Satisfiability Problem (SAT) Based on Join-and-Check
- 28 June 2007
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 49 (1-4) , 207-220
Linearly ordered semigroups for fuzzy set theory
- 28 June 2007
- Published by Springer Nature in Annals of Mathematics and Artificial Intelligence
- Vol. 49 (1-4) , 207-220
Linearly ordered semigroups for fuzzy set theory
- 10 April 2006
- Published by Wiley
- p. 123-147
Parallel Resolution of the Satisfiability Problem: A Survey
- 10 April 2006
- Published by Wiley
- p. 123-147
Parallel Resolution of the Satisfiability Problem: A Survey
- 1 January 2006
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 380-388
Parallel Resolution of the Satisfiability Problem (SAT) with OpenMP and MPI
- 1 January 2006
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 380-388
Parallel Resolution of the Satisfiability Problem (SAT) with OpenMP and MPI
- 1 January 2005
- Published by Inderscience Publishers in International Journal of Computational Science and Engineering
- Vol. 1 (2/3/4) , 192
Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study
This paper provides both a formal and an empirical study of decomposition techniques for parallel resolution of Constraint Satisfaction Problems (CSP) in shared memory. The main contribution of this study is to bring together decomposition techniques with Backtrack search to solve CSP on parallel architectures in shared memory. Another contribution is to demonstrate how to obtain good scalability up to hundreds of processors in shared memory for CSP resolution and more generally for Irregular Applications.
- 1 January 2005
- Published by Inderscience Publishers in International Journal of Computational Science and Engineering
- Vol. 1 (2/3/4) , 192
Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study
This paper provides both a formal and an empirical study of decomposition techniques for parallel resolution of Constraint Satisfaction Problems (CSP) in shared memory. The main contribution of this study is to bring together decomposition techniques with Backtrack search to solve CSP on parallel architectures in shared memory. Another contribution is to demonstrate how to obtain good scalability up to hundreds of processors in shared memory for CSP resolution and more generally for Irregular Applications.
- 20 January 2003
- Published by Institute of Electrical and Electronics Engineers (IEEE)
A methodological approach to implement CSP on FPGA
- 20 January 2003
- Published by Institute of Electrical and Electronics Engineers (IEEE)
A methodological approach to implement CSP on FPGA