EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

713. A Knowledge Compilation Take on Binary Polynomial Optimization

Invited abstract in session TC-4: Recent Advances in MINLP, stream MINLP.

Tuesday, 12:30-14:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Silvia Di Gregorio
University Sorbonne Paris Nord

Abstract

The Binary Polynomial Optimization (BPO) problem is defined as the problem of minimizing a given polynomial function over all binary points. The main contribution of this paper is to draw a novel connection between BPO and the problem of performing model counting over the (max, +) semiring on Boolean functions. This connection allows us to give a strongly polynomial algorithm that solves BPO with a hypergraph that is either beta-acyclic or with bounded incidence treewidth. This result unifies and significantly extends the known tractable classes of BPO. The generality of our technique allows us to deal also with extensions of BPO, where we enforce extended cardinality constraints on the set of binary points, and where we seek k best feasible solutions. We also extend our results to the significantly more general problem where variables are replaced by literals. Preliminary computational re- sults show that the resulting algorithms can be significantly faster than current state-of-the-art.

Keywords

Status: accepted

Back to the list of papers