LLL‐reduction for integer knapsacks

Given a matrix A∈ℤ ^m×n satisfying certain regularity assumptions, a well‐known integer programming problem asks to find an integer point in the associated knapsack polytope $P\left(A\mathrm{,}b\right)=\left\{x\in {ℝ}_{\ge 0}^n:Ax=b\right\}$ or determine that no such point exists. We obtain an LLL‐based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector b.