Publications

Conference talks

• talk on toulbar2 at ROADEF 2023, Rennes, France, February 21, 2023.

• ANITI webinar on toulbar2 for industrial applications : slides in English | talk in French

• talk on toulbar2 latest algorithmic features at ISMP 2018, Bordeaux, France, July 6, 2018.

• toulbar2 projects meeting at CP 2016, Toulouse, France, September 5, 2016.

Related publications

What are the algorithms inside toulbar2 ?

• Soft arc consistencies (NC, AC, DAC, FDAC)

  In the quest of the best form of local consistency for Weighted CSP, J. Larrosa & T. Schiex, In Proc. of IJCAI-03. Acapulco, Mexico, 2003.

• Soft existential arc consistency (EDAC)

  Existential arc consistency: Getting closer to full arc consistency in weighted csps, S. de Givry, M. Zytnicki, F. Heras, and J. Larrosa, In Proc. of IJCAI-05, Edinburgh, Scotland, 2005.

• Depth-first Branch and Bound exploiting a tree decomposition (BTD)

  Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP, S. de Givry, T. Schiex, and G. Verfaillie, In Proc. of AAAI-06, Boston, MA, 2006 .

• Virtual arc consistency (VAC)

  Virtual arc consistency for weighted csp, M. Cooper, S. de Givry, M. Sanchez, T. Schiex, and M. Zytnicki In Proc. of AAAI-08, Chicago, IL, 2008.

• Soft generalized arc consistencies (GAC, FDGAC)

  Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction, J. H. M. Lee and K. L. Leung, In Proc. of IJCAI-09, Pasadena (CA), USA, 2009.

• Russian doll search exploiting a tree decomposition (RDS-BTD)

  Russian doll search with tree decomposition, M Sanchez, D Allouche, S de Givry, and T Schiex, In Proc. of IJCAI-09, Pasadena (CA), USA, 2009.

• Soft bounds arc consistency (BAC)

  Bounds Arc Consistency for Weighted CSPs, M. Zytnicki, C. Gaspin, S. de Givry, and T. Schiex, Journal of Artificial Intelligence Research, 35:593-621, 2009.

• Counting solutions in satisfaction (#BTD, Approx_#BTD)

  Exploiting problem structure for solution counting, A. Favier, S. de Givry, and P. Jégou, In Proc. of CP-09, Lisbon, Portugal, 2009.

• Soft existential generalized arc consistency (EDGAC)

  A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction, J. H. M. Lee and K. L. Leung, In Proc. of AAAI-10, Boston, MA, 2010 .

• Preprocessing techniques (combines variable elimination and cost function decomposition)

  Pairwise decomposition for combinatorial optimization in graphical models, A Favier, S de Givry, A Legarra, and T Schiex, In Proc. of IJCAI-11, Barcelona, Spain, 2011.

• Decomposable global cost functions (wregular, wamong, wsum)

  Decomposing global cost functions, D Allouche, C Bessiere, P Boizumault, S de Givry, P Gutierrez, S Loudni, JP Métivier, and T Schiex, In Proc. of AAAI-12, Toronto, Canada, 2012.

• Pruning by dominance (DEE)

  Dead-End Elimination for Weighted CSP, S de Givry, S Prestwich, and B O’Sullivan, In Proc. of CP-13, pages 263-272, Uppsala, Sweden, 2013.

• Hybrid best-first search exploiting a tree decomposition (HBFS)

  Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP, D Allouche, S de Givry, G Katsirelos, T Schiex, and M Zytnicki, In Proc. of CP-15, Cork, Ireland, 2015.

• Unified parallel decomposition guided variable neighborhood search (UDGVNS/UPDGVNS)

  Iterative Decomposition Guided Variable Neighborhood Search for Graphical Model Energy Minimization, A Ouali, D Allouche, S de Givry, S Loudni, Y Lebbah, F Eckhardt, and L Loukil, In Proc. of UAI-17, pages 550-559, Sydney, Australia, 2017.

  Variable Neighborhood Search for Graphical Model Energy Minimization, A Ouali, D Allouche, S de Givry, S Loudni, Y Lebbah, L Loukil, and P Boizumault, Artificial Intelligence, 2020.

• Clique cut global cost function (clique)

  Clique Cuts in Weighted Constraint Satisfaction, S de Givry and G Katsirelos, In Proc. of CP-17, pages 97-113, Melbourne, Australia, 2017.

• Greedy sequence of diverse solutions (div)

  Guaranteed diversity & quality for the Weighted CSP, M Ruffini, J Vucinic, S de Givry, G Katsirelos, S Barbe, and T Schiex, In Proc. of ICTAI-19, pages 18-25, Portland, OR, USA, 2019.

• VAC-integrality based variable heuristics and initial upper-bound probing (vacint and rasps)

  Relaxation-Aware Heuristics for Exact Optimization in Graphical Models, F Trösser, S de Givry and G Katsirelos, In Proc. of CPAIOR-20, Vienna, Austria, 2020.

• Partition crossover iterative local search (pils)

  Iterated local search with partition crossover for computational protein design, François Beuvin, Simon de Givry, Thomas Schiex, Sébastien Verel, and David Simoncini, Proteins: Structure, Function, and Bioinformatics, 2021.

• Knapsack/generalized linear global constraint (knapsack/knapsackp)

  Multiple-choice knapsack constraint in graphical models, P Montalbano, S de Givry, and G Katsirelos, In Proc. of CP-AI-OR’2022, Los Angeles, CA, 2022.

• Parallel hybrid best-first search (parallel HBFS)

  Parallel Hybrid Best-First Search, A Beldjilali, P Montalbano, D Allouche, G Katsirelos, and S de Givry, In Proc. of CP-22, volume 235, pages 7:1-7:10, Haifa, Israel, 2022.

• Low rank block coordinate descent (LR-BCD)

  Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models, V Durante, G Katsirelos, and T Schiex, In Proc. of the 39th International Conference on Machine Learning (ICML), PMLR 162:5726-5741, 2022.

• Virtual Pairwise Consistency (pwc, hve)

  Virtual Pairwise Consistency in Cost Function Networks, P Montalbano, D Allouche, S de Givry, G Katsirelos, and T Werner In Proc. of CP-AI-OR’2023, Nice, France, 2023.

• Bi-Objective Combinatorial Optimization (global bounding constraint)

  Bi-Objective Discrete Graphical Model Optimization, S Buchet, D Allouche, S de Givry, and T Schiex In Proc. of CP-AI-OR’2024, Uppsala, Sweden, 2024.

toulbar2 for Combinatorial Optimization in Life Sciences

• Computational Protein Design

  Colom, Mireia Solà, et al. Deep Evolutionary Forecasting identifies highly-mutated SARS-CoV-2 variants via functional sequence-landscape enumeration. Research Square, 2022.

  XENet: Using a new graph convolution to accelerate the timeline for protein design on quantum computers Jack B. Maguire, Daniele Grattarola, Vikram Khipple Mulligan, Eugene Klyshko, Hans Melo. Plos Comp. Biology, 2021.

  Designing Peptides on a Quantum Computer, Vikram Khipple Mulligan, Hans Melo, Haley Irene Merritt, Stewart Slocum, Brian D. Weitzner, Andrew M. Watkins, P. Douglas Renfrew, Craig Pelissier, Paramjit S. Arora, and Richard Bonneau, bioRxiv, 2019.

  Computational design of symmetrical eight-bladed \(\beta\)-propeller proteins, Noguchi, H., Addy, C., Simoncini, D., Wouters, S., Mylemans, B., Van Meervelt, L., Schiex, T., Zhang, K., Tameb, J., and Voet, A., IUCrJ, 6(1), 2019.

  Positive Multi-State Protein Design, Jelena Vučinić, David Simoncini, Manon Ruffini, Sophie Barbe, Thomas Schiex, Bioinformatics, 2019.

  Cost function network-based design of protein-protein interactions: predicting changes in binding affinity, Clément Viricel, Simon de Givry, Thomas Schiex, and Sophie Barbe, Bioinformatics, 2018.

  Algorithms for protein design, Pablo Gainza, Hunter M Nisonoff, Bruce R Donald, Current Opinion in Structural Biology, 39:6-26, 2016.

  Fast search algorithms for computational protein design, Seydou Traoré, Kyle E Roberts, David Allouche, Bruce R Donald, Isabelle André, Thomas Schiex, and Sophie Barbe, Journal of computational chemistry, 2016.

  Comparing three stochastic search algorithms for computational protein design: Monte Carlo, replica exchange Monte Carlo, and a multistart, steepest-descent heuristic, David Mignon, Thomas Simonson, Journal of computational chemistry, 2016.

  Protein sidechain conformation predictions with an mmgbsa energy function, Thomas Gaillard, Nicolas Panel, and Thomas Simonson, Proteins: Structure, Function, and Bioinformatics, 2016.

  Improved energy bound accuracy enhances the efficiency of continuous protein design, Kyle E Roberts and Bruce R Donald, Proteins: Structure, Function, and Bioinformatics, 83(6):1151-1164, 2015.

  Guaranteed discrete energy optimization on large protein design problems, D. Simoncini, D. Allouche, S. de Givry, C. Delmas, S. Barbe, and T. Schiex, Journal of Chemical Theory and Computation, 2015.

  Computational protein design as an optimization problem, David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, Simon de Givry, George Katsirelos, Barry O’Sullivan, Steve Prestwich, Thomas Schiex, and Seydou Traoré, Journal of Artificial Intelligence, 212:59-79, 2014.

  A new framework for computational protein design through cost function network optimization, Seydou Traoré, David Allouche, Isabelle André, Simon de Givry, George Katsirelos, Thomas Schiex, and Sophie Barbe, Bioinformatics, 29(17):2129-2136, 2013.

• Genetics

  Optimal haplotype reconstruction in half-sib families, Aurélie Favier, Jean-Michel Elsen, Simon de Givry, and Andrès Legarra, ICLP-10 workshop on Constraint Based Methods for Bioinformatics, Edinburgh, UK, 2010.

  Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques, Marti Sanchez, Simon de Givry, and Thomas Schiex, Constraints, 13(1-2):130-154, 2008. See also Mendelsoft integrated in the QTLmap Quantitative Genetics platform from INRA GA dept.

• RNA motif search

  Darn! a weighted constraint solver for RNA motif localization, Matthias Zytnicki, Christine Gaspin, and Thomas Schiex, Constraints, 13(1-2):91-109, 2008.

• Agronomy

  Solving the crop allocation problem using hard and soft constraints, Mahuna Akplogan, Simon de Givry, Jean-Philippe Métivier, Gauthier Quesnel, Alexandre Joannon, and Frédérick Garcia, RAIRO - Operations Research, 47:151-172, 2013.

Other publications mentioning toulbar2

• Constraint Satisfaction, Distributed Constraint Optimization

  Graph Based Optimization For Multiagent Cooperation, Arambam James Singh, Akshat Kumar, In Proc. of AAMAS, 2019.

  Probabilistic Inference Based Message-Passing for Resource Constrained DCOPs, Supriyo Ghosh, Akshat Kumar, Pradeep Varakantham, In Proc. of IJCAI, 2015.

  SAT-based MaxSAT algorithms, Carlos Ansótegui and Maria Luisa Bonet and Jordi Levy, Artificial Intelligence, 196:77-105, 2013.

  Local Consistency and SAT-Solvers, P. Jeavons and J. Petke, Journal of Artificial Intelligence Research, 43:329-351, 2012.

• Data Mining and Machine Learning

  Pushing Data in CP Models Using Graphical Model Learning and Solving, Céline Brouard, Simon de Givry, and Thomas Schiex, In Proc. of CP-20, Louvain-la-neuve, Belgium, 2020.

  A constraint programming approach for mining sequential patterns in a sequence database, Jean-Philippe Métivier, Samir Loudni, and Thierry Charnois, In Proc. of the ECML/PKDD Workshop on Languages for Data Mining and Machine Learning, Praha, Czech republic, 2013.

• Timetabling, planning and POMDP

  Solving a Judge Assignment Problem Using Conjunctions of Global Cost Functions, S de Givry, J.H.M. Lee, K.L. Leung, and Y.W. Shum, In Proc. of CP-14, pages 797-812, Lyon, France, 2014.

  Optimally solving Dec-POMDPs as continuous-state MDPs, Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet, In Proc. of IJCAI, pages 90-96, 2013.

  A weighted csp approach to cost-optimal planning, Martin C Cooper, Marie de Roquemaurel, and Pierre Régnier, Ai Communications, 24(1):1-29, 2011.

  Point-based backup for decentralized POMDPs: Complexity and new algorithms, Akshat Kumar and Shlomo Zilberstein, In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, 1:1315-1322, 2010.

• Inference, Sampling, and Diagnostic

  Dubray, A., Derval, G., Nijssen, S., Schaus, P. Optimal Decoding of Hidden Markov Models with Consistency Constraints. In Proc. of Discovery Science (DS), LNCS 13601, 2022.

  Mohamed-Hamza Ibrahim, Christopher Pal and Gilles Pesant, Leveraging cluster backbones for improving MAP inference in statistical relational models, In Ann. Math. Artif. Intell. 88, No. 8, 907-949, 2020.

  C. Viricel, D. Simoncini, D. Allouche, S. de Givry, S. Barbe, and T. Schiex, Approximate counting with deterministic guarantees for affinity computations, In Proc. of Modeling, Computation and Optimization in Information Systems and Management Sciences - MCO’15, Metz, France, 2015.

  Discrete sampling with universal hashing, Stefano Ermon, Carla P Gomes, Ashish Sabharwal, and Bart Selman, In Proc. of NIPS, pages 2085-2093, 2013.

  Compiling ai engineering models for probabilistic inference, Paul Maier, Dominik Jain, and Martin Sachenbacher, In KI 2011: Advances in Artifcial Intelligence, pages 191-203, 2011.

  Diagnostic hypothesis enumeration vs. probabilistic inference for hierarchical automata models, Paul Maier, Dominik Jain, and Martin Sachenbacher, In Proc. of the International Workshop on Principles of Diagnosis, Murnau, Germany, 2011.

• Computer Vision and Energy Minimization

  Exact MAP-inference by Confining Combinatorial Search with LP Relaxation, Stefan Haller, Paul Swoboda, Bogdan Savchynskyy, In Proc. of AAAI, 2018.

• Computer Music

  Exploiting structural relationships in audio music signals using markov logic networks, Hélène Papadopoulos and George Tzanetakis, In Proc. of 38th International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pages 4493-4497, Canada, 2013.

  Modeling chord and key structure with markov logic, Hélène Papadopoulos and George Tzanetakis, In Proc. of the Society for Music Information Retrieval (ISMIR), pages 121-126, 2012.

• Inductive Logic Programming

  Extension of the top-down data-driven strategy to ILP, Erick Alphonse and Céline Rouveirol, In Proc. of Inductive Logic Programming, pages 49-63, 2007.

• Other domains

  An automated model abstraction operator implemented in the multiple modeling environment MOM, Peter Struss, Alessandro Fraracci, and D Nyga, In Proc. of the 25th International Workshop on Qualitative Reasoning, Barcelona, Spain, 2011.

  Modeling Flowchart Structure Recognition as a Max-Sum Problem, Martin Bresler, Daniel Prusa, Václav Hlavác, In Proc. of International Conference on Document Analysis and Recognition, Washington, DC, USA, 1215-1219, 2013.