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).
Citations
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, 21(3):413-434, 2016
Tractability-preserving Transformations of Global Cost Functions
David Allouche, Christian Bessiere, Patrice Boizumault, Simon de Givry, Patricia Gutierrez, Jimmy HM. Lee, Ka Lun Leung, Samir Loudni, Jean-Philippe Métivier, Thomas Schiex, Yi Wu
Artificial Intelligence, 238:166-189, 2016
Soft arc consistency revisited
Martin Cooper, Simon de Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki, and Thomas Werner
Artificial Intelligence, 174(7-8):449-478, 2010
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
- Presentation
- Downloads
- Benchmark libraries
- Tutorials
- Use cases
- User Guide
- What is toulbar2
- How do I install it ?
- How do I test it ?
- Using it as a black box
- Quick start
- Command line options
- General control
- Preprocessing
- Initial upper bounding
- Tree search algorithms and tree decomposition selection
- Variable neighborhood search algorithms
- Node processing & bounding options
- Branching, variable and value ordering
- Diverse solutions
- Console output
- File output
- Probability representation and numerical control
- Random problem generation
- Input formats
- How do I use it ?
- References
- Reference Manual
- Introduction
- Exact optimization for cost function networks and additive graphical models
- Modules
- Variable and cost function modeling
- Solving cost function networks
- Output messages, verbosity options and debugging
- Preprocessing techniques
- Variable and value search ordering heuristics
- Soft arc consistency and problem reformulation
- Virtual Arc Consistency enforcing
- NC bucket sort
- Variable elimination
- Propagation loop
- Backtrack management
- Libraries
- Documentation in pdf
- Publications