On s'intéresse au problème d'optimiser une fonction objectif g(W x) + c^T x pour x entier, où chaque coordonnée de x est contrainte dans un intervalle. On suppose que la matrice W est à coefficient entiers de valeur absolue bornée par Delta, et qu'elle projette x sur un espace de petite dimension m << n. Ce problème est une généralisation du résultat de Hunkenschröder et al. dans lequel g est séparable convexe, et x est dans un 0-1 hypercube.

On présentera un algorithme en complexité n^m (m Delta)^O(m^2), sous la supposition que l'on sache résoudre efficacement le problème lorsque n = m. Cet algorithme utilise les travaux d'Eisenbrand et Weismantel sur la programmation linéaire entière avec peu de contraintes.

L'algorithme présenté peut être employé théoriquement dans plusieurs problèmes notamment la programmation mixte linéaire avec peu de contraintes, ou encore le problème du sac à dos où l'on doit acheter son sac.