Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.ESA.2024.32" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2024.32</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2024.32" target="_blank" >10.4230/LIPIcs.ESA.2024.32</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds

Popis výsledku v původním jazyce

We provide several novel algorithms and lower bounds in central settings of mixed-integer (non-)linear optimization, shedding new light on classic results in the field. This includes an improvement on record running time bounds obtained from a slight extension of Lenstra&apos;s 1983 algorithm [Math. Oper. Res.&apos;83] to optimizing under few constraints with small coefficients. This is important for ubiquitous tasks like knapsack-, subset sum- or scheduling problems [Eisenbrand and Weismantel, SODA&apos;18, Jansen and Rohwedder, ITCS&apos;19]. Further, we extend our algorithm to an intermediate linear optimization problem when the matrix has many rows that exhibit 2-stage stochastic structure, which adds to a prominent line of recent results on this and similarly restricted cases [Jansen et al. ICALP&apos;19, Cslovjecsek et al. SODA&apos;21, Brand et al. AAAI&apos;21, Klein, Reuter SODA&apos;22, Cslovjecsek et al. SODA&apos;24]. We also show that the generalization of two fundamental classes of structured constraints from these works (n-fold and 2-stage stochastic programs) to separable-convex mixed-integer optimization are harder than their mixed-integer, linear counterparts. This counters a widespread belief popularized initially by an influential paper of Hochbaum and Shanthikumar, namely that &quot;convex separable optimization is not much harder than linear optimization&quot; [J. ACM&apos;90]. To obtain our algorithms, we employ the mixed Graver basis introduced by Hemmecke [Math. Prog.&apos;03], and our work is the first to give bounds on the norm of its elements. Importantly, we use these bounds differently from how purely-integer Graver bounds are exploited in related approaches, and prove that, surprisingly, this cannot be avoided.

Název v anglickém jazyce

Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds

Popis výsledku anglicky

We provide several novel algorithms and lower bounds in central settings of mixed-integer (non-)linear optimization, shedding new light on classic results in the field. This includes an improvement on record running time bounds obtained from a slight extension of Lenstra&apos;s 1983 algorithm [Math. Oper. Res.&apos;83] to optimizing under few constraints with small coefficients. This is important for ubiquitous tasks like knapsack-, subset sum- or scheduling problems [Eisenbrand and Weismantel, SODA&apos;18, Jansen and Rohwedder, ITCS&apos;19]. Further, we extend our algorithm to an intermediate linear optimization problem when the matrix has many rows that exhibit 2-stage stochastic structure, which adds to a prominent line of recent results on this and similarly restricted cases [Jansen et al. ICALP&apos;19, Cslovjecsek et al. SODA&apos;21, Brand et al. AAAI&apos;21, Klein, Reuter SODA&apos;22, Cslovjecsek et al. SODA&apos;24]. We also show that the generalization of two fundamental classes of structured constraints from these works (n-fold and 2-stage stochastic programs) to separable-convex mixed-integer optimization are harder than their mixed-integer, linear counterparts. This counters a widespread belief popularized initially by an influential paper of Hochbaum and Shanthikumar, namely that &quot;convex separable optimization is not much harder than linear optimization&quot; [J. ACM&apos;90]. To obtain our algorithms, we employ the mixed Graver basis introduced by Hemmecke [Math. Prog.&apos;03], and our work is the first to give bounds on the norm of its elements. Importantly, we use these bounds differently from how purely-integer Graver bounds are exploited in related approaches, and prove that, surprisingly, this cannot be avoided.

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

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-338-6

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

18

Strana od-do

1-18

Název nakladatele

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl, DE

Místo konání akce

London, UK

Datum konání akce

2. 9. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

—