README.md 9.52 KB
Newer Older
1
# toulbar2
2
## Exact optimization for cost function networks and additive graphical models 
3

Thomas Schiex's avatar
Thomas Schiex committed
4
5
master: [![Build Status](https://travis-ci.com/toulbar2/toulbar2.svg?branch=master)](https://travis-ci.com/toulbar2/toulbar2)
cpd: [![Build Status](https://travis-ci.com/toulbar2/toulbar2.svg?branch=cpd)](https://travis-ci.com/toulbar2/toulbar2)
6

7
8
## What is toulbar2?

Thomas Schiex's avatar
Thomas Schiex committed
9
10
11
12
13
toulbar2 is an open-source black-box C++ optimizer for cost function
networks and discrete additive graphical models. It can read a variety
of formats. The optimized criteria and feasibility should be provided
factorized in local cost functions on discrete variables. Constraints
are represented as functions that produce costs that exceed a
14
15
16
user-provided primal bound. toulbar2 looks for a non-forbidden assignment 
of all variables that optimizes the sum of all functions (a decision 
NP-complete problem).
Thomas Schiex's avatar
Thomas Schiex committed
17
18

toulbar2 won several competitions on deterministic and probabilistic
19
20
21
22
23
24
25
26
27
28
29
30
31
32
graphical models:

* Max-CSP 2008 Competition [CPAI08][cpai08] (winner on 2-ARY-EXT and N-ARY-EXT)
* Probabilistic Inference Evaluation [UAI 2008][uai2008] (winner on several MPE tasks, inra entries)
* 2010 UAI APPROXIMATE INFERENCE CHALLENGE [UAI 2010][uai2010] (winner on 1200-second MPE task)
* The Probabilistic Inference Challenge [PIC 2011][pic2011] (second place by ficolofo on 1-hour MAP task)
* UAI 2014 Inference Competition [UAI 2014][uai2014] (winner on all MAP task categories, see Proteus, Robin, and IncTb entries)

[cpai08]: http://www.cril.univ-artois.fr/CPAI08/
[uai2008]: http://graphmod.ics.uci.edu/uai08/Evaluation/Report
[uai2010]: http://www.cs.huji.ac.il/project/UAI10/summary.php
[pic2011]: http://www.cs.huji.ac.il/project/PASCAL/board.php
[uai2014]: http://www.hlt.utdallas.edu/~vgogate/uai14-competition/leaders.html 

33

Thomas Schiex's avatar
Thomas Schiex committed
34
35
36
37
## Installation from binaries

You can install toulbar2 directly using the package manager in Debian
and Debian derived Linux distributions (Ubuntu, Mint,...). For the
Thomas Schiex's avatar
Thomas Schiex committed
38
most recent version, compile from source.
Thomas Schiex's avatar
Thomas Schiex committed
39

40

Thomas Schiex's avatar
Thomas Schiex committed
41
## Download
42

Thomas Schiex's avatar
Thomas Schiex committed
43
44
45
Download the latest release from GitHub
(https://github.com/toulbar2/toulbar2) or similarly use tag versions,
e.g.:
46
47
48

    git clone --branch 1.0.0 https://github.com/toulbar2/toulbar2.git

49

Thomas Schiex's avatar
Thomas Schiex committed
50
51
52
## Installation from sources

Compilation requires git, cmake and a C++-11 capable compiler. 
53

Thomas Schiex's avatar
Thomas Schiex committed
54
Required library:
55
* libgmp-dev
Thomas Schiex's avatar
Thomas Schiex committed
56

Thomas Schiex's avatar
Thomas Schiex committed
57
Recommended libraries (default use):
58
* libboost-graph-dev
Thomas Schiex's avatar
Thomas Schiex committed
59
* libboost-iostreams-dev
60
61
* zlib1g-dev
* liblzma-dev
62

63
Optional libraries:
64
* libxml2-dev
65
* libopenmpi-dev
66
* libjemalloc-dev
67

68
GNU C++ Symbols to be defined if using Linux Eclipse/CDT IDE (no value needed):
69
* BOOST
70
71
* LINUX
* LONGDOUBLE_PROB
72
* LONGLONG_COST
73
* NARYCHAR
74
* OPENMPI
75
76
* WCSPFORMATONLY
* WIDE_STRING
77

78
Also C++11 should be set as the language standard.
79
80
81

Commands for compiling toulbar2 on Linux in directory toulbar2/src without cmake:

Simon de Givry's avatar
Simon de Givry committed
82
83
    bash
    cd src
84
    echo '#define Toulbar_VERSION "1.0.0"' > ToulbarVersion.hpp
85
    g++ -o toulbar2 -I. tb2*.cpp applis/*.cpp core/*.cpp globals/*.cpp incop/*.cpp search/*.cpp utils/*.cpp vns/*.cpp ToulbarVersion.cpp -std=c++11 -O3 -DNDEBUG \
86
     -DBOOST -DLINUX -DLONGDOUBLE_PROB -DLONGLONG_COST -DNARYCHAR -DWCSPFORMATONLY -DWIDE_STRING -lboost_graph -lboost_iostreams -lgmp -lz -llzma -static
87

Thomas Schiex's avatar
Thomas Schiex committed
88
Replace LONGLONG_COST by INT_COST to reduce memory usage by two and reduced cost range (costs must be smaller than 10^8).
89

90
91
Use OPENMPI flag and MPI compiler for a parallel version of toulbar2:

92
93
    bash
    cd src
94
    echo '#define Toulbar_VERSION "1.0.0"' > ToulbarVersion.hpp
95
    mpicxx -o toulbar2 -I. tb2*.cpp applis/*.cpp core/*.cpp globals/*.cpp incop/*.cpp search/*.cpp utils/*.cpp vns/*.cpp ToulbarVersion.cpp -std=c++11 -O3 -DNDEBUG \
96
     -DBOOST -DLINUX -DLONGDOUBLE_PROB -DLONGLONG_COST -DNARYCHAR -DOPENMPI -DWCSPFORMATONLY -DWIDE_STRING -lboost_graph -lboost_iostreams -lgmp -lz -llzma
97

98

99
100
101
102
103
## Authors

toulbar2 was originally developped by Toulouse (INRA MIAT) and Barcelona (UPC, IIIA-CSIC) teams, hence the name of the solver. 

Additional contributions by:
104
* Caen University, France (GREYC) and University of Oran, Algeria for (parallel) variable neighborhood search methods
105
106
107
108
109
110
111
112
113
114
* 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][incop] local search solver
* University College Cork, Ireland (Insight) for a Python interface in [NumberJack][numberjack] and a portfolio dedicated to UAI graphical models [Proteus][proteus]
* Artois University, France (CRIL) for an XCSP 2.1 format reader of CSP and WCSP instances

[incop]: http://imagine.enpc.fr/~neveub/incop/incoppresentation.html
[numberjack]: http://numberjack.ucc.ie/
[proteus]: https://github.com/9thbit/uai-proteus

115

116
117
118
119
## Citing

Please use one of the following references for citing toulbar2:

Thomas Schiex's avatar
Thomas Schiex committed
120
 * Multi-Language Evaluation of Exact Solvers in Graphical Model Discrete Optimization
121
 Barry Hurley, Barry O'Sullivan, David Allouche, George Katsirelos, Thomas Schiex, Matthias Zytnicki, Simon de Givry
122
123
 Constraints, 21(3):413-434, 2016

Thomas Schiex's avatar
Thomas Schiex committed
124
 * Tractability-preserving Transformations of Global Cost Functions
125
126
 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
127

Thomas Schiex's avatar
Thomas Schiex committed
128
 * Soft arc consistency revisited
129
 Martin Cooper, Simon de Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki, and Thomas Werner
130
131
 Artificial Intelligence, 174(7-8):449-478, 2010 

132

133
134
##  What are the algorithms inside toulbar2?

Thomas Schiex's avatar
Thomas Schiex committed
135
136
137
138
139
140
* Soft arc consistency (AC): 
Arc consistency for Soft Constraints
T. Schiex
Proc. of CP'2000. Singapour, September 2000.

* More soft arc consistencies (NC, DAC, FDAC):
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
 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, Los Angeles, USA, 2010

* 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 

205
206
207
208
209
210
211
212
213
214
* SCP branching (CPD branch): Fast search algorithms for Computational Protein Design.
S. Traoré, K.E. Roberts, D. Allouche, B. Donald, I. André, T. Schiex, S. Barbe.
Journal of Computational Chemistry, 2016.

* Guaranteed Free Energy computation (weighted model counting): Guaranteed 
Weighted Counting for Affinity Computation: Beyond Determinism and Structure 
C. Viricel, D. Simoncini, S. Barbe, T. Schiex. Proc. of the 22nd International 
Conference on Principles and Practice of Constraint Programming Toulouse, 
France. 5-9 september 2016

215
216
217
218
* 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
219

220
221
222
223
* 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
224

225
226
Copyright (C) 2006-2018, toulbar2 team.
toulbar2 is currently maintained by Simon de Givry, INRA - MIAT, Toulouse, France (simon.de-givry@inra.fr)