A Knowledge Compilation Take on Binary Polynomial Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929588076019712 |
|---|---|
| author | Capelli, Florent Del Pia, Alberto Di Gregorio, Silvia |
| author_facet | Capelli, Florent Del Pia, Alberto Di Gregorio, Silvia |
| contents | The Binary Polynomial Optimization (BPO) problem is defined as the problem of maximizing a given polynomial function over all binary points. The main contribution of this paper is to draw a novel connection between BPO and the field of Knowledge Compilation. This connection allows us to unify and significantly extend the state-of-the-art for BPO, both in terms of tractable classes, and in terms of existence of extended formulations. In particular, for instances of BPO with hypergraphs that are either $β$-acyclic or with bounded incidence treewidth, we obtain strongly polynomial algorithms for BPO, and extended formulations of polynomial size for the corresponding multilinear polytopes. The generality of our technique allows us to obtain the same type of results for extensions of BPO, where we enforce extended cardinality constraints on the set of binary points, and where variables are replaced by literals. We also obtain strongly polynomial algorithms for the variant of the above problems where we seek $k$ best feasible solutions, instead of only one optimal solution. Computational results show that the resulting algorithms can be significantly faster than current state-of-the-art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_00149 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Knowledge Compilation Take on Binary Polynomial Optimization Capelli, Florent Del Pia, Alberto Di Gregorio, Silvia Optimization and Control Discrete Mathematics The Binary Polynomial Optimization (BPO) problem is defined as the problem of maximizing a given polynomial function over all binary points. The main contribution of this paper is to draw a novel connection between BPO and the field of Knowledge Compilation. This connection allows us to unify and significantly extend the state-of-the-art for BPO, both in terms of tractable classes, and in terms of existence of extended formulations. In particular, for instances of BPO with hypergraphs that are either $β$-acyclic or with bounded incidence treewidth, we obtain strongly polynomial algorithms for BPO, and extended formulations of polynomial size for the corresponding multilinear polytopes. The generality of our technique allows us to obtain the same type of results for extensions of BPO, where we enforce extended cardinality constraints on the set of binary points, and where variables are replaced by literals. We also obtain strongly polynomial algorithms for the variant of the above problems where we seek $k$ best feasible solutions, instead of only one optimal solution. Computational results show that the resulting algorithms can be significantly faster than current state-of-the-art. |
| title | A Knowledge Compilation Take on Binary Polynomial Optimization |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2311.00149 |