October 27, 2023
@
11:00 AM
–
12:00 PM
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.
Bio: Florent Capelli is a Junior Professor I, the “Centre de Recherche de Informatique de Lens” at the Université d’Artois in France. He worked for six years as an assistant professor at Université de Lille before joining l’Université d’Artois. He received his PhD at Université Paris Diderot in 2016 and worked for one year as a postdoctoral student at Birkbeck College in London. Dr. Capelli’s expertise covers knowledge compilation, data bases theory, graph theory and computational complexity theory. He recently obtained fundings from by the Agence National de Recherche (ANR) for his project KCODA, Knowledge Compilation for Data Analysis, that aims at importing techniques and tools from Knowledge Compilation for solving challenging problems in optimization and databases.
Food will be provided at the end of the event for those who RSVP to the event on Outlook.
Free