Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-22997S" target="_blank" >GA22-22997S: Efficient and Realistic Models in Computational Social Choice</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics, LIPIcs
ISBN
978-3-95977-338-6
ISSN
1868-8969
e-ISSN
—
Number of pages
18
Pages from-to
1-18
Publisher name
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl, DE
Event location
London, UK
Event date
Sep 2, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—