Publication details

Unary Integer Linear Programming with Structural Restrictions

Authors

EIBEN Eduard GANIAN Robert KNOP Dusan ORDYNIAK Sebastian

Year of publication 2018
Type Article in Proceedings
Conference Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.24963/ijcai.2018/179
Keywords Integer Linear Programming; Classical Complexity
Description Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.
Related projects: