George Katsirelos

I am a researcher at the EkINocs team of the MIA Paris unit at INRAE.

Research

I work on all aspects of combinatorial optimization, focusing especially on techniques and problems arising in constraint programming and Boolean satisfiability.

DBLP, Google Scholar

Conference papers

1. An Analysis of Core-guided Maximum Satisfiability Solvers Using Linear Programming. George Katsirelos. Proceedings of SAT 2023
2. Virtual Pairwise Consistency in Cost Function Networks. Pierre Montalbano, David Allouche, George Katsirelos, Simon de Givry, and Tomas Werner. Proceedings of CPAIOR 2023.
3. Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models. Valentin Durante, George Katsirelos, and Thomas Schiex. Proceedings of ICML 2022.
4. Structured Set Variable Domains in Bayesian Network Structure Learning. Fulya Trösser, Simon de Givry, George Katsirelos. Proceedings of CP 2022.
5. Parallel Hybrid Best-First Search. Abdelkader Beldjilali, David Allouche, Pierre Montalbano, George Katsirelos and Simon de Givry. Proceedings of CP 2022.
6. Multiple-choice knapsack constraint in graphical models. Pierre Montalbano, Simon de Givry, George Katsirelos. Proceedings of CPAIOR 2022.
7. Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming. Fulya Trösser, Simon de Givry, George Katsirelos. Proceedings of IJCAI 2021. Supplementary material, Code
8. Relaxation-Aware Heuristics for Exact Optimization in Graphical Models. Fulya Trösser, Simon de Givry, George Katsirelos. Proceedings of CPAIOR 2020.
9. Chain Length and CSPs Learnable with Few Queries. Christian Bessiere, Clement Carbonnel, George Katsirelos. Proceedings of AAAI 2020.
10. Guaranteed Diversity & Quality for the Weighted CSP. Thomas Schiex, Manon Ruffini, Jelena Vucinic, Sophie Barbe, George Katsirelos and Simon de Givry. Proceedings of ICTAI 2019.
11. A Hybrid Approach for Exact Coloring of Massive Graphs. Emmanuel Hebrard and George Katsirelos. Proceedings of CPAIOR 2019. code
12. Clause Learning and New Bounds for Graph Coloring. Emmanuel Hebrard and George Katsirelos. Proceedings of CP 2018. Best paper award. code
13. Conflict Directed Clause Learning for the Maximum Weighted Clique Problem. Emmanuel Hebrard and George Katsirelos. Proceedings of IJCAI 2018.
14. Clique Cuts in Weighted Constraint Satisfaction. Simon de Givry and George Katsirelos. Proceedings of CP 2017.
15. Ranking Constraints. Christian Bessiere, Emmanuel Hebrard, George Katsirelos, Zeynep Kiziltan and Toby Walsh. Proceedings of IJCAI 2016.
16. Finding a collection of MUSes incrementally. Fahiem Bacchus and George Katsirelos. Proceedings of CPAIOR 2016.
17. Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP. David Allouche, Simon de Givry, George Katsirelos, Thomas Schiex and Matthias Zytnicki. Proceedings of CP 2015.
18. Using Minimal Correction Sets to more Efficiently Compute Minimal Unsatisfiable Sets. Fahiem Bacchus and George Katsirelos. Proceedings of CAV 2015
19. Reasoning about Connectivity Constraints. Christian Bessiere, Emmanuel Hebrard, George Katsirelos and Toby Walsh. Proceedings of IJCAI 2015.
20. Relaxation Search: a Simple Way of Managing Optional Clauses. Fahiem Bacchus, Jessica Davies, Maria Tsimpoukelli and George Katsirelos. Proceedings of AAAI 2014.
21. The Balance Constraint Family. Christian Bessiere, Emmanuel Hebrard, George Katsirelos, Zeynep Kiziltan, Emilie Picard-Cantin, Claude-Guy Quimper and Toby Walsh. Proceedings of CP 2014.
22. Detecting and Exploiting Subproblem Tractability. Christian Bessiere,Clement Carbonnel, Emmanuel Hebrard, George Katsirelos and Toby Walsh. Proceedings of IJCAI 2013.
23. Constraint Acquisition via Partial Queries. Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of IJCAI 2013.
24. Resolution and Parallelizability: Barriers to the Efficient Parallelization of SAT Solvers. George Katsirelos, Ashish Sabharwal, Horst Samulowitz and Laurent Simon. Proceedings of AAAI 2013.
25. The SeqBin constraint revisited. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CP 2012. An extended version of this, including all proofs, is available on arxiv.
26. Computational Protein Design as a Cost Function Network Optimization Problem. David Allouche, Seydou Traoré, Isabelle André, Simon de Givry, George Katsirelos, Sophie Barbe and Thomas Schiex. Proceedings of CP 2012.
27. Eigenvector centrality in industrial SAT instances. George Katsirelos and Laurent Simon. Proceedings of CP 2012.
28. Learning Polynomials over GF(2) in a SAT Solver (Poster Presentation). George Katsirelos, Laurent Simon. Proceedings of SAT 2012, LNCS 7317, 496--497, 2012. Published version.
29. Complexity of and Algorithms for Borda Manipulation. Jessica Davies, George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of AAAI-2011, 2011. Published version. Outstanding paper award
30. Decomposition of the NValue Constraint. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of CP-2010, LNCS 6308, 114--128, 2010. Published version.
31. On The Complexity and Completeness of Static Constraints for Breaking Row and Column Symmetry. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CP-2010, LNCS 6308, 305--320, 2010. Published version.
32. Symmetries of Symmetry Breaking Constraints. George Katsirelos, Toby Walsh. Proceedings of ECAI-2010, 861--866, 2010. Published version.
33. A Restriction of Extended Resolution for Clause Learning SAT Solvers. Gilles Audemard, George Katsirelos and Laurent Simon. Proceedings of AAAI-2010, 15-20, 2010. Published version.
34. Propagating Conjunctions of AllDifferent Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of AAAI-2010, 27-32, 2010. Published version.
35. Restricted Global Grammar Constraints. George Katsirelos, Sebastian Maneth, Nina Narodytska and Toby Walsh. Proceedings of CP-2009, LNCS 5732, 501-508, 2009. Published version.
36. Circuit Complexity and Decompositions of Global Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of IJCAI-2009, 2009. Published version.
37. Decompositions of All Different, Global Cardinality and Related Constraints. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh. Proceedings of IJCAI-2009, 2009. Published version.
38. Reformulating Global Grammar Constraints. George Katsirelos, Nina Narodytska and Toby Walsh. Proceedings of CPAIOR-2009, LNCS 5547, 132-147, 2009. Published version.
39. Combining Symmetry Breaking and Global Constraints. George Katsirelos, Nina Narodytska, and Toby Walsh. "Recent Advances in Constraints", Post-conference proceedings of CSCLP-2008, LNAI 5655, 2009. Published version.
40. The Weighted CFG Constraint. George Katsirelos, Nina Narodytska and Toby Walsh, Proceedings of CP-AI-OR 2008, LNCS 5015, 323-327, 2008. Published version.
41. A Compression Algorithm for Large Arity Extensional Constraints. George Katsirelos and Toby Walsh, Proceedings of CP-2007, LNCS 4741, 379-393, 2007. Published version.
42. Generalized Nogoods in CSPs. George Katsirelos and Fahiem Bacchus, The twentieth national conference on artificial intelligence -- AAAI-05. Published version.
43. Unrestricted Nogood Recording in CSP search. George Katsirelos and Fahiem Bacchus, Ninth International Conference on Principles and Practice of Constraint Programming--CP 2003. Extended version. Published version.
44. GAC on conjunctions of constraints. G. Katsirelos and F. Bacchus, Principles and Practice of Constraint Programming--CP 2001, pages 610--614, 2001. Published version

Journal papers

1. Learning Constraints through Partial Queries. Christian Bessiere, Clément Carbonnel, Anton Dries, Emmanuel Hebrard, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Kostas Stergiou, Dimosthenis C Tsouros, Toby Walsh. Artificial Intelligence, 2023. DOI
2. Gene Regulatory Network Inference Methodology for Genomic and Transcriptomic Data Acquired in Genetically Related Heterozygote Individuals. Lise Pomiès, Céline Brouard, Harold Duruflé, Élise Maigné, Clément Carré, Louise Gody, Fulya Trösser, George Katsirelos, Brigitte Mangin, Nicolas B. Langlade and Simon de Givry. Bioinformatics, 38(17), 4127-4134, 2022. DOI
3. Guaranteed Diversity and Optimality in Cost Function Network Based Computational Protein Design Methods. Manon Ruffini, Jelena Vucinic, Simon de Givry, George Katsirelos, Sophie Barbe, Thomas Schiex. Algorithms 14, no. 6: 168. 2021. DOI
4. Constraint and Satisfiability Reasoning for Graph Coloring. Emmanuel Hebrard and George Katsirelos. Journal of Artificial Intelligence Research (JAIR) 69: 33-65, 2020. DOI
5. Multi-Language Evaluation of Exact Solvers in Graphical Model Discrete Optimization. Barry Hurley, Barry O'Sullivan, David Allouche, George Katsirelos, Thomas Schiex, Matthias Zytnicki, Simon de Givry. Constraints, 2016.
6. Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules. Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh, Lirong Xia. Artificial Intelligence 217: 20-42, 2014
7. Computational protein design as an optimization problem. David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, Simon de Givry, George Katsirelos, Barry O'Sullivan, Steven D. Prestwich, Thomas Schiex, Seydou Traoré. Artificial Intelligence 212: 59-79, 2014.
8. A New Framework for Computational Protein Design through Cost Function Network Optimization. S. Traoré, D. Allouche, I. André, S. de Givry, G. Katsirelos, T. Schiex, S. Barbé. Bioinformatics 29(17):2129-2136, 2013.
9. The Complexity of Integer Bound Propagation. Lucas Bordeaux, George Katsirelos, Nina Narodytska and Moshe Y. Vardi. In Journal of Artificial Intelligence Research (JAIR), 40, 657--676, 2011. Published version.
10. The Weighted Grammar Constraint. George Katsirelos, Nina Narodytska and Toby Walsh. Annals of Operations Research, 2010. Published version

Selected Workshop papers

1. An Empirical Study of Borda Manipulation. Jessica Davies, George Katsirelos, Nina Narodytska and Toby Walsh. Third International Workshop on Computational Social Choice, COMSOC-2010, 2010. (link)
2. Two Encodings of DNNF Theories. Jean Christoph Jung, Pedro Barahona, George Katsirelos and Toby Walsh. ECAI'08 Workshop on Inference methods based on Graphical Structures of Knowledge, 2008. (link)

Theses

1. Exact Methods for Bayesian Network Structure Learning and Cost Function Networks. Fulya Trösser, PhD, Université de Toulouse, 2022.
2. Nogood Processing in CSPs. George Katsirelos, PhD, University of Toronto, 2008.

Software

• ELSA is a solver for the Bayesian Network Structure Learning (BNSL) problem, developed by Fulya Trösser based on van Beek and Hoffmann's CPBayes. It combines a variety of techniques from constraint programming with a cut generation algorithm and a greedy linear solver. It is described in [Trösser, de Givry, and Katsirelos, IJCAI 2021] and [Trösser, de Givry, and Katsirelos, CP 2022]. You can download a tarball of the latest version (corresponding to the CP22 paper).
• ChromSAT is a solver for the graph coloring problem, which combines constraint- and satisfiability-based reasoning along with a few novel ideas that make it perform well both on small graphs (a few hundred vertices) and on graphs with millions of vertices. It was developed in collaboration with Emmanuel Hebrard and decsribed in [Hebrard and Katsirelos, CP 2018], [Hebrard and Katsirelos, JAIR 2020] and [Hebrard and Katsirelos, CPAIOR 2019]. It is available on github.
• MCSMUS is a state-of-the-art tool to extract MUSes from CNF formulas, described in [Bacchus and Katsirelos, CAV 2015] and [Bacchus and Katsirelos, CPAIOR 2016]. It can extract either a single MUS or all MUSes and comes with MiniSAT, Glucose and lingeling backends. Its source is available on Bitbucket.
• GlucosER is a CDCL (conflict-driven clause learning) SAT solver that uses a restriction of extended resolution. The objective is to get significant speedups in some instances due to the more powerful proof system, without sacrificing performance compared to current CDCL solvers. For more, see [Audemard, Katsirelos and Simon, AAAI-2010]. Download the source tarball of glucosER 1.0 or get a statically linked linux 32-bit binary. Note that you need boost to compile glucosER.
• Minicsp is a clause learning CSP solver that I developed based on the ideas in my thesis (see [Katsirelos and Bacchus, AAAI-2005], or my thesis) and integrates some improved techniques on clause learning in CSP that were developed later.
• toulbar2 is a solver for the weighted constraint satisfaction problem (WCSP), also known as exact maximum a posteriori (MAP) inference in Markov Random Fields (MRF). It is developed by large group of researchers, led by Simon de Givry. Some of my contributions to it are described in [Montalbano, de Givry, Katsirelos, CPAIOR 2022][Rufini et al, Algorithms 2021][Trösser, de Givry, and Katsirelos, CPAIOR 2020], [Schiex et al, ICTAI 2019], [de Givry and Katsirelos, CP 2017], [Hurley et al, Constraints 2016], [Allouche et al, CP 2015]. We have used toulbar2 for many applications, notably Computational Protein Design (CPD) ([Rufini et al, Algorithms 2021], [Schiex et al, ICTAI 2019], [Allouche et al, AIJ 2014], [Allouche et al, Bioinformatics 2013], [Allouche et al, CP2012]).

George Katsirelos