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

Created from the Publication Database of the Vienna University of Technology.