Evaluating and Tuning n-fold Integer Programming

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403776" target="_blank" >RIV/00216208:11320/19:10403776 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/19:00333753

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=J6g0RJ51c1" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=J6g0RJ51c1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3330137" target="_blank" >10.1145/3330137</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Evaluating and Tuning n-fold Integer Programming

Popis výsledku v původním jazyce

In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, and so on, 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. Program., 2013] showed an algorithm with runtime ΔO(rst + r2s) n3, where Δ 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 that 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 &quot;best&quot; step, while finding only an &quot;approximately best&quot; step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n3 to n2 log n. 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 while significantly lowering the time the algorithm spends per single iteration. Second, our new strategy for finding &quot;approximately best&quot; steps wildly outperforms the original construction.

Název v anglickém jazyce

Evaluating and Tuning n-fold Integer Programming

Popis výsledku anglicky

In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, and so on, 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. Program., 2013] showed an algorithm with runtime ΔO(rst + r2s) n3, where Δ 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 that 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 &quot;best&quot; step, while finding only an &quot;approximately best&quot; step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n3 to n2 log n. 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 while significantly lowering the time the algorithm spends per single iteration. Second, our new strategy for finding &quot;approximately best&quot; steps wildly outperforms the original construction.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Experimental Algorithmics

ISSN

1084-6654

e-ISSN

—

Svazek periodika

2019

Číslo periodika v rámci svazku

24

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

1-22

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85069915485