{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:36Z","timestamp":1781345676855,"version":"3.54.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>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.\n\n\n\nWe 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.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/179","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:49:10Z","timestamp":1530769750000},"page":"1284-1290","source":"Crossref","is-referenced-by-count":7,"title":["Unary Integer Linear Programming with Structural Restrictions"],"prefix":"10.24963","author":[{"given":"Eduard","family":"Eiben","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity group, TU Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[{"name":"Algorithms group, University of Sheffield, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","theme":"Artificial Intelligence","location":"Stockholm, Sweden","acronym":"IJCAI-2018","number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2018,7,13]]},"end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:50:33Z","timestamp":1530769833000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/179"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/179","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}