toulbar2, an exact cost function network solver

Simon De Givry

► To cite this version:

Simon De Givry. toulbar2, an exact cost function network solver. 24ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision ROADEF 2023, Feb 2023, Rennes, France. hal-04021879

HAL Id: hal-04021879

https://hal.science/hal-04021879

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# 1 Introduction

toulbar2 is an open-source C++ solver for cost function networks, with an MIT license and a documentation describing its interfaces with C++ and python.<fnref n="1" />

The constraints and objective function are factorized in local functions on discrete variables. Each function returns a cost for any assignment of its variables. Constraints are represented as functions with costs in {0, τ} where τ is an upper bound cost associated with forbidden assignments. toulbar2 looks for a non-forbidden assignment of all variables that minimizes the sum of all functions. These functions can be nonlinear (quadratic terms or higher parity) and all variables must have a finite domain of reasonable size (less than a few hundred).

Using on the fly translation, toulbar2 can also directly solve optimization problems on other graphical models such as Maximum Probability Explanation on Bayesian networks, and Maximum A Posteriori on Markov random fields. It can also read partial weighted MaxSAT problems (wcnf format), pseudo-Boolean optimization problems (opb and qpbo formats), as well as constrained satisfaction and optimization problems (CSP and COP in XCSP3 format).<fnref n="2" />

toulbar2 exploits an *anytime* hybrid best-first branch-and-bound algorithm (HBFS) [1, 6] that tries to quickly provide good solutions together with an upper bound on the gap between the cost of each solution and the (unknown) optimal cost. Thus, even when it is unable to prove optimality, it will bound the quality of the solution provided. It can also apply a variable neighborhood search algorithm exploiting a problem decomposition (UDGVNS) [4]. Both algorithms are complete and can be run in parallel using OpenMPI [2, 4].

In addition, toulbar2 can also find a sequence of diverse solutions [5] or exhaustively enumerate solutions below a cost threshold and perform guaranteed approximate weighted counting of solutions. For stochastic graphical models, it computes the partition function, a #P-complete problem. Current work in toulbar2 is on multicriteria and bilevel optimization.

The presentation will give an overview of the solver and its results on two recent competitions.

# 2 XCSP’2022 Competition Results

The toulbar2 team participated to the XCSP’2022 competition. We used the default toulbar2 settings running HBFS for the *Main and Mini COP* tracks and parallel HBFS with 4 cores [2] for the *Parallel COP* track. toulbar2 terminates in second position in the Parallel and Mini COP tracks and fourth position in the Main COP track (see Table 1 for Mini COP).<fnref n="3" /> Among the five competitors in the Mini COP track (respectively 2 competitors in the Parallel COP track), it was able to solve the largest number of instances optimally (resp. 51/158 and 80/250).

<footnote n="1">1. https://github.com/toulbar2/toulbar2</footnote>

<footnote n="2">2. https://xcsp.org</footnote>

<footnote n="3">3. https://www.cril.univ-artois.fr/XCSP22</footnote>
<table><caption>TAB. 1 – XCSP'2022 Competition Results in the Mini Constraint Optimization Problem Track.</caption><thead><tr><th>solver</th><th>score</th><th>optimum</th><th>best bound</th></tr></thead><tbody><tr><td>Mistral</td><td><strong>93.00</strong></td><td>34</td><td><strong>99</strong></td></tr><tr><td>toulbar2</td><td>86.00</td><td><strong>51</strong></td><td>87</td></tr><tr><td>miniRBO</td><td>74.50</td><td>41</td><td>78</td></tr><tr><td>Sat4j-both</td><td>58.50</td><td>39</td><td>60</td></tr><tr><td>Sat4j-rs</td><td>43.00</td><td>33</td><td>46</td></tr><tr><td>Glasgow</td><td>31.50</td><td>21</td><td>34</td></tr></tbody></table>

## 3 UAI'2022 Competition

We also participated to a competition on probabilistic graphical models. We compared our solver **toulbar2** using two different methods, HBFS and UDGVNS, with **cplex** 20.1 and **daoopt** [3] on 120 instances provided as tuning benchmarks by the competition.<fnref n="4" /> The average results are shown in Fig. 1. In 1 hour, **toulbar2** solved optimally 86/120 instances whatever using HBFS or UDGVNS, whereas **daoopt** solved 92 instances and **cplex** 95. In less than two minutes, UDGVNS got the best solutions in average, while HBFS provided the best dual bounds.

<figure><img src="image_2.png" /><figcaption>FIG. 1 – Average normalized lower and upper bounds (y-axis) as time passes (x-axis, Left : 1hour, right : 2min.) for cplex, daoopt, and toulbar2 on UAI'2022 tuning benchmarks.</figcaption></figure>

## Références

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

[2] A Beldjilali, P Montalbano, D Allouche, G Katsirelos, and S de Givry. Parallel hybrid best-first search. In Proc. of CP-22, Haifa, Israel, 2022.

[3] L Otten, A Ihler, K Kask, and R Dechter. Winning the pascal 2011 map challenge with enhanced AND/OR branch-and-bound. In DISCML'12 Workshop, at NIPS'12, Lake Tahoe, NV, 2012.

[4] A Ouali, D Allouche, S de Givry, S Loudni, Y Lebbah, L Loukil, and P Boizumault. Variable neighborhood search for graphical model energy minimization. Artif. Intelli., 278, 2020.

[5] M Ruffini, J Vucinic, S de Givry, G Katsirelos, S Barbe, and T Schiex. Guaranteed diversity and optimality in cost function network based computational protein design methods. Algorithms, 14(6) :168, 2021.

[6] F Trösser, S de Givry, and G Katsirelos. Relaxation-aware heuristics for exact optimization in graphical models. In Proc. of CP-AI-OR'2020, pages 475–491, Vienna, Austria, 2020.

<footnote n="4">4. https://uaicompetition.github.io/uci-2022</footnote>