2026-07-25T11:48:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21103 2024-09-23T09:13:16Z ddc:004 open_access

Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds Brand, Cornelius Koutecký, Martin Lassota, Alexandra Ordyniak, Sebastian Mixed-Integer Programming Separable Convex Optimization Parameterized Algorithms Parameterized Complexity 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’s 1983 algorithm [Math. Oper. Res. '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'18, Jansen and Rohwedder, ITCS'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'19, Cslovjecsek et al. SODA'21, Brand et al. AAAI'21, Klein, Reuter SODA'22, Cslovjecsek et al. SODA'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 "convex separable optimization is not much harder than linear optimization" [J. ACM '90]. To obtain our algorithms, we employ the mixed Graver basis introduced by Hemmecke [Math. Prog. '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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cornelius Brand and Martin Koutecký and Alexandra Lassota and Sebastian Ordyniak 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.32 urn:nbn:de:0030-drops-211033 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode