Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16820
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

Felix Ohnesorge, Klaus Jansen, Björn Schumacher
arXiv (Cornell University)
Complexity and Algorithms in Graphs
preprint

Canonical Truncation for Mixed-Integer and Combinatorial n-Fold Optimization

Felix Ohnesorge, Klaus Jansen, Björn Schumacher
preprint en

Abstract

We consider a special block-structured integer program with $n$ blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective $c^{\intercal}x + g(Ax)$, where $c$ is a rational cost vector, $A$ is an integral matrix with $d$ rows, and $g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\}$ is an arbitrary function. We access $g$ via an oracle that minimizes $c^{\intercal}x + g(Ax)$ when all but $O(d)$ variables are fixed. Our algorithm runs in time $(ndΔ)^{O(d)}(Q + \text{poly}(|I|))$ where $Δ$ is the largest absolute value of an entry in $A$, $Q$ is the necessary time to evaluate the oracle for $g$ and $|I|$ is the size of the input. This model is a variation of the model studied by Dadush et al.~[IPCO 23]. Their model has only a single block but individual upper and lower bounds on the variables instead of prescribed block sums. For their model they present an algorithm with running time $t^d(dΔ)^{O(d^2)}Q$ where $t$ is the number of variables. We use our algorithm to solve mixed-integer linear programs with no upper bounds on the variables, a linear objective, and arbitrarily many constraints involving only fractional variables in time $(mΔ)^{O(m)}\text{poly}(|I|)$, where $m$ is the number of constraints involving integral variables and $Δ$ is the largest absolute value of coefficients of integral variables. This improves the dependence on $m$ in the exponent to asymptotically match the dependency in the integer setting. Further, we use our algorithm to generalize the parameterized algorithm for scheduling on uniformly related machines by Rohwedder~[ICALP 25] to obtain an algorithm for multiple knapsack with running time $w_{\max}^{O(d)}\text{poly}(|I|)$ where $w_{\max}$ is the maximum weight of an item and $d$ the number of different weights.

arXiv (Cornell University)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon