[Back]

E. Eiben, R. Ganian, D. Knop:
"Unary Integer Linear Programming with Structural Restrictions";
in: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence", International Joint Conferences on Artificial Intelligence, Schweden, 2018, ISBN: 978-0-9992411-2-7, 1284 - 1290.

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 wellstructured
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.

https://publik.tuwien.ac.at/files/publik_276178.pdf