Unary Integer Linear Programming with Structural Restrictions

D 2018

Unary Integer Linear Programming with Structural Restrictions

EIBEN, Eduard, Robert GANIAN, Dusan KNOP and Sebastian ORDYNIAK

Basic information

Original name

Unary Integer Linear Programming with Structural Restrictions

Authors

EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Dusan KNOP (203 Czech Republic) and Sebastian ORDYNIAK (276 Germany)

Edition

USA, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, p. 1284-1290, 7 pp. 2018

Publisher

ijcai.org

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/18:00106814

Organization unit

Faculty of Informatics

ISBN

978-0-9992411-2-7

ISSN

DOI

http://dx.doi.org/10.24963/ijcai.2018/179

UT WoS

000764175401059

Keywords in English

Integer Linear Programming; Classical Complexity

Abstract

V originále

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.

Citovat

EIBEN, Eduard, Robert GANIAN, Dusan KNOP and Sebastian ORDYNIAK. Unary Integer Linear Programming with Structural Restrictions. Online. In Jerome Lang. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. USA: ijcai.org, 2018, p. 1284-1290. ISBN 978-0-9992411-2-7. Available from: https://dx.doi.org/10.24963/ijcai.2018/179.

@inproceedings{1523777,
   author = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian},
   address = {USA},
   booktitle = {Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence},
   doi = {http://dx.doi.org/10.24963/ijcai.2018/179},
   editor = {Jerome Lang},
   keywords = {Integer Linear Programming; Classical Complexity},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-0-9992411-2-7},
   pages = {1284-1290},
   publisher = {ijcai.org},
   title = {Unary Integer Linear Programming with Structural Restrictions},
   year = {2018}
}

TY  - JOUR
ID  - 1523777
AU  - Eiben, Eduard - Ganian, Robert - Knop, Dusan - Ordyniak, Sebastian
PY  - 2018
TI  - Unary Integer Linear Programming with Structural Restrictions
PB  - ijcai.org
CY  - USA
SN  - 9780999241127
KW  - Integer Linear Programming
KW  - Classical Complexity
N2  - 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.
ER  -

EIBEN, Eduard, Robert GANIAN, Dusan KNOP and Sebastian ORDYNIAK. Unary Integer Linear Programming with Structural Restrictions. Online. In Jerome Lang. \textit{Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence}. USA: ijcai.org, 2018, p.~1284-1290. ISBN~978-0-9992411-2-7. Available from: https://dx.doi.org/10.24963/ijcai.2018/179.

Detailed Information on Publication Record