|
|
 |
|
Jeudi 12 Septembre
| Heure: |
11:00 - 12:00 |
| Lieu: |
Salle C308, Institut Galilée, Université de Villetaneuse |
| Résumé: |
A Knowledge Compilation Take on Binary Boolean Optimization |
| Description: |
Florent Capelli The Binary Boolean Optimization (BPO) problem aims at finding the maximal value that a rational polynomial P(x) can take when x is supposed to be a vector with 0 and 1 values. This non-linear optimization problem has recently received renewed attention. Current techniques for solving it either involve to solve a linear relaxation of the problem or use dedicated algorithm exploiting some structure in the way monomials are interacting with one another, allowing one to skip large parts of the search space compared to the brute force approach. In this talk, we present and explore the consequences of an interesting connection between BPO instances and another well studied problem on Boolean functions: the Algebraic Model Counting (AMC) problem. Given a Boolean function f on variables X and a weight on each of its variable, the AMC problem aims at finding the sum of the weights of every satisfying assignments of f. This problem can encode a lot of different tasks by simply changing the underlying algebraic structure where the sum and products are made. This way, we show how one can reformulate BPO instances as an AMC problem on an algebraic structure known as the (max,+)-semiring. The consequences of this connection are manyfold. In particular, we are able to recover every known results on the tractablability of BPO problem from this connection and the existing literature on the complexity of AMC. More importantly, this connection allows us to discover new tractable classes for BPO and is flexible enough so that we can find tractable instances of the slight variations of BPO such as BPO with cardinality constraints or pseudo-Boolean BPO, two problems for which few tractability results where known. More importantly, this approach yields practical results: by running a modified version of d4, a tool originally made for knowledge compilation, so that it performs AMC on the (max,+)-semiring instead, we show that our approach is competitive with the existing ones on hard instances. This talk will cover a gentle presentation of the BPO problem and its connection with AMC. We will then give a quick overview on existing techniques for solving AMC that are based on Knowledge Compilation and how this approach is fruitful for solving extensions of the BPO problem. We will conclude by a presentation of the way d4 works and of our practical results. |
|
|
