1 Search Results for "Altmanová, Katerina"

Document

DOI: 10.4230/LIPIcs.SEA.2018.10

Evaluating and Tuning n-fold Integer Programming

Authors: Katerina Altmanová, Dusan Knop, and Martin Koutecký

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract

In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Programming, 2013] showed an algorithm with runtime a^{O(rst + r^2s)} n^3, where a is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements which make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a "best" step, while finding only an "approximatelly best" step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n^3 to n^2 log n which yields the currently asymptotically fastest algorithm for n-fold IP. Finally, we tested the behavior of the algorithm with various values of the tuning parameter and different strategies of finding improving steps. First, we show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior. Second, our new strategy for finding "approximatelly best" steps wildly outperforms the original construction.

Cite as

Katerina Altmanová, Dusan Knop, and Martin Koutecký. Evaluating and Tuning n-fold Integer Programming. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{altmanova_et_al:LIPIcs.SEA.2018.10,
  author =	{Altmanov\'{a}, Katerina and Knop, Dusan and Kouteck\'{y}, Martin},
  title =	{{Evaluating and Tuning n-fold Integer Programming}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89454},
  doi =		{10.4230/LIPIcs.SEA.2018.10},
  annote =	{Keywords: n-fold integer programming, integer programming, analysis of algorithms, primal heuristic, local search}
}

Refine by Author
1 Altmanová, Katerina
1 Knop, Dusan
1 Koutecký, Martin

Refine by Classification
1 Software and its engineering → Software design engineering
1 Theory of computation → Parameterized complexity and exact algorithms

Refine by Keyword
1 analysis of algorithms
1 integer programming
1 local search
1 n-fold integer programming
1 primal heuristic

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Altmanová, Katerina"

Evaluating and Tuning n-fold Integer Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message