Eisenbrand, Friedrich ;
Hunkenschröder, Christoph ;
Klein, KimManuel
Faster Algorithms for Integer Programs with Block Structure
Abstract
We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) blockstructure generalizing nfold integer programs which recently received considerable attention in the literature. An nfold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the nfold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B.
Our algorithm is based on a new upper bound on the l_1norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma.
Furthermore, we extend our techniques to the recently introduced treefold IPs, where we again present a more efficient algorithm in a generalized setting.
BibTeX  Entry
@InProceedings{eisenbrand_et_al:LIPIcs:2018:9053,
author = {Friedrich Eisenbrand and Christoph Hunkenschr{\"o}der and KimManuel Klein},
title = {{Faster Algorithms for Integer Programs with Block Structure}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {49:149:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9053},
URN = {urn:nbn:de:0030drops90537},
doi = {10.4230/LIPIcs.ICALP.2018.49},
annote = {Keywords: nfold, Treefold, Integer Programming}
}
2018
Keywords: 

nfold, Treefold, Integer Programming 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 