New! toulbar2 won medals at XCSP 2024 and UAI 2022 Competitions!
New! Your Sudoku solved on your smartphone by toulbar2 (APK)

Presentation

About toulbar2

toulbar2 is an open-source C++ solver for cost function networks. It solves various combinatorial optimization problems.

The constraints and objective function are factorized in local functions on discrete variables. Each function returns a cost (a finite positive integer) for any assignment of its variables. Constraints are represented as functions with costs in {0, \(\infty\)} where \(\infty\) is a large integer representing forbidden assignments. toulbar2 looks for a non-forbidden assignment of all variables that minimizes the sum of all functions.

Its engine uses a hybrid best-first branch-and-bound algorithm exploiting soft arc consistencies. It incorporates a parallel variable neighborhood search method for better performance. See Publications.

toulbar2 won several medals in competitions on Max-CSP/COP (CPAI08, XCSP3 2022, 2023, and 2024) and probabilistic graphical models (UAI 2008, 2010, 2014, 2022 MAP task).

toulbar2 is now also able to collaborate with ML code that can learn an additive graphical model (with constraints) from data (see example at cfn-learn).

Authors

toulbar2 was originally developed by Toulouse (INRAE MIAT) and Barcelona (UPC, IIIA-CSIC) teams, hence the solver’s name.

Additional contributions by:

  • Caen University, France (GREYC) and University of Oran, Algeria for (parallel) variable neighborhood search methods

  • The Chinese University of Hong Kong and Caen University, France (GREYC) for global cost functions

  • Marseille University, France (LSIS) for tree decomposition heuristics

  • Ecole des Ponts ParisTech, France (CERMICS/LIGM) for INCOP local search solver

  • University College Cork, Ireland (Insight) for a Python interface in Numberjack and a portfolio dedicated to UAI graphical models Proteus

  • Artois University, France (CRIL) for an XCSP 2.1 format reader of CSP and WCSP instances

  • Université de Toulouse I Capitole (IRIT) and Université du Littoral Côte d’Opale, France (LISIC) for PILS local search solver

Citations

Acknowledgments

toulbar2 has been partly funded by the French Agence Nationale de la Recherche (projects STAL-DEC-OPT from 2006 to 2008, ANR-10-BLA-0214 Ficolofo from 2011 to 2014, and ANR-16-CE40-0028 DemoGraph from 2017 to 2021, PIA3 ANITI ANR-19-P3IA-0004 from 2019 to 2024) and a PHC PROCORE project number 28680VH (from 2013 to 2015). It is currently supported by ANITI2 (2024-2031) and ANR project GMLaAS (2025-2029).

License

MIT License

Copyright (c) 2022 toulbar2 team

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Detailed Content