Parameterized algorithms for block-structured integer programs with large entries

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493513" target="_blank" >RIV/00216208:11320/24:10493513 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1137/1.9781611977912.29" target="_blank" >https://doi.org/10.1137/1.9781611977912.29</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611977912.29" target="_blank" >10.1137/1.9781611977912.29</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized algorithms for block-structured integer programs with large entries

Popis výsledku v původním jazyce

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1, ..., n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form (Equation presented) Ciyi = a and Diyi = bi for all i = 1, ..., n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables. A line of recent work established that the optimization problem for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable when parameterized by the dimensions of relevant matrices Ai, Ci, Di and by the maximum absolute value of any entry appearing in the constraint matrix. A fundamental tool used in these advances is the notion of the Graver basis of a matrix, and this tool heavily relies on the assumption that all the entries of the constraint matrix are bounded. In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: . The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices Ai, Di and by the maximum absolute value of the entries of matrices Di. That is, we allow matrices Ai to have arbitrarily large entries. . The linear optimization problem for n-fold integer programs that are uniform - all matrices Ci are equal - is fixed-parameter tractable when parameterized by the dimensions of matrices Ci and Di and by the maximum absolute value of the entries of matrices Di. That is, we require that Ci = C for all i = 1, ..., n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. In both results, we depart from the approach that relies purely on Graver bases. Instead, for two-stage stochastic programs, we devise a reduction to integer programming with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce a given n-fold program to an exponential-size program with bounded right-hand sides, which we consequently solve using a reduction to mixed integer programming with a bounded number of integral variables.

Název v anglickém jazyce

Parameterized algorithms for block-structured integer programs with large entries

Popis výsledku anglicky

We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form {Aix + Diyi = bi for all i = 1, ..., n}, where Ai and Di are bounded-size matrices. Intuitively, this form corresponds to the setting when after setting a small set of global variables x, the program can be decomposed into a possibly large number of bounded-size subprograms. On the other hand, n-fold programs are integer programs of the form (Equation presented) Ciyi = a and Diyi = bi for all i = 1, ..., n}, where again Ci and Di are bounded-size matrices. This form is natural for knapsack-like problems, where we have a large number of variables partitioned into small-size groups, each group needs to obey some set of local constraints, and there are only a few global constraints that link together all the variables. A line of recent work established that the optimization problem for both two-stage stochastic programs and n-fold programs is fixed-parameter tractable when parameterized by the dimensions of relevant matrices Ai, Ci, Di and by the maximum absolute value of any entry appearing in the constraint matrix. A fundamental tool used in these advances is the notion of the Graver basis of a matrix, and this tool heavily relies on the assumption that all the entries of the constraint matrix are bounded. In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: In this work, we prove that the parameterized tractability results for two-stage stochastic and n-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove the following: . The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices Ai, Di and by the maximum absolute value of the entries of matrices Di. That is, we allow matrices Ai to have arbitrarily large entries. . The linear optimization problem for n-fold integer programs that are uniform - all matrices Ci are equal - is fixed-parameter tractable when parameterized by the dimensions of matrices Ci and Di and by the maximum absolute value of the entries of matrices Di. That is, we require that Ci = C for all i = 1, ..., n, but we allow C to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is NP-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input. In both results, we depart from the approach that relies purely on Graver bases. Instead, for two-stage stochastic programs, we devise a reduction to integer programming with a bounded number of variables using new insights about the combinatorics of integer cones. For n-fold programs, we reduce a given n-fold program to an exponential-size program with bounded right-hand sides, which we consequently solve using a reduction to mixed integer programming with a bounded number of integral variables.

Druh

D - Stať ve sborníku

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/GA22-22997S" target="_blank" >GA22-22997S: Efektivní a realistické modely ve výpočetní teorii voleb</a><br>

Návaznosti

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

Rok uplatnění

2024

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 statě ve sborníku

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-791-2

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

740-751

Název nakladatele

SIAM

Místo vydání

USA

Místo konání akce

Alexandria, VA, USA

Datum konání akce

7. 1. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—