Pierre Talbot

Story of this paper

This paper is the summary of the PhD work of Hedieh Haddad in integrating Bayesian optimisation and constraint programming. It extends our previous papers at PTHG 2024 and ICTAI 2024. Although the proposed algorithm is simple, it have shown to improve the efficiency of several state-of-the-art solvers on standard benchmarks.


@misc{haddad2026hyperparameteroptimizationconstraintprogramming,
      title={Hyperparameter Optimization of Constraint Programming Solvers},
      author={Hedieh Haddad and Thibault Falque and Pierre Talbot and Pascal Bouvry},
      year={2026},
      eprint={2601.11389},
      archivePrefix={arXiv},
      primaryClass={cs.AI},
      url={https://arxiv.org/abs/2601.11389}
}

Story of this paper

This paper describes the constraint solver Turbo (as of version 1.2.8), which is fully executed on GPU (both propagation and search). It extends the AAAI 2022 paper, which focused on the theoretical model and only supported a few constraints. When I tried to extend the solver from AAAI 2022, it turned out to be very slow due to code abstractions (clean code?!) which were not suited to GPU architectures. I revamped the solver to be compatible with GPU architectures, and this paper describes the current algorithm, after years of trial and error (as shown on the online technical journal of Turbo). It is a significant milestone because we now have a working general-purpose GPU-based constraint solver.

@inproceedings{AAAI2026-Talbot,
  author={Talbot, Pierre},
  title = {{A GPU-based Constraint Programming Solver}},
  booktitle={{Proceedings of the AAAI Conference on Artificial Intelligence}},
  year = {2026},
  volume={XX},
  number={X},
  doi={XXX},
  month={XX},
  pages={XX}
}

Story of this paper

This paper shows how to transform a constraint network into a ternary constraint network (TCN). This transformation and the preprocessing algorithm are the ones used in Turbo. It is complementary to the AAAI 2026 paper; I initially included this decomposition in a paper submitted to CP 2025, but the reviewers said it was standard/not new. Clearly, TCNs exist since the inception of CP, but I could not find a paper formally describing the transformation and preprocessing of TCN. Although it is not very complicated, there can be subtle bugs when implementing this transformation, and I hope this paper can help future implementation! I intend to update the paper from times to times to make it more complete and, perhaps, submit it to a journal in the future.


@misc{TCN-preprint25-Talbot,
      title={Decomposition and Preprocessing of Ternary Constraint Networks},
      author={Pierre Talbot},
      year={2025},
      eprint={2511.11872},
      archivePrefix={arXiv},
      primaryClass={cs.SC},
      url={https://arxiv.org/abs/2511.11872}
}

Story of this paper

This is a survey paper of combinatorial optimization of quantum circuit expressed as ZX-calculus diagrams. The work is conducted by Tobias who read and explained most of the literature of this recent and quickly progressing field! This paper is under review in the journal Quantum.


@misc{ZX-preprint25-Fischbach,
      title={A Review on Quantum Circuit Optimization using ZX-Calculus},
      author={Tobias Fischbach and Pierre Talbot and Pascal Bouvry},
      year={2025},
      eprint={2509.20663},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2509.20663},
}

Story of this paper

This paper is a draft of an upcoming paper on Turbo, the first general constraint solver fully executed on GPU. This is a preliminary version of the AAAI 2026 paper and the preprint 2025 on ternary constraint network.

@inproceedings{JFPC25-Talbot,
  address = {Dijon, France},
  title = {R\'{e}seau de Contrainte Ternaire pour une Propagation Efficace de Bornes sur GPU},
  booktitle = {{Journ\'{e}es Francophones de Programmation par Contraintes (JFPC 2025)}},
  author = {Talbot, Pierre},
  month = {30 June--4 July},
  year = {2025}
}

Story of this paper

This paper is the work of Tobias Fischbach, Ph.D. candidate, to optimize quantum circuits. Due to the hardware requirements of quantum computers, it is necessary to optimize the circuit while preserving its semantics. For this purpose, we use the ZX-calculus, a formal semantics-preserving rewriting language. The quantum circuit is converted into a ZX diagram, optimized, and then extracted from the optimized ZX diagram. We give a formalization of the state-space and the optimization. Then, we investigate two simple exhaustive search algorithms (DFS, IDDFS) to explore the state-space of ZX diagrams. The results show that it can beat existing state-of-the-art greedy optimization algorithm (full-reduce), but it takes longer to execute.


    @inproceedings{OLA-2025,
  author = {{Tobias Fischbach, Pierre Talbot, Pascal Bouvry}},
  title = {{Exhaustive Search for Quantum Circuit Optimization using ZX Calculus}},
  booktitle = {{Optimization and Learning}},
  publisher={Springer Nature Switzerland},
  year={2026},
  pages={239--253},
  doi = {10.1007/978-3-032-13589-6_18},
  url = {https://link.springer.com/chapter/10.1007/978-3-032-13589-6_18}
}

Story of this paper

This is a follow-up paper of the workshop paper at PTHG-2024 (in which we compared 3 HPO methods) by Hedieh Haddad, Ph.D. candidate. Here, we focus on the most successful HPO method: Bayesian optimization. The approach is evaluated in detail and despite its simplicity, we do better than the default search and universal search strategies such as CACD and PICK3 with Choco and ACE solvers. A surprising result is that spending up to 50% of the time to look for a good search strategy can pay off. Perhaps in constraint programming we have the bad habit of not doing enough preprocessing and parameters-tuning...

@inproceedings{ICTAI-2024,
  author = {{Haddad, Hedieh and Talbot, Pierre and Bouvry, Pascal}},
  title = {{Selecting Search Strategy in Constraint Solvers using Bayesian Optimization}},
  booktitle = {{IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI 2024)}},
  year = {2024},
  pages={764--773},
  doi = {10.1109/ICTAI62512.2024.00113},
  organization={IEEE}
}

Story of this paper

This paper is the work of Hedieh Haddad, Ph.D. candidate, to explore the usage of hyperparameter optimization (HPO) in constraint solvers, and more particularly to guess which search strategy to use. More specifically, this paper compares 3 HPO methods (random search, hyperband and Bayesian optimisation) to choose the search strategy.

@inproceedings{PTHG-2024,
  author =  {Hedieh Haddad, Pierre Talbot, Pascal Bouvry},
  title = {{Comparison of Hyperparameter Optimization Methods for Selecting Search Strategy of Constraint Programming Solvers}},
  booktitle = {PTHG-24: The Seventh Workshop on Progress Towards the Holy Grail},
  year =  {2024},
  URL =   {https://freuder.wordpress.com/progress-towards-the-holy-grail-workshops/pthg-24-the-seventh-workshop-on-progress-towards-the-holy-grail/}
}

Story of this paper

This paper is an abstract of my Ph.D. thesis published in the Constraints journal.

@article{constraints-2023,
  title = {Spacetime programming: a synchronous language for constraint search},
  volume = {28},
  issn = {1383-7133, 1572-9354},
  shorttitle = {Spacetime programming},
  url = {https://link.springer.com/10.1007/s10601-023-09356-1},
  doi = {10.1007/s10601-023-09356-1},
  language = {en},
  number = {3},
  urldate = {2024-06-03},
  journal = {Constraints},
  author = {Talbot, Pierre},
  month = sep,
  year = {2023},
  pages = {516--517}
}

Story of this paper

This paper is mainly a collaboration with my student Manuel who defined and solved a new combinatorial problem for satellite imaging. He was relying on heuristics or greedy algorithm, and I helped him to use a constraint programming model and solver. It is also a multiobjective optimization problem and we compute the whole Pareto front, which is quite unusual in constraint programming.

@inproceedings{CP2023-2-Combarro,
  author =  {Combarro Sim\'{o}n, Manuel and Talbot, Pierre and Danoy, Gr\'{e}goire and Musial, Jedrzej and Alswaitti, Mohammed and Bouvry, Pascal},
  title = {{Constraint Model for the Satellite Image Mosaic Selection Problem}},
  booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages = {44:1--44:15},
  series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =  {978-3-95977-300-3},
  ISSN =  {1868-8969},
  year =  {2023},
  volume =  {280},
  editor =  {Yap, Roland H. C.},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  URL =   {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.44},
  doi =   {10.4230/LIPIcs.CP.2023.44}
}

Story of this paper

This paper is a collaboration with Tingting Hu and Nicolas Navet. They work in the field of automotive networks. The problem tackled is to allocate services on processors in a car such that we do not exceed the capacity constraints of the network and processors. The particularity is that our algorithm calls an external worst-case traversal time analysis program during the solving. We have proved the soundness of our approach using concepts from abstract interpretation.

@inproceedings{CP2023-1-Talbot,
  author =  {Talbot, Pierre and Hu, Tingting and Navet, Nicolas},
  title = {{Constraint Programming with External Worst-Case Traversal Time Analysis}},
  booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages = {34:1--34:20},
  series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =  {978-3-95977-300-3},
  ISSN =  {1868-8969},
  year =  {2023},
  volume =  {280},
  editor =  {Yap, Roland H. C.},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  URL =   {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.34},
  doi =   {10.4230/LIPIcs.CP.2023.34}
}

@inproceedings{AAAI2022-Talbot,
  author={Talbot, Pierre and Pinel, Fr\'{e}d\'{e}ric and Bouvry, Pascal},
  title = {{A Variant of Concurrent Constraint Programming on GPU}},
  booktitle={{Proceedings of the AAAI Conference on Artificial Intelligence}},
  year = {2022},
  volume={36},
  number={4},
  doi={10.1609/aaai.v36i4.20298},
  month={Jun.},
  pages={3830-3839}
}

Story of this paper

Note: this paper was presented at the ICLP 2020 conference, and published in the journal Theory and Practice of Logic Programming.

This paper was implemented during my postdoc in Nantes, and follows our ICTAI 2019 paper. The overarching goal of the project is to explore the theory of abstract interpretation for constraint reasoning. Why is that so? Because abstract interpretation seems to provide clean foundation for diverse solving methods such as constraint programming, temporal reasoning and mixed integer programming. We believe the crux of the matter is to combine these methods in order to take the best from each world. Combination among solvers is also studied in satisfiability modulo theories, but on a more logical level: which combination of logical languages preserves some properties? We think the Nelson-Oppen combination provides little details on how the theories are actually combined in practice. We would like to close the gap between theory and practice. Abstract interpretation provides a nice theory to define constraint solvers as abstract domains, which are ordered structures with some operators. The definition of these abstract domains is very close to how they are actually implemented, a property we find very interesting.

Product of abstract domains, and thus their combinations, is also part of the theory of abstract interpretation, and this is a reason why this theory is so interesting. In general terms, we call domain transformers the abstract domains which are parametrized by one or more abstract domains. Hence a product is a domain transformer too. In ICTAI 2019 paper, we introduced a simple domain transformer in which two abstract domains are combined logically. For instance, consider x + y < 4 /\ 2 * z + 4 * w < 3 * a. The first part x + y < 4 is efficiently treated in the octagon abstract domain, whilst the second part is better treated in polyhedron, an abstract domain encapsulating a linear programming solver. The shortcoming of the logical product (of ICTAI 2019) is that two constraints in two different abstract domains cannot share variables. This paper remedies to this issue and propose two domain transformers able to share information among abstract domains sharing variables. In addition, we show how to add in modular way, new domain transformers to an existing product of abstract domains. In other terms, the cooperation scheme among solvers is not fixed inside the solver, but can be modularly defined as an abstract domain itself. You will find various examples illustrating the introduced domain transformers in the paper.

Future work include the formalization of conflicts learning inside this framework, possibly trying to simplify what has been achieved with ACDCL (see D'Silva et al., POPL '13, 2013), and the study of other techniques such as cuts in linear programming.

@article{TPLP2020-Talbot,
  author={Talbot, Pierre and Monfroy, \'{E}ric and Truchet, Charlotte},
  title = {{Modular Constraint Solver Cooperation via Abstract Interpretation}},
  journal = {{Theory and Practice of Logic Programming}},
  year = {2020},
  volume={20},
  doi={10.1017/S1471068420000162},
  number={6},
  publisher={{Cambridge University Press}},
  pages={848--863}
}

Story of this paper

This paper is a first step of my postdoc in the university of Nantes. This work started with the idea that we could use the decomposition of global constraints into primitive constraints to treat groups of similar constraints with suited abstract domains (such as octagon for difference constraints). This is why I experimented on a scheduling problem (RCPSP) with the decomposition of the cumulative global constraint. Although the experimentations do not show improvement on the solving time, I think the formal framework is very neat as it encapsulates a traditional constraint solver in an abstract domain, which is then composed via equivalence constraints with a difference logic solver (octagon domain).

The next step is to integrate a conflict learning in this framework, and hopefully it will lead to better speed-up on RCPSP and other problems.

@inproceedings{ICTAI19-Talbot,
  author={Talbot, Pierre and Cachera, David and Monfroy, \'{E}ric and Truchet, Charlotte},
  booktitle={{31st IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2019)}},
  title={{Combining Constraint Languages via Abstract Interpretation}},
  year={2019},
  pages={50--58},
  doi={10.1109/ICTAI.2019.00016},
  ISBN={978-1-7281-3798-8 },
  address = {Portland, USA},
  month={4--6 November}
}

Story of this paper

This paper summarizes and extends the chapters 3 and 4 of my dissertation. In comparison to the conference version, the provided extended version gives the proofs and additional contents in appendix, with minor corrections on the definitions of lattices (Section 3). I present the syntax and semantics of the programming language "spacetime" which merges several paradigms:

Concurrent constraint programming (CCP) which was introduced some 30 years ago by Saraswat et al. I think CCP is really beautiful because every syntactically correct programs already have good semantical properties (closure operator). However, it never really had a practical implementation, although languages such as Oz took some ideas from it. Spacetime incorporates the ideas of processes exchanging information through ordered structures (lattices in spacetime) and the "ask and tell" operators of CCP.
Synchronous programming, more precisely Esterel introduced by Berry and others some 30 years ago too. This paradigm is not very well-known neither although its core idea is very useful for programming: it forces the processes in a program to obey a global clock. In each instant of the clock, the processes can only perform a limited number of actions, so we can check at compile-time that they do not generate race conditions (for example if two processes would write contradictory information on a variable). I believe that time is one of the most important concept when programming concurrent systems, and I think synchronous programming should be more well-known!
Constraint programming is a declarative paradigm to solve constraint satisfaction problems (CSP). Operationally, constraint solvers explore finite combinatorial state space using a backtracking algorithm.

These paradigms do not seem to have much in common, but spacetime is actually a merge of the two first paradigms, which is applied to CSP solving. You can imagine spacetime as a concurrent Prolog with a time abstraction to synchronize the unfolding of nondeterministic predicates. The main idea is that in each instant of the program, we explore one node of the state space (usually a tree-shaped structure). This way, the processes are forced to cooperate as everybody must finish to explore one node before the next is explored. In the paper, we present the CSP state space, and various search strategies and their compositions (key point: a search strategy is a process, therefore we can compose them like we compose processes!).

Spacetime differs substantially from known paradigms, since it merges paradigms that are not themselves mainstream and well-known. Nevertheless, I think the language can be improved and simplified. I wish to make the spacetime environment easy to use, and to write tutorial explaining how it functions.

My next work on spacetime is to add an additional feature called "universe", which are first-class state space. It is actually very useful to program so called "restart-based search strategy" and nested search. I improved a lot the ideas that were sketched in the dissertation, but I still need to experiment and finish the implementation. Another work I really would like to attempt is to use spacetime as a target to compile various languages such as Esterel, Prolog and CHR.

@inproceedings{PPDP19-Talbot,
 author = {Talbot, Pierre},
 title = {{Spacetime Programming: A Synchronous Language for Composable Search Strategies}},
 booktitle = {{Proceedings of the 21st International Symposium on Principles and Practice of Declarative Programming (PPDP 2019)}},
 year = {2019},
 month = {7--9 October},
 isbn = {978-1-4503-7249-7},
 location = {Porto, Portugal},
 pages = {18:1--18:16},
 articleno = {18},
 numpages = {16},
 url = {http://doi.acm.org/10.1145/3354166.3354183},
 doi = {10.1145/3354166.3354183},
 acmid = {3354183},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {concurrent constraint programming, constraint satisfaction problem, search strategy, synchronous programming},
}

Story of this paper

This paper is a draft of the ICTAI 2019 paper, so please read and cite the ICTAI version.

@inproceedings{JFPC19-Talbot,
  address = {Albi, France},
  title = {Octogones entiers pour le probl\`{e}me {RCPSP}},
  booktitle = {{Quinzi\`{e}mes Journ\'{e}es Francophones de Programmation par Contraintes (JFPC 2019)}},
  author = {Talbot, Pierre and Cachera, David and Monfroy, \'{E}ric and Truchet, Charlotte},
  month = {12--14 June},
  year = {2019},
  pages = {33--42},
}

Story of this dissertation

This dissertation presents two things: a formalism of constraint programming based on lattice theory, and a programming language called spacetime. Both parts are linked because spacetime is defined on lattice structures, and is used to write search strategy exploring constraint problems. For a summary and improved version of a fragment (chapters 3 and 4) of spacetime, please see PPDP 2019 paper.

Currently, I am writing a survey with Kazunori Ueda and Peter Van Roy which improves and summarizes the two first chapters of this dissertation. I think the result will be more digest and precise, but work remained to be done; I hope to finish this up before 2020.

Chapter 7 was explained in the ICMC 2017 paper and should be cited if you refer to the musical application of spacetime (rather than the language).

Chapter 8 is basically a translation of the JFPC 2017 paper.

@phdthesis{dissertation-talbot,
  author = {Pierre Talbot},
  title = {{Spacetime Programming: A Synchronous Language for Constraint Search}},
  school = {Sorbonne University},
  year = {2018},
}

Story of this paper

The starting point of this work is to observe that constraint programming and music should share a lot in common since they are both manipulating relations. However this is not the case in practice, and I believe it is because constraint programming is not very interactive: we state the problem and then wait for the solver to give us a solution. In this work, I sketch a system that allows the composer to interact dynamically with the solving process, so she knows why a solution is choosen. The composer can also interact with the process by dynamically adding new constraints.

This work is essentially a first step towards constraint-based computer-aided composition system. I think there is much to be done in this area, but current constraint solver are too static to be completely usable in this context. Perhaps when spacetime will be completely done, I will return to this application and explore it further!

@inproceedings{ICMC17-Talbot,
  author = {Talbot, Pierre and Agon, Carlos and Esling, Philippe},
  title = {{Interactive computer-aided composition with constraints}},
  booktitle = {Proceedings of the 2017 International Computer Music Conference (ICMC 2017)},
  address = {Shanghai, China},
  pages = {265--270},
  year =   {2017},
  month =    {16--20 October},
  address = {Shanghai, China},
  publisher = {Shanghai Conservatory of Music},
}

Story of this paper

This paper is a collaboration with Clément Poncelet on using spacetime for model checking with constraints. I do hope we find the time to pursue this work, but I first need to integrate the novel version of universe into the compiler of spacetime.

This work was translated in English and slightly improved in my dissertation.

@inproceedings{JFPC17-Talbot,
  author = {Talbot, Pierre and Poncelet, Cl\'{e}ment},
  title =  {{Langage pour la v\'{e}rification de mod\`{e}les par contraintes}},
  booktitle = {{Treizi\`{e}mes journ\'{e}es Francophones de Programmation par Contraintes (JFPC 2017)}},
  address = {Montreuil sur Mer, France},
  year = {2017},
  month = {13--15 June},
  pages = {201--211}
}

Story of this paper

This paper was my first paper on the language spacetime that I wrote for the doctoral program of IJCAI 2017. It has been totally subsumed by my PPDP 2019 paper.

It stays here for completeness, but please cite PPDP 2019 instead.

@inproceedings{IJCAI17-Talbot,
  author    = {Pierre Talbot},
  title     = {Search Strategies as Synchronous Processes (Extended Abstract)},
  booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on
               Artificial Intelligence, {IJCAI} 2017, Melbourne, Australia, August
               19-26, 2017},
  pages     = {5213--5214},
  year      = {2017},
  doi       = {10.24963/ijcai.2017/766},
  url       = { https://doi.org/10.24963/ijcai.2017/766},
}

Home Research Teaching Outreach Contact