betaFeedback

WorksComputer Science

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

Abstract

We consider a special block-structured integer program with nn blocks. Every block has a prescribed number of vectors that need to be selected while minimizing the objective c⊺x+g(Ax)c^{\intercal}x + g(Ax), where cc is a rational cost vector, AA is an integral matrix with dd rows, and g ⁣:Zd→Q∪{+∞}g \colon \mathbb{Z}^d \to \mathbb{Q}\cup \{+\infty\} is an arbitrary function. We access gg via an oracle that minimizes c⊺x+g(Ax)c^{\intercal}x + g(Ax) when all but O(d)O(d) variables are fixed. Our algorithm runs in time (ndΔ)O(d)(Q+poly(∣I∣))(ndΔ)^{O(d)}(Q + \text{poly}(|I|)) where ΔΔ is the largest absolute value of an entry in AA, QQ is the necessary time to evaluate the oracle for gg and ∣I∣|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 td(dΔ)O(d2)Qt^d(dΔ)^{O(d^2)}Q where tt 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)poly(∣I∣)(mΔ)^{O(m)}\text{poly}(|I|), where mm is the number of constraints involving integral variables and ΔΔ is the largest absolute value of coefficients of integral variables. This improves the dependence on mm 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 wmax⁡O(d)poly(∣I∣)w_{\max}^{O(d)}\text{poly}(|I|) where wmax⁡w_{\max} is the maximum weight of an item and dd the number of different weights.

Funding. Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project number 528381760.

Introduction

We study the following block-structured integer program. Let n,d≥1n,d \ge1 be integers. For each block ii, let b(i)b^{(i)} and t(i)t^{(i)} be positive integers, and set t=∑i=1nt(i)t=\sum_{i=1}^{n}t^{(i)}. For x∈Ztx\in\mathbb{Z}^{t}, let x(i)x^{(i)} denote its block of t(i)t^{(i)} consecutive coordinates, starting at 1+∑h<it(h)1+\sum_{h<i}t^{(h)}. Let A=(A1∣⋯∣An)∈Zd×tA=(A_{1}\mid\cdots\mid A_{n})\in\mathbb{Z}^{d\times t}, c∈Qtc\in\mathbb{Q}^{t}, and g:Zd→Q∪{+∞}g:\mathbb{Z}^{d}\to\mathbb{Q}\cup\{+\infty\}. Set Δ=max⁡{1,∥A∥∞}\Delta=\max\{1,\lVert A\rVert_{\infty}\} where ∥A∥∞\lVert A\rVert_{\infty} is the largest absolute value of an entry in AA. We consider

minimizecTx+g(Ax)such that1Tx(i)=b(i)(i∈[n]),x∈Z≥0t.(1)\begin{aligned} \text{minimize}\quad&c^{\mathsf{T}}x+g(Ax)\\ \text{such that}\quad&\mathbf{1}^{\mathsf{T}}x^{(i)}=b^{(i)}\quad(i\in[n]),\\ &x\in\mathbb{Z}^{t}_{\ge0}. \tag*{(1)} \end{aligned}

We optimize for the combination of cTxc^{\mathsf{T}}x and gg applied to the linking image AxAx while every prescribed block sum, i.e., 1Tx(i)=b(i)\mathbf{1}^{\mathsf{T}}x^{(i)}=b^{(i)}, is satisfied. We are given gg via an oracle with the following low-dimensional optimization assumption. Given a partition K\mathbin{\mathaccent\cdot\cup}J of [t][t], the coordinates with indices in JJ are fixed and determined by the vector z∈Z≥0Jz\in\mathbb{Z}^{J}_{\ge0}. Further, we have ∣K∣≤6d−3|K|\le6d-3. The oracle solves

minimizecKTx+cJTz+g(AKx+AJz)such that1Tx(i)+1Tz(i)=b(i)(i∈[n]),x∈Z≥0K.(2)\begin{aligned} \text{minimize}\quad&c_{K}^{\mathsf{T}}x+c_{J}^{\mathsf{T}}z+g(A_{K}x+A_{J}z)\\ \text{such that}\quad&\mathbf{1}^{\mathsf{T}}x^{(i)}+\mathbf{1}^{\mathsf{T}}z^{(i)}=b^{(i)}\quad(i\in[n]),\\ &x\in\mathbb{Z}^{K}_{\ge0}. \tag*{(2)} \end{aligned}

where cK,cJc_{K},c_{J} and AK,AJA_{K},A_{J} are the restrictions to the columns given by KK and JJ respectively. x(i)x^{(i)} and z(i)z^{(i)} contain the coordinates of KK and JJ, respectively, belonging to the original block ii. The oracle reports infeasibility in case no feasible integer point exists due to the supplied JJ and zz. If the optimum is +∞+\infty, it is returned symbolically. Let Q≥1Q\ge1 be the necessary time to evaluate the oracle (2), return the optimal value, and a corresponding solution.

Theorem 1.1. Under the oracle assumption in (2), the problem (1) can be solved in (ndΔ)O(d)(Q+poly⁡(∣I∣))(nd\Delta)^{O(d)}(Q+\operatorname{poly}(|I|)) time.

An evaluation oracle for an arbitrary gg does not suffice for the claimed bound. When n=d=1n=d=1, A=(0,1)A=(0,1), c=0c=0, and b(1)=bb^{(1)}=b, the problem is min⁡z∈{0,…,b}g(z)\min_{z\in\{0,\ldots,b\}}g(z), which requires Ω(b)\Omega(b) evaluation oracle calls for arbitrary functions.

Our oracle model is an adaptation of the one by Dadush et al. [7]. They optimize cTx+g(Wx)c^{\mathsf{T}}x+g(Wx) with lower and upper bounds for xx, where W∈Zd×tW\in\mathbb{Z}^{d\times t} has entries bounded by Δ\Delta, assuming that optimization is possible when all but dd variables are fixed. Their algorithm has running time td(dΔ)O(d2)Qt^{d}(d\Delta)^{O(d^{2})}Q, where QQ again is the cost of the oracle. The factor tdt^{d} can be absorbed into the parameter dependence in several special cases. Hunkenschröder et al. [11] considered the 0/1 variant with the restriction of gg to special convex functions. Their assumed oracle provides the function value and the gradient at the queried point. They obtain an (mΔ)O(m3)poly⁡(∣I∣)(m\Delta)^{O(m^{3})}\operatorname{poly}(|I|) algorithm even when WW is unknown under certain conditions.

Applications

Mixed-Integer Linear Programming

Let A∈Zm×pA \in\mathbb{Z}^{m \times p}, C∈Qm×qC \in\mathbb{Q}^{m \times q}, b∈Qmb \in\mathbb{Q}^{m}, c∈Qpc \in\mathbb{Q}^{p}, and e∈Qqe \in\mathbb{Q}^{q}, where m,p≥1m,p \ge1. Let P⊂RqP \subset\mathbb{R}^{q} be an explicitly given rational polyhedron, and set Δ=max⁡{1,∥A∥∞}\Delta= \max\{1, \lVert A \rVert_{\infty}\}. We consider the following mixed-integer linear program

minimizecTx+eTysuch thatAx+Cy=bx∈Z≥0p,y∈P(3)\begin{aligned} \text{minimize}\quad& c^{\mathsf{T}}x + e^{\mathsf{T}}y \\ \text{such that}\quad& Ax + Cy = b \\ & x \in\mathbb{Z}_{\ge0}^{p},\quad y \in P \tag*{(3)} \end{aligned}

To solve (3), we apply Theorem 1.1 for a single block together with a calculated block sum while encoding the fractional part of (3) in gg (as done in [7]). We solve the corresponding oracle using the algorithm of Lenstra with Kannan’s improvement [20, 16], which solve MILPs in time pO(p)poly⁡(∣I∣)p^{O(p)}\operatorname{poly}(\lvert I\rvert). This yields the following result.

Theorem 1.2. The MILP (3) can be solved in (mΔ)O(m)poly⁡(∣I∣)(m\Delta)^{O(m)}\operatorname{poly}(\lvert I\rvert) time.

Dadush et al. [7 Corollary 3] already consider a closely related mixed-integer model with upper bounds on the integer variables, arbitrary coefficients on the continuous variables, and additional constraints involving only those variables. Their bound is pm(mΔ)O(m2)poly⁡(∣I∣)p^{m}(m\Delta)^{O(m^{2})}\operatorname{poly}(\lvert I\rvert). Without integer-variable upper bounds or the linear objective, the pmp^{m} factor can be omitted. The running time (mΔ)O(m2)poly⁡(∣I∣)(m\Delta)^{O(m^{2})}\operatorname{poly}(\lvert I\rvert) for the MILP (3) was also achieved in [Roh19]. Thus, our contribution is reducing the dependence on mm in the exponent, which asymptotically matches the best known dependence on mm in the exponent for pure non-negative integer linear programming [8, 15]. Brand et al. [1] give algorithms for separable convex mixed-integer optimization with few rows, with parameter dependence (m∥E∥∞)O(m2)(m\lVert E\rVert_{\infty})^{O(m^{2})} for the full constraint matrix EE, where mm is the number of rows in EE. Compared to (3), extra constraints for the fractional variables outside of EE are not permitted in their model.

Combinatorial nn-fold

Let A=(A1∣⋯∣An)A = (A_{1} \mid\cdots\mid A_{n}), cc, and the positive block totals b(i)b^{(i)} be as in (1), and let u∈Qdu \in\mathbb{Q}^{d}. Let f:Zd→Qf : \mathbb{Z}^{d} \to\mathbb{Q} be a separable discrete convex function, i.e., fh(s+1)−fh(s)f_{h}(s+1)-f_{h}(s) is non-decreasing in ss for every h∈[d]h \in[d]. We consider the combinatorial nn-fold problem

minimizecTx+f(Ax)such thatAx≤u,1Tx(i)=b(i)(i=1,…,n),x∈Z≥0d.(4)\begin{aligned} \text{minimize}\quad& c^{\mathsf{T}}x + f(Ax) \\ \text{such that}\quad& Ax \le u, \\ & \mathbf{1}^{\mathsf{T}}x^{(i)} = b^{(i)} \quad(i = 1,\ldots,n), \\ & x \in\mathbb{Z}_{\ge0}^{d}. \tag*{(4)} \end{aligned}

Knop et al. [18] introduced the combinatorial nn-fold model that specializes nn-fold IPs by restricting the block-local matrices to rows containing only ones. Our addition is the separable convex cost on the linking image AxAx.

Theorem 1.3. The combinatorial nn-fold (4) can be solved in (ndΔ)O(d)poly⁡(∣I∣)(nd\Delta)^{O(d)}\operatorname{poly}(|I|) time, assuming that ff can be evaluated exactly in time poly⁡(∣I∣)\operatorname{poly}(|I|).

For linear objectives and a fixed linking right-hand side, Jansen et al. [14] already obtain (ndΔ)O(d)(nd\Delta)^{O(d)} parameter dependence with logarithmic dependence on the right-hand side. The same asymptotic dependency on nn, dd, and Δ\Delta was also achieved by Rohwedder [23] and Gupta et al. [9] but both algorithms have a linear dependence on the total prescribed block sums. None of the just mentioned algorithms are able to handle non-linear objectives. Notable about this line of research is that the quadratic dependence on the number of linking constraints in the exponent of nn-fold algorithms (e.g. [CEH+21]) is replaced by introducing the number of blocks into the base of the parameter term.

Multiple Knapsack

An instance of Multiple Knapsack consists of item types with positive integer weights wiw_i, nonnegative rational profits pip_i, and integer multiplicities ni≥0n_i \ge0, together with mm knapsacks of integer capacities C1,…,Cm>0C_1,\ldots,C_m > 0. The task is to select and assign items to the knapsacks without exceeding their capacities or the available multiplicities, maximizing the total profit. All numbers, including the multiplicities, are encoded in binary. Let dd be the number of distinct item weights and let wmax⁡=max⁡iwiw_{\max} = \max_i w_i be the largest weight. A running time of wmax⁡O(d2)poly⁡(∣I∣)w_{\max}^{O(d^2)}\operatorname{poly}(|I|) already follows directly from a straightforward nn-fold IP formulation with classic convex costs and standard nn-fold algorithms [17]: the formulation has dd linking constraints for the weight classes, one local capacity constraint per knapsack, and an additional block recording rejected items and their profits.

We remove the quadratic dependence on dd in the exponent by combining our combinatorial nn-fold algorithm with a modular reduction for scheduling on uniformly related machines by Rohwedder [23].

Theorem 1.4. Multiple Knapsack can be solved in time wmax⁡O(d)⋅poly⁡(∣I∣)w_{\max}^{O(d)}\cdot\operatorname{poly}(|I|).

Note that the dependence on wmax⁡w_{\max} cannot be removed: the reduction of Koutecký and Zink [19 Theorem 4.13] for scheduling on uniformly related machines implies that Multiple Knapsack is NP-hard already for d=6d = 6 and unit profits, and hence is not in XP parameterized only by dd unless P = NP. A lower bound follows under the Satisfiability Hypothesis (SH) of Stearns and Hunt [SH90]: for every fixed ε>0\varepsilon> 0, there is no wmax⁡O(d1−ε)⋅poly⁡(∣I∣)w_{\max}^{O(d^{1-\varepsilon})}\cdot\operatorname{poly}(|I|)-time algorithm, even with identical capacities and unit profits. Indeed, the reduction of Chen, Jansen, and Zhang [4] maps a 3SAT instance of size ss to O(s)O(s) jobs with polynomially bounded processing times. Such an algorithm would therefore solve 3SAT in time 2O(s1−εlog⁡s)≤2O(s1−ε/2)2^{O(s^{1-\varepsilon}\log s)} \le2^{O(s^{1-\varepsilon/2})}, contradicting SH.

Other parameterizations and approximation algorithms have also been studied for the classical formulation with explicitly listed items (see e.g., [5, 10, 12, 13]).

Technical Overview

The core idea of our algorithm is the classic paradigm to focus on optimal solutions with special structure. Since the evaluation of gg only depends on the linking image, the concrete assignment of the variables only matters for the linear objective cc. For a fixed linking image, we choose a representative candidate from the set of optimal solutions according to cc. In particular, we choose the lexicographically (lexicographic order denoted by <lex<_{\mathrm{lex}}) smallest solution. We call these solutions canonical. Considering the lexicographically smallest solution is a common approach, see for example [24]. Therefore, our contribution is applying this technique in our proposed setting and its application.

Canonical solutions have inherently small support: the number of non-zero coordinates in every block is bounded by a function in dd and Δ\Delta. Further, the number of blocks with multiple big coordinates (coordinates exceeding a certain threshold) and the total number of big coordinates in these blocks is bounded by O(d)O(d). The proofs for the structural properties rely on the fact that the variables have no individual upper bounds. These structural properties allow us to define truncated canonical solutions, which can be efficiently enumerated while retaining all the necessary information to invoke the oracle. This is in contrast to the approach used in [7], which builds on the proximity for ILPs in [8] and combines it with a guessing procedure to apply the oracle.

Properties of Canonical Solutions

We define

p:Z≥0t→Z≥0t,u↦lexminv∈Z≥0t{cTv:Av=Au,1Tu(i)=1Tv(i)(i∈[n])}.p:\mathbb{Z}_{\geq0}^{t}\to\mathbb{Z}_{\geq0}^{t},\quad u\mapsto\mathop{\mathrm{lexmin}}\limits_{v\in\mathbb{Z}_{\geq0}^{t}}\left\{c^{\mathsf{T}}v:\begin{aligned}Av&=Au,\\ \mathbf{1}^{\mathsf{T}}u^{(i)}&=\mathbf{1}^{\mathsf{T}}v^{(i)}\quad(i\in[n])\end{aligned}\right\}.

The function is well-defined, since uu is contained in the finite candidate set for p(u)p(u). Call xx canonical if it is a fixpoint of pp, i.e., p(x)=xp(x)=x. Replacing an optimal solution x⋆x^\star by its canonical representative p(x⋆)p(x^\star) preserves all constraints and cannot increase its linear cost. Consequently a canonical optimum exists.

First, we show that being canonical is hereditary in the sense that all subvectors of a canonical vector are also canonical. u∈Z≥0tu\in\mathbb{Z}_{\geq0}^{t} is a subvector of x∈Z≥0tx\in\mathbb{Z}_{\geq0}^{t} if ui≤xiu_i\leq x_i for all i∈[t]i\in[t]. We denote this by u≤xu\leq x.

Lemma 2.1. Let x∈Z≥0tx\in\mathbb{Z}_{\geq0}^{t} be canonical. Then every u∈Z≥0tu\in\mathbb{Z}_{\geq0}^{t} with u≤xu\leq x is also canonical.

Proof. Let u∈Z≥0tu\in\mathbb{Z}_{\geq0}^{t} such that u≤xu\leq x. Towards a proof by contradiction, suppose v:=p(u)≠uv:=p(u)\ne u. Set x′=x+v−ux'=x+v-u. Since Av=AuAv=Au and 1Tv(i)=1Tu(i)\mathbf{1}^{\mathsf{T}}v^{(i)}=\mathbf{1}^{\mathsf{T}}u^{(i)} for all i∈[n]i\in[n], we have Ax′=AxAx'=Ax and 1Tx′(i)=1Tx(i)\mathbf{1}^{\mathsf{T}}x'^{(i)}=\mathbf{1}^{\mathsf{T}}x^{(i)} for all i∈[n]i\in[n]. If cTv<cTuc^{\mathsf{T}}v<c^{\mathsf{T}}u we have cTx′<cTxc^{\mathsf{T}}x'<c^{\mathsf{T}}x. Otherwise, if cTv=cTuc^{\mathsf{T}}v=c^{\mathsf{T}}u and v<lexuv<_{\mathrm{lex}}u we have cTx′=cTxc^{\mathsf{T}}x'=c^{\mathsf{T}}x and x′<lexxx'<_{\mathrm{lex}}x. Both cases contradict that xx is a fixpoint of pp, which implies v=uv=u.

A direct implication of this lemma is that all subvectors of a canonical solution have a different linking sum or block sum.

Corollary 2.2. Let x∈Z≥0tx\in\mathbb{Z}_{\geq0}^{t} be canonical. Then, for u,v∈Z≥0tu,v\in\mathbb{Z}_{\geq0}^{t} with u,v≤xu,v\leq x, Au=AvAu=Av and 1Tu(i)=1Tv(i)\mathbf{1}^{\mathsf{T}}u^{(i)}=\mathbf{1}^{\mathsf{T}}v^{(i)} for all i∈[n]i\in[n] implies u=vu=v.

Proof. Let u,v∈Z≥0u,v \in\mathbb{Z}_{\geq0} with u,v≤xu,v \leq x, Au=AvAu=Av and 1Tu(i)=1Tv(i)\mathbf{1}^{\mathsf{T}}u^{(i)}=\mathbf{1}^{\mathsf{T}}v^{(i)} for all i∈[n]i \in[n]. Thus, the candidate set for p(v)p(v) and p(u)p(u) is the same and since p(u)=up(u)=u and p(v)=vp(v)=v, we have u=vu=v.

This fact is important for the structural properties we show next since it enables counting arguments. We start by showing that a canonical solution inherently has small support in every block. The support of a vector x∈Rtx \in\mathbb{R}^{t} is defined as supp⁡(x):={i∈[t]:xi≠0}\operatorname{supp}(x):=\{i \in[t]:x_i \ne0\}.

Lemma 2.3. Let x∈Z≥0tx \in\mathbb{Z}_{\geq0}^{t} be canonical. Then

∣supp⁡(x(i))∣<S:=8(d+1)2Δfor all i∈[n].\left|\operatorname{supp}\left(x^{(i)}\right)\right| < S := 8(d+1)^2\Delta\qquad\text{for all } i \in[n].

Proof. Towards a proof by contradiction, suppose that there is an i∈[n]i \in[n] such that ∣supp⁡(x(i))∣≥S:=8(d+1)2Δ\left|\operatorname{supp}\left(x^{(i)}\right)\right| \geq S := 8(d+1)^2\Delta. Set B:={u∈{0,1}t:u≤x,∥u∥1≤S,u(h)=0 for h≠i}B:=\{u \in\{0,1\}^{t}:u \leq x,\lVert u\rVert_1 \leq S,u^{(h)}=0\text{ for }h \ne i\} with ∣B∣≥2S|B| \geq2^S. For every u∈Bu \in B we have ∥Au∥∞≤SΔ\lVert Au\rVert_{\infty} \leq S\Delta and ∥u∥1≤S\lVert u\rVert_1 \leq S. Hence, the number of possible images (Au,∥u∥1)(Au,\lVert u\rVert_1) is bounded by (2SΔ+1)d+1(2S\Delta+1)^{d+1}. Since 2m>m+12^m>m+1 for every integer m≥2m \geq2, we have

∣B∣≥2S=(24(d+1)Δ)2(d+1)>(4(d+1)Δ+1)2(d+1)≥(2SΔ+1)d+1,|B| \geq2^S = \left(2^{4(d+1)\Delta}\right)^{2(d+1)} > \left(4(d+1)\Delta+1\right)^{2(d+1)} \geq(2S\Delta+1)^{d+1},

where the last inequality uses (4(d+1)Δ+1)2≥16(d+1)2Δ2+1=2SΔ+1\left(4(d+1)\Delta+1\right)^2 \geq16(d+1)^2\Delta^2+1=2S\Delta+1. Thus two different vectors in BB have the same linking image and all block sums, which contradicts Corollary 2.2.

We call the coordinate rr in a solution xx big if xr≥q:=4dΔx_r \geq q:=4d\Delta and small otherwise. The set of big coordinates for block ii is denoted by

B(i)(x)={j:xj(i)≥q}.B^{(i)}(x)=\{j:x_j^{(i)}\geq q\}.

If a block has only a single big coordinate its value is fully determined by the assignment of the small variables in the block and b(i)b^{(i)}. Under the assumption that we know the values of all small coordinates, these can be determined in the algorithm without invoking the oracle. Thus, we are only interested in the total number of big coordinates in blocks with at least two big coordinates. This number is in O(d)O(d) as shown by the following lemma.

Lemma 2.4. Let x∈Z≥0tx \in\mathbb{Z}_{\geq0}^{t} be canonical. Then

∑i∈[n]∣B(i)(x)∣≥2∣B(i)(x)∣≤6d−3.\sum_{\substack{i \in[n]\\ |B^{(i)}(x)|\geq2}} |B^{(i)}(x)| \leq6d-3.

Proof. Suppose there are 2d2d disjoint pairs (pi,hi)(p_i,h_i) of big coordinates in xx, with each pair contained in a single block. We build (q+1)2d(q+1)^{2d} different subvectors of xx. Given a vector y∈{0,…,q}2dy \in\{0,\ldots,q\}^{2d} set upi:=yiu_{p_i}:=y_i and uhi:=q−yiu_{h_i}:=q-y_i for all i∈[2d]i \in[2d]. Set all other coordinates to zero and call this vector uyu_y. All these vectors are subvectors of xx and hence canonical. Further, all constructed vectors share the same block sums and ∥Auy∥∞≤2dqΔ\lVert Au_y\rVert_{\infty}\leq2dq\Delta. Thus there are at most (4dqΔ+1)d(4dq\Delta+ 1)^d different linking images but (4dqΔ+1)d=(q2+1)d<(q+1)2d(4dq\Delta+ 1)^d = (q^2 + 1)^d < (q + 1)^{2d} which contradicts Corollary 2.2.

The maximum number of distinct disjoint pairs in block ii is ⌊∣B(i)(x)∣2⌋\left\lfloor\frac{|B^{(i)}(x)|}{2} \right\rfloor. It follows that

∑i∈[n]∣B(i)(x)∣≥2⌊∣B(i)(x)∣2⌋≤2d−1.\sum_{\substack{i\in[n]\\ |B^{(i)}(x)|\ge2}} \left\lfloor\frac{|B^{(i)}(x)|}{2} \right\rfloor\le2d-1.

Since k≤3⌊k2⌋k \le3\left\lfloor\frac{k}{2} \right\rfloor for k≥2k \ge2, we obtain the claimed bound.

Next, we truncate all big coordinates in canonical vectors such that we still retain the information which coordinates are big and are able to enumerate all truncated vectors efficiently.

Lemma 2.5. Let x∈Z≥0tx \in\mathbb{Z}_{\ge0}^t be canonical with ∥x(i)∥1=b(i)\lVert x^{(i)}\rVert_1 = b^{(i)} for i∈[n]i \in[n]. Then there exists a truncation u∈Z≥0tu \in\mathbb{Z}_{\ge0}^t of xx such that

  1. u≤xu \le x, hence, by heredity uu is canonical,

  2. 1Tu(i)=bˉ(i):=min⁡{b(i),qS}\mathbf{1}^{\mathsf{T}}u^{(i)} = \bar{b}^{(i)} := \min\{b^{(i)}, qS\},

  3. ∥Au∥∞≤nqSΔ\lVert Au\rVert_\infty\le nqS\Delta, and

  4. xj>uj⟹uj≥qx_j > u_j \Longrightarrow u_j \ge q for all j∈[t]j \in[t].

Proof. We construct uu from xx. Start with u≤xu \le x where the entries are given by uj=min⁡{xj,q}u_j = \min\{x_j,q\}. Its sum in block ii is less than qSqS by Lemmas 2.1 and 2.3, and at most b(i)b^{(i)}. Increase its coordinates integrally, never exceeding xx, until 1Tu(i)=bˉ(i)\mathbf{1}^{\mathsf{T}}u^{(i)} = \bar{b}^{(i)} in every block. This is possible since bˉ(i)≤b(i)\bar{b}^{(i)} \le b^{(i)}. The resulting vector satisfies all claimed properties.

Algorithm

The algorithm works by first enumerating all truncated candidates as defined by Lemma 2.5. Then for every candidate we fix all fully determined variables and solve the remaining problem with the oracle given in (2).

We start by eliminating duplicate columns in every block. Within each block, merge variables whose columns in AiA_i agree, retaining one of minimum linear cost. Since we only have prescribed block sums and no individual lower/upper bounds for variables, this transformation preserves all the necessary structure. After this step, the number of variables is bounded by n(2Δ+1)dn(2\Delta+ 1)^d. In the following we use the same notation for the reduced instance.

Define the set of truncated candidates with the bounds given in Lemma 2.5

T:={u∈Z≥0t:p(u)=u, ∥Au∥∞≤nqSΔ, 1Tu(i)=bˉ(i) (i∈[n])}.\mathcal{T} := \left\{u \in\mathbb{Z}_{\ge0}^t : p(u) = u,\ \lVert Au\rVert_\infty\le nqS\Delta,\ \mathbf{1}^{\mathsf{T}}u^{(i)} = \bar{b}^{(i)}\ (i \in[n])\right\}.

This set can be enumerated efficiently using straightforward dynamic programming.

Lemma 3.1. T\mathcal{T} can be enumerated in (2ndΔ)O(d)poly⁡(∣I∣)(2nd\Delta)^{O(d)}\operatorname{poly}(|I|) time.

Proof. We use a dynamic program processing blocks in order and inserting bˉ(i)\bar{b}^{(i)} units into block ii, one at a time. At layer (i,h)(i,h), for 0≤h≤bˉ(i)0 \le h \le\bar{b}^{(i)}, let Pi,h(ρ)P_{i,h}(\rho) store the minimum-cost, lexicographically smallest vector with linking image ρ\rho, block sums bˉ(ℓ)\bar{b}^{(\ell)} for ℓ<i\ell< i, sum hh in block ii, and zero in later blocks. Start with the zero vector at image zero. The initial layer of each block is the preceding block’s final layer, and for h≥1h \ge1 the recurrence is

Pi,h(ρ)=lexmin⁡arg⁡min⁡u∈Z≥0t{cTu:u=Pi,h−1(ρ−Aij)+eij, 1≤j≤t(i)}.P_{i,h}(\rho) = \operatorname{lexmin}\mathop{\arg\min}_{u \in\mathbb{Z}_{\geq0}^{t}} \{c^{\mathsf{T}}u : u = P_{i,h-1}(\rho- A_{ij}) + e_{ij},\ 1 \le j \le t^{(i)}\}.

where AijA_{ij} is the jjth column of AA in block ii and eije_{ij} is the unit vector corresponding to the jjth variable in block ii. Removing a positive coordinate from any candidate gives a predecessor. Replacing this predecessor by the stored minimum-cost, lexicographically smallest representative cannot worsen the resulting vector. Induction therefore proves the recurrence.

The preprocessing can be done in time poly⁡(∣I∣)\operatorname{poly}(|I|). For all states ρ\rho, we have ∥ρ∥∞≤nqSΔ\|\rho\|_{\infty} \le nqS\Delta since ∥Pi,h(ρ)∥1≤nqS\|P_{i,h}(\rho)\|_{1} \le nqS. Every state has at most (2Δ+1)d(2\Delta+ 1)^d potential predecessors and thus a state can be calculated in O((d+t)⋅(2Δ+1)d)O((d+t)\cdot(2\Delta+1)^d). Since T\mathcal{T} is the last layer of the dynamic program, it can be enumerated in time

nqS⋅(2nqSΔ+1)d⋅O((d+t)⋅(2Δ+1)d)⋅poly⁡(∣I∣)≤(2ndΔ)O(d)poly⁡(∣I∣).nqS\cdot(2nqS\Delta+1)^d\cdot O((d+t)\cdot(2\Delta+1)^d)\cdot\operatorname{poly}(|I|)\leq(2nd\Delta)^{O(d)}\operatorname{poly}(|I|).

Theorem 1.1. Under the oracle assumption in (2), the problem (1) can be solved in (ndΔ)O(d)(Q+poly⁡(∣I∣))(nd\Delta)^{O(d)}(Q+\operatorname{poly}(|I|)) time.

Proof. If ndΔ=1nd\Delta= 1, then n=d=Δ=1n=d=\Delta=1, and every column of AA belongs to {−1,0,1}\{-1,0,1\}. Retain a minimum-cost variable for each column value and fix all other variables to zero. This preserves an optimum and leaves at most 3=6d−33=6d-3 free variables, so a single oracle call solves the problem in Q+poly⁡(∣I∣)Q+\operatorname{poly}(|I|) time. Henceforth assume ndΔ≥2nd\Delta\ge2.

The remaining part of the algorithm is to apply the oracle. For each truncated candidate u∈Tu \in\mathcal{T}, we define a set J⊆[t]J \subseteq[t] and vector z∈Z≥0tz \in\mathbb{Z}_{\geq0}^{t} to supply to the oracle. JJ is the set of all indices corresponding to small coordinates in uu, i.e., ui<qu_i < q, and all indices of big coordinates that are the only big coordinate in their block. For all indices ii corresponding to small coordinates, we set zi=uiz_i=u_i. Let jj be the index of the single big coordinate in block ii. We set zj=bˉ(i)−(∥u(i)∥1−uj)z_j=\bar{b}^{(i)}-(\|u^{(i)}\|_1-u_j). Finally set K:=[t]∖JK:=[t]\setminus J. We have ∣K∣≤6d−3|K|\leq6d-3 by Lemma 2.4. We call the oracle (2) with (K,J)(K,J) and z∈Z≥0tz\in\mathbb{Z}_{\geq0}^{t}. Discard the result if the oracle reports infeasibility. Return the best solution over all candidates, which may be +∞+\infty when all feasible oracle calls return this value.

Let x⋆x^\star be an optimal canonical solution. By Lemma 2.5 and the definition of T\mathcal{T} the truncated version xˉ\bar{x} of x⋆x^\star will be considered by the algorithm. Let J⊆[t]J\subseteq[t] and zz be the set and vector constructed in the iteration of xˉ\bar{x}. We have zi=xi⋆z_i=x_i^\star for all i∈Ji\in J by property 4 of Lemma 2.5 and the fact that the value for a unique big coordinate in a block is fully determined by the values of the small variables. Thus, the oracle in this iteration finds a solution at least as good as x⋆x^\star.

The preprocessing and enumerating the set T\mathcal{T} takes time (2ndΔ)O(d)poly⁡(∣I∣)(2nd\Delta)^{O(d)}\operatorname{poly}(|I|) by Lemma 3.1. The number of oracle calls is bounded by (2ndΔ)O(d)(2nd\Delta)^{O(d)}. Since 2ndΔ≤(ndΔ)22nd\Delta\leq(nd\Delta)^2 when ndΔ≥2nd\Delta\geq2, we obtain the claimed running time.

Applications

MILP

Theorem 1.2. The MILP (3) can be solved in (mΔ)O(m)poly⁡(∣I∣)(m\Delta)^{O(m)}\operatorname{poly}(|I|) time.

Proof. We start by solving the LP relaxation of (3). If the LP relaxation is infeasible, then so is the MILP, and we are done. Since all data are rational, if the LP relaxation has an optimal solution, the MILP is either infeasible or has an optimal solution; if the LP relaxation is unbounded below, the MILP is either infeasible or also unbounded below [21].

Suppose first that the LP relaxation has an optimal solution. For fixed xx, the constraints on yy depend on xx only through ρ=Ax\rho=Ax. To express the MILP in the form required by Theorem 1.1, define, for ρ∈Zm\rho\in\mathbb{Z}^m,

g(ρ)={min⁡{eTy:Cy=b−ρ, y∈P},if the feasible set is nonempty,+∞,otherwise.g(\rho)= \begin{cases} \min\{e^\mathsf{T}y: Cy=b-\rho,\ y\in P\}, & \text{if the feasible set is nonempty},\\ +\infty, & \text{otherwise}. \end{cases}

All nonempty LPs defining gg have the same recession directions, namely those of PP that lie in ker⁡C\ker C. An improving direction would also make the original LP relaxation unbounded below, so every nonempty LP defining gg has a finite, attained rational minimum. The MILP therefore reduces to minimizing cTx+g(Ax)c^\mathsf{T}x+g(Ax) over x∈Z≥0px\in\mathbb{Z}_{\geq0}^p, where g(Ax)=+∞g(Ax)=+\infty excludes choices of xx that admit no feasible yy.

To apply Theorem 1.1 with one block and d=md=m, we also need a prescribed sum of the integer coordinates. We will obtain this by bounding 1Tx\mathbf{1}^\mathsf{T}x and adding a slack variable. The bound must preserve an optimal solution whenever one exists and have polynomial binary encoding length. Let (xˉ,yˉ)(\bar{x},\bar{y}) be the optimal LP solution computed above, chosen with polynomial encoding length. Let BB be the integer constraint matrix obtained by writing the full constraint system as inequalities and clearing denominators row by row, and set N=p+qN=p+q and H=max⁡{1,∥B∥∞}H=\max\{1,\lVert B\rVert_\infty\}. Its square subdeterminants have absolute value at most N!HNN!H^N. Thus, by the mixed-integer proximity bound in [3 Remark 1], converting from the infinity norm to the 1-norm, whenever the MILP is feasible it has an optimal solution (x∗,y∗)(x^*,y^*) with ∥(xˉ,yˉ)−(x∗,y∗)∥1≤U:=N2N!HN\lVert(\bar{x},\bar{y})-(x^*,y^*)\rVert_1\leq U:=N^2N!H^N.

The positive integer UU is computable in polynomial time and has polynomial encoding length. Set b(1):=⌈∥xˉ∥1⌉+Ub^{(1)}:=\lceil\lVert\bar{x}\rVert_1\rceil+U. Then b(1)b^{(1)} has polynomial encoding length and 1Tx∗≤b(1)\mathbf{1}^\mathsf{T}x^*\leq b^{(1)}. Denominator clearing is used only to derive this bound; the reduction retains the original linking matrix AA.

Introduce s∈Z≥0s\in\mathbb{Z}_{\geq0} with zero cost and a zero linking column, so that 1Tx+s=b(1)\mathbf{1}^\mathsf{T}x+s=b^{(1)}. Write A~=(A∣0)\widetilde{A}=(A\mid0), c~=(c,0)\widetilde{c}=(c,0), and w=(x,s)w=(x,s). We obtain

min⁡{c~Tw+g(A~w):1Tw=b(1),w∈Z≥0p+1}.\min\{\widetilde{c}^\mathsf{T}w+g(\widetilde{A}w):\mathbf{1}^\mathsf{T}w=b^{(1)},\quad w\in\mathbb{Z}_{\geq0}^{p+1}\}.

This has one block, mm linking rows, and coefficient bound Δ\Delta. It has a finite optimum exactly when the MILP (3) is feasible, and then preserves its optimal value.

It remains to implement the oracle in (2) for this choice of gg. For a given partition K∪˙J=[p+1]K\mathbin{\dot\cup}J=[p+1] with ∣K∣≤6m−3|K|\leq6m-3 and z∈Z≥0Jz\in\mathbb{Z}_{\geq0}^J, first check whether the block-sum constraint admits a nonnegative integer completion, reporting infeasibility otherwise. Substituting the definition of gg then gives the MILP

minimizec~KTw+eTysuch thatA~Kw+A~Jz+Cy=b,1Tw+1Tz=b(1),w∈Z≥0K,y∈P.\begin{aligned} \text{minimize}\quad& \widetilde{c}_{K}^{\mathsf{T}}w+e^{\mathsf{T}}y\\ \text{such that}\quad& \widetilde{A}_{K}w+\widetilde{A}_{J}z+Cy=b,\\ & \mathbf{1}^{\mathsf{T}}w+\mathbf{1}^{\mathsf{T}}z=b^{(1)},\\ & w\in\mathbb{Z}_{\geq0}^{K},\quad y\in P. \end{aligned}

If this MILP is infeasible, the oracle returns +∞+\infty together with any nonnegative integer completion of the block sum. Otherwise, it returns an optimal integer vector and the corresponding objective value. In all calls generated by the algorithm, the fixed coordinates are at most b(1)b^{(1)}, so the oracle inputs have polynomial encoding length. Since this MILP has only O(m)O(m) integer variables, it can be solved in time Q=mO(m)poly⁡(∣I∣)Q=m^{O(m)}\operatorname{poly}(|I|) [20, 16]; the continuous dimension affects only the polynomial factor. Applying Theorem 1.1 now gives

(mΔ)O(m)(Q+poly⁡(∣I∣))=(mΔ)O(m)poly⁡(∣I∣).(m\Delta)^{O(m)}\bigl(Q+\operatorname{poly}(|I|)\bigr)=(m\Delta)^{O(m)}\operatorname{poly}(|I|).

If the returned optimum is +∞+\infty, the original MILP is infeasible. Otherwise, discard the slack coordinate and solve the LP defining g(Ax)g(Ax) for the returned xx to recover an optimal continuous vector yy.

Finally, if the original LP relaxation is unbounded below, apply the preceding procedure with both objective vectors set to 00, starting with an LP solution for this zero objective. This decides mixed-integer feasibility within the same running time: if no feasible point exists, report infeasibility; otherwise, the original MILP is unbounded below. □

Combinatorial n-fold

The block-sum constraints restrict the possible solutions, which implies ∥Ax∥∞≤M\lVert Ax\rVert_{\infty}\leq M where M=Δ∑i=1nb(i)M=\Delta\sum_{i=1}^{n}b^{(i)} for all x∈Z≥0tx\in\mathbb{Z}_{\geq0}^{t} that adheres to the prescribed block sums.

Theorem 1.3. The combinatorial n-fold (4) can be solved in (ndΔ)O(d)poly⁡(∣I∣)(nd\Delta)^{O(d)}\operatorname{poly}(|I|) time, assuming that ff can be evaluated exactly in time poly⁡(∣I∣)\operatorname{poly}(|I|).

Proof. To express the combinatorial n-fold (4) in the form required by Theorem 1.1, define, for ρ∈Zd\rho\in\mathbb{Z}^{d},

g(ρ)={f(ρ),ρ≤u,+∞,otherwise.g(\rho)= \begin{cases} f(\rho), & \rho\leq u,\\ +\infty, & \text{otherwise}. \end{cases}

Then Equation (4) is precisely Equation (1) with this choice of gg. The block totals are already prescribed, so it remains to implement the oracle in Equation (2).

For a given partition K⊔J=[t]K\sqcup J=[t] with ∣K∣≤6d−3|K|\leq6d-3 and z∈Z≥0Jz\in\mathbb{Z}_{\geq0}^{J}, first check whether the block-sum constraints admit a nonnegative integer completion, reporting infeasibility otherwise. If they do, retain one such completion. The finite-valued part of the oracle is

minimizecKTx+f(AKx+AJz)subject toAKx+AJz≤u,1Tx(i)+1Tz(i)=b(i)(i∈[n]),x∈Z≥0K.(5)\begin{aligned} \text{minimize}\quad& c_K^{\mathsf T}x + f(A_Kx + A_Jz)\\ \text{subject to}\quad& A_Kx + A_Jz \le u,\\ & \mathbf{1}^{\mathsf T}x^{(i)} + \mathbf{1}^{\mathsf T}z^{(i)} = b^{(i)} \quad(i \in[n]),\\ & x \in\mathbb{Z}_{\ge0}^{K}. \tag*{(5)} \end{aligned}

Introducing dd integer variables for the linking image gives the equivalent separable convex integer program

minimizecKTx+f(v)subject tov=AKx+AJz≤u,1Tx(i)+1Tz(i)=b(i)(i∈[n]),x∈Z≥0K,v∈Zd.(6)\begin{aligned} \text{minimize}\quad& c_K^{\mathsf T}x + f(v)\\ \text{subject to}\quad& v = A_Kx + A_Jz \le u,\\ & \mathbf{1}^{\mathsf T}x^{(i)} + \mathbf{1}^{\mathsf T}z^{(i)} = b^{(i)} \quad(i \in[n]),\\ & x \in\mathbb{Z}_{\ge0}^{K},\quad v \in\mathbb{Z}^{d}. \tag*{(6)} \end{aligned}

We solve (6) using Theorem 7.1.2 in [6]. Put N=∣K∣+d≤7d−3N = |K| + d \le7d - 3. The block sums imply 0≤xj≤b(i)0 \le x_j \le b^{(i)} for every free variable in block ii, and −M≤vh≤M-M \le v_h \le M for every h∈[d]h \in[d]. These coordinate bounds have polynomial encoding length in ∣I∣|I|.

Let f~\widetilde{f} be the sum of the linear interpolations of the fhf_h on [−M,M][-M,M]; it is convex and agrees with ff at integer points. For τ∈Q\tau\in\mathbb{Q}, let CτC_\tau be the real relaxation of (6), with the coordinate bounds above and cKTx+f~(v)≤τc_K^{\mathsf T}x + \widetilde{f}(v) \le\tau. To strongly separate a query (xˉ,vˉ)∈QN(\bar{x},\bar{v}) \in\mathbb{Q}^{N}, first check the explicit linear constraints and return any violated constraint, orienting equalities appropriately. Otherwise, set

kh=min⁡{⌊vˉh⌋,M−1},sh=f(k+eh)−f(k),k_h = \min\{\lfloor\bar{v}_h\rfloor, M-1\}, \qquad s_h = f(k+e_h)-f(k),

for h∈[d]h \in[d], where ehe_h is the hh-th unit vector. Separability and discrete convexity imply f~(v)≥f(k)+sT(v−k)\widetilde{f}(v) \ge f(k) + s^{\mathsf T}(v-k) throughout the box, with equality at vˉ\bar{v}. If cKTxˉ+f~(vˉ)≤τc_K^{\mathsf T}\bar{x} + \widetilde{f}(\bar{v}) \le\tau, report membership in CτC_\tau. Otherwise, return the valid separating inequality

cKTx+sTv≤τ−f(k)+sTkc_K^{\mathsf T}x + s^{\mathsf T}v \le\tau- f(k) + s^{\mathsf T}k

which is strictly violated at the query point; a zero normal certifies Cτ=∅C_\tau= \varnothing. This oracle uses d+1d+1 evaluations of ff at integer points in [−M,M]d[-M,M]^d and polynomial-time rational arithmetic, with separating inequalities of polynomial encoding length in ∣I∣|I| and the encoding length of τ\tau. Also, CτC_\tau lies in the Euclidean ball of radius NMNM centered at the origin.

Dadush’s deterministic integer-feasibility algorithm [6 Theorem 7.1.2] therefore solves each objective-threshold query in (N+1)O(N)poly⁡(∣I∣)(N+1)^{O(N)}\operatorname{poly}(|I|) time. Since exact polynomial-time evaluation implies polynomial encoding length for all feasible integer objective values, binary search requires only polynomially many such queries to obtain an exact minimizer. Thus (6) can be solved deterministically in

Q=(N+1)O(N)poly⁡(∣I∣)=dO(d)poly⁡(∣I∣).Q = (N+1)^{O(N)}\operatorname{poly}(|I|) = d^{O(d)}\operatorname{poly}(|I|).

If this program is infeasible, the oracle returns +∞+\infty together with the retained block-sum completion; otherwise, it returns an optimal xx and its objective value. The returned vector and any finite objective value have polynomial encoding length. Applying Theorem 1.1 now gives

(ndΔ)O(d)(Q+poly⁡(∣I∣))=(ndΔ)O(d)poly⁡(∣I∣).(nd\Delta)^{O(d)}(Q+\operatorname{poly}(|I|))=(nd\Delta)^{O(d)}\operatorname{poly}(|I|).

If the returned optimum is +∞+\infty, the original problem is infeasible. Otherwise, the algorithm returns an optimal xx.

Multiple Knapsack

Theorem 1.4. Multiple Knapsack can be solved in time wmax⁡O(d)⋅poly⁡(∣I∣)w_{\max}^{O(d)}\cdot\operatorname{poly}(|I|).

Proof sketch. Adding zero-profit items of weight one allows every knapsack to be filled exactly and introduces at most one additional weight class. Since the total available profit is fixed, we minimize rejection cost. For each weight class ii, let Fi(z)F_i(z) be the cost of rejecting its zz cheapest items. Its marginal costs are nondecreasing, so FiF_i is discrete convex.

We apply Rohwedder’s modular construction [23]. Knapsacks of capacity at least H=dwmax⁡3H=dw_{\max}^{3} are big; the others are small. We guess a pivot class aa and reserve ∣B∣wmax⁡2|B|w_{\max}^{2} pivot items in total, where BB is the set of big knapsacks. Small knapsacks are represented by full configurations. For big knapsacks, removing pivot items and bundles of waw_a equal-weight nonpivot items leaves bounded residual configurations preserving the load modulo waw_a. A suitable pivot exists by the pigeonhole principle, and its reserve guarantees that the bundles can be distributed before inserting the pivot items.

Grouping small knapsacks by capacity and big knapsacks by residue modulo waw_a gives a combinatorial nn-fold structure with O(H+wa)O(H+w_a) configuration blocks and one bundle block. Applying Theorem 1.3 to each pivot gives a running time of wmax⁡O(d)poly⁡(∣I∣)w_{\max}^{O(d)}\operatorname{poly}(|I|). Appendix § 6 gives the full formulation, correctness proof, and reconstruction.

Generative AI Disclosure

ChatGPT Astra suggested algorithms for MILPs and the presented combinatorial nn-fold extension using the lexicographical minimal solutions. The authors combined them to the model presented in this paper. ChatGPT Astra was also used to polish the text in the paper. The authors take full responsibility for the content of the document.

Full Proof for Multiple Knapsack

Since the total profit ∑j=1mpjnj\sum_{j=1}^{m} p_j n_j of all available items is fixed, maximizing the profit of selected items is equivalent to minimizing the total profit of the items not selected. We regard the profit of an unselected item as its rejection cost. Items of the same weight can then be grouped: if a prescribed number of them is to be rejected, it is optimal to reject the cheapest ones. This gives a separable convex rejection cost. We combine this observation with the modular pivot construction of Rohwedder [23] and Theorem 1.3.

Put T=∑j=1mCjT = \sum_{j=1}^{m} C_j. We assume wmax⁡≥2w_{\max} \ge2, since otherwise selecting the most profitable items is optimal. Add TT dummy items of weight one and profit zero. Every packing can now be filled to capacity without changing its profit, and discarding dummy items recovers a packing of the original instance. Group the augmented items by weight, merging the dummies with any real items of weight one. Adding the dummies introduces at most one new weight class, which is absorbed in the wmax⁡O(d)w_{\max}^{O(d)} running-time bound. Thus, without loss of generality, we continue to write dd for the number of weight classes after augmentation. Index these classes by their distinct weights w1,…,wdw_1,\ldots,w_d, with multiplicities N1,…,NdN_1,\ldots,N_d. In particular, d≤wmax⁡d \le w_{\max}. For i∈[d]i \in[d] and z∈{0,…,Ni}z \in\{0,\ldots,N_i\}, let Fi(z)F_i(z) be the total rejection cost of the zz cheapest items of weight wiw_i. The differences Fi(z+1)−Fi(z)F_i(z+1)-F_i(z) are nondecreasing, so FiF_i is discrete convex. Sorting the profit classes within each weight class gives a piecewise-linear interpolation with one segment per distinct profit. Its breakpoints are prefix sums of binary multiplicities. Thus the functions have polynomial encoding length and can be evaluated exactly in polynomial time. Extend them beyond their domains using their first and last segment slopes; these extensions remain convex.

To formulate the packing constraints, use Rohwedder’s modular construction [23] and set

H=dwmax⁡3,B={j:Cj≥H},R=∣B∣wmax⁡2.H = d w_{\max}^{3}, \qquad B = \{j : C_j \ge H\}, \qquad R = |B|w_{\max}^{2}.

Call the knapsacks in BB big and all others small. For each candidate pivot class a∈[d]a \in[d] satisfying Na≥RN_a \ge R, solve the formulation below. We take the best solution over all candidates. The formulation will reserve RR items of this class for the big knapsacks. If B=∅B = \varnothing, then R=0R = 0.

For a fixed pivot aa, group small knapsacks by their exact capacity and big knapsacks by their capacity modulo waw_a. Let T\mathcal{T} be the set of nonempty classes and mτm_\tau the number of knapsacks in class τ∈T\tau\in\mathcal{T}. There are at most H+waH+w_a classes. A small class of capacity t<Ht < H has configurations

Cτ={c∈Z≥0d:wTc=t}.\mathcal{C}_\tau= \{c \in\mathbb{Z}_{\ge0}^{d} : \mathbf{w}^{\mathsf{T}}c = t\}.

For a big class of residue ρ\rho, use the residual configurations

Cτ={c∈Z≥0d:ca=0,ci<wa for i≠a,wTc≡ρ(modwa)}.\mathcal{C}_\tau= \left\{c \in\mathbb{Z}_{\ge0}^{d} : c_a = 0,\quad c_i < w_a\text{ for }i \ne a,\quad\mathbf{w}^{\mathsf{T}}c \equiv\rho\pmod{w_a}\right\}.

A bundle of a nonpivot class contains waw_a items, whereas a pivot bundle contains one item. Write γi=wa\gamma_i = w_a for i≠ai \ne a and γa=1\gamma_a = 1.

Let xτ,cx_{\tau,c} count knapsacks using configuration cc, and let bib_i count bundles of class ii, excluding the reserved pivot items. The selected count outside the reserve is

Yi=∑τ∈T∑c∈Cτcixτ,c+γibi.Y_i = \sum_{\tau\in\mathcal{T}}\sum_{c \in\mathcal{C}_\tau} c_i x_{\tau,c} + \gamma_i b_i.

Consequently, the number of rejected items for a given class ii is

Ni−(Yi+R1i=a)={Ni−Yi−R,i=a,Ni−Yi,i≠a.N_i - (Y_i + R 1_{i=a}) = \begin{cases} N_i - Y_i - R, & i = a,\\ N_i - Y_i, & i \ne a. \end{cases}

We obtain the minimization problem

min⁡∑i=1dFi(Ni−Yi−R1i=a)subject to∑c∈Cτxτ,c=mτ(τ∈T),Yi≤Ni−R1i=a(i∈[d]),∑i=1dwiYi≤T−waR,∑i=1dbi+h=T,xτ,c,bi,h∈Z≥0.(7)\begin{aligned} \min\quad& \sum_{i=1}^{d} F_i(N_i - Y_i - R 1_{i=a})\\ \text{subject to}\quad& \sum_{c\in C_\tau} x_{\tau,c} = m_\tau&& (\tau\in\mathcal{T}),\\ & Y_i \le N_i - R 1_{i=a} && (i \in[d]),\\ & \sum_{i=1}^{d} w_iY_i \le T - w_aR,\\ & \sum_{i=1}^{d} b_i + h = T,\\ & x_{\tau,c}, b_i, h \in\mathbb{Z}_{\ge0}. \tag*{(7)} \end{aligned}

The last equality creates one additional block containing the bundle variables and a slack variable hh. It does not restrict the other variables: every bundle has weight at least one, so the total-weight inequality already implies ∑ibi≤T\sum_i b_i \le T. The reserve is accounted for both in the selected weight and in the rejection costs.

The correctness of this formulation follows essentially the same argument as Rohwedder [23 Sections 2 and 4].

Lemma A.1. For every κ∈Q≥0\kappa\in\mathbb{Q}_{\ge0}, the following are equivalent:

  1. The original instance admits a packing with rejection cost at most κ\kappa.

  1. For some pivot class a∈[d]a \in[d] satisfying Na≥RN_a \ge R, Equation (7) admits a feasible solution with objective value at most κ\kappa.

Moreover, any feasible solution of Equation (7) can be converted into a packing with the same rejection cost in time polynomial in its encoding length and ∣I∣|I|.

Proof. Take an optimal packing and fill its unused capacity with dummy items. Every big knapsack contains at least H/wmax⁡=dwmax⁡2H/w_{\max} = d w_{\max}^{2} items, so by the pigeonhole principle, some weight class contributes at least R=∣B∣wmax⁡2R = |B|w_{\max}^{2} items to the big knapsacks. Choose this class as the pivot; if there are no big knapsacks, choose any class. Keep the full configurations of the small knapsacks. From every big knapsack remove all pivot items and groups of waw_a nonpivot items of the same weight until fewer than waw_a of each nonpivot class remain. These removals preserve the load modulo waw_a. Reserve RR of the removed pivot items and record all other removed items as bundles. This gives a feasible solution of Equation (7). Within each weight class, the rejected items may be chosen to be the cheapest ones without changing feasibility. Hence the objective equals the rejection cost of an optimal packing.

Conversely, assign the configurations of a feasible solution to knapsacks of their classes. Small knapsacks are full. Every big residual configuration fits, since wTc≤(d−1)(wa−1)wmax⁡<H\mathbf{w}^{\mathsf{T}}\mathbf{c} \le(d-1)(w_a-1)w_{\max} < H. Keep the R+baR+b_a pivot items aside and insert the nonpivot bundles first. At every stage, the total free space in the big knapsacks is at least the weight of all selected but unplaced items. In particular, it is at least waR≥∣B∣wmax⁡2w_aR \ge|B|w_{\max}^{2}. If B≠∅B \ne\varnothing, some big knapsack therefore has free space at least wmax⁡2w_{\max}^{2}. Every nonpivot bundle has weight wawi≤wmax⁡2w_aw_i \le w_{\max}^{2} and can therefore be placed. Afterwards, all remaining free spaces are multiples of waw_a and their sum is at least wa(R+ba)w_a(R+b_a). Thus all pivot items can also be placed. If B=∅B = \varnothing, the small configurations already have total weight TT, so the weight inequality forces all bundle variables to zero.

Choose the rejected items in each class to be its cheapest items, assign the remaining copies to the constructed positions of that weight, and discard dummy items. This produces a packing with rejection cost exactly the objective of Equation (7). Taking the minimum over pivot choices therefore yields an optimal solution of the original instance. Bundle placement and the assignment of original profit classes can both be performed in batches, so reconstruction is polynomial in the input and output encoding lengths. □\square

of Theorem 1.4. By Lemma A.1, it remains to solve Equation (7), which we do by applying Theorem 1.3. Use the d+1d+1 inequalities involving YiY_i as linking rows, and define

fi(t)=Fi(Ni−R1i=a−t)(i∈[d]),fd+1(t)=0.f_i(t)=F_i(N_i-R\mathbf{1}_{i=a}-t)\quad(i\in[d]),\qquad f_{d+1}(t)=0.

Each fif_i is discrete convex. The polynomial-time exact evaluation assumption of Theorem 1.3 holds by the piecewise-linear descriptions above. The formulation has d+1d+1 linking rows and at most H+wa+1H+w_a+1 blocks, with coefficient bound Δ≤H≤wmax⁡4\Delta\le H\le w_{\max}^{4}. There are at most (H+wa)(H+1)d=wmax⁡O(d)(H+w_a)(H+1)^d=w_{\max}^{O(d)} configurations. Their encoding, together with the rejection-cost functions, has length wmax⁡O(d)⋅poly⁡(∣I∣)w_{\max}^{O(d)}\cdot\operatorname{poly}(|I|); the number of profit classes affects only the polynomial factor.

Since d≤wmax⁡d\le w_{\max} and wa≤wmax⁡w_a\le w_{\max}, there are at most 2wmax⁡2w_{\max} linking rows and 3wmax⁡43w_{\max}^{4} blocks. Applying Theorem 1.3 to each of the dd pivot choices therefore takes

wmax⁡O(d)⋅poly⁡(∣I∣)w_{\max}^{O(d)}\cdot\operatorname{poly}(|I|)

time, including configuration enumeration and reconstruction. □\square

References

  1. [1]C. Brand, M. Koutecký, A. Lassota, and S. Ordyniak. “Separable Convex Mixed-Integer Optimization: Improved Algorithms and Lower Bounds”. In: 32nd Annual European Symposium on Algorithms (ESA 2024). Vol. 308. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, 32:1–32:18. DOI: 10.4230/LIPIcs.ESA.2024.32.DOI
  2. [3]W. J. Cook, A. M. H. Gerards, A. Schrijver, and É. Tardos. “Sensitivity theorems in integer linear programming”. In: Math. Program. 34.3 (1986), pp. 251–264. DOI: 10.1007/BF01582230.DOI
  3. [4]L. Chen, K. Jansen, and G. Zhang. “On the Optimality of Approximation Schemes for the Classical Scheduling Problem”. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014). SIAM, 2014, pp. 657–668. DOI: 10.1137/1.9781611973402.50.DOI
  4. [5]C. Chekuri and S. Khanna. “A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem”. In: SIAM Journal on Computing 35.3 (2005), pp. 713–728. DOI: 10.1137/S0097539700382820.DOI
  5. [6]D. N. Dadush. “Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation”. PhD thesis. Georgia Institute of Technology, 2012. URL: http://hdl.handle.net/1853/44807.
  6. [7]D. Dadush, A. Léonard, L. Rohwedder, and J. Verschae. “Optimizing Low Dimensional Functions over the Integers”. In: Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings. Vol. 13904. Lecture Notes in Computer Science. Springer, 2023, pp. 115–126. DOI: 10.1007/978-3-031-32726-1_9.DOI
  7. [8]F. Eisenbrand and R. Weismantel. “Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma”. In: ACM Transactions on Algorithms 16.1 (2020), 5:1–5:14. DOI: 10.1145/3340322.
  8. [9]S. Gupta, P. Jain, S. Seetharaman, and M. Zehavi. “A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma”. In: 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Vol. 358. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 14:1–14:17. DOI: 10.4230/LIPIcs.IPEC.2025.14.DOI
  9. [10]F. Gurski, C. Rehs, and J. Rethmann. “Knapsack Problems: A Parameterized Point of View”. In: Theoretical Computer Science 775 (2019), pp. 93–108. DOI: 10.1016/j.tcs.2018.12.019.DOI
  10. [11]C. Hunkenschröder, S. Pokutta, and R. Weismantel. “Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube”. In: SIAM J. Optim. 33.2 (2023), pp. 538–552. DOI: 10.1137/22M1489988.DOI
  11. [12]K. Jansen. “Parameterized Approximation Scheme for the Multiple Knapsack Problem”. In: SIAM Journal on Computing 39.4 (2009), pp. 1392–1412. DOI: 10.1137/080731207.DOI
  12. [13]K. Jansen. “A Fast Approximation Scheme for the Multiple Knapsack Problem”. In: SOFSEM 2012: Theory and Practice of Computer Science. Vol. 7147. Lecture Notes in Computer Science. Springer, 2012, pp. 313–324. DOI: 10.1007/978-3-642-27660-6_26.DOI
  13. [14]K. Jansen, K. Kahler, L. Pirotton, and M. Tutas. “New Algorithm for Combinatorial n-Folds and Applications”. In: 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Vol. 358. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 15:1–15:15. DOI: 10.4230/LIPIcs.IPEC.2025.15.DOI
  14. [15]K. Jansen and L. Rohwedder. “On Integer Programming, Discrepancy, and Convolution”. In: Mathematics of Operations Research 48.3 (2023), pp. 1481–1495. DOI: 10.1287/moor.2022.1308.DOI
  15. [16]R. Kannan. “Minkowski’s Convex Body Theorem and Integer Programming”. In: Math. Oper. Res. 12.3 (1987), pp. 415–440. DOI: 10.1287/moor.12.3.415.DOI
  16. [17]D. Knop, M. Koutecký, A. Levin, M. Mnich, and S. Onn. “High-multiplicity N-fold IP via configuration LP”. In: Math. Program. 200.1 (2023), pp. 199–227. DOI: 10.1007/S10107-022-01882-9.DOI
  17. [18]D. Knop, M. Koutecký, and M. Mnich. “Combinatorial n-fold Integer Programming and Applications”. In: Mathematical Programming 184.1–2 (2020), pp. 1–34. DOI: 10.1007/s10107-019-01402-2.DOI
  18. [19]M. Koutecký and J. Zink. “Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines”. In: Journal of Scheduling 28.1 (2025), pp. 139–156. DOI: 10.1007/s10951-024-00827-8.
  19. [20]H. W. Lenstra Jr. “Integer Programming with a Fixed Number of Variables”. In: Math. Oper. Res. 8.4 (1983), pp. 538–548. DOI: 10.1287/moor.8.4.538.DOI
  20. [21]R. R. Meyer. “On the existence of optimal solutions to integer and mixed-integer programming problems”. In: Math. Program. 7.1 (1974), pp. 223–235. DOI: 10.1007/BF01585518.
  21. [23]L. Rohwedder. “ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines”. In: 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Vol. 334. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 126:1–126:13. DOI: 10.4230/LIPIcs.ICALP.2025.126.
  22. [24]L. Rohwedder and K. Węgrzycki. “Space-Efficient Algorithm for Integer Programming with Few Constraints”. In: Integer Programming and Combinatorial Optimization - 26th International Conference, IPCO 2025, Baltimore, MD, USA, June 11–13, 2025, Proceedings. Vol. 15620. Lecture Notes in Computer Science. Springer, 2025, pp. 442–451. DOI: 10.1007/978-3-031-93112-3_32.

Paper details

vlnc:W_evzvy3gt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents