Целочисленное программирование - NP-Complete, как указано в по этой ссылке . Некоторые эвристические методы, используемые в функции intlinprog в Matlab (например, определение минимального и максимального значения для ограничения пространства поиска), но они не могут вообще изменить сложность проблемы.
Кроме того, если все значения находятся в диапазоне от -a до a, у нас есть алгоритм, который работает в N^2(R*a^2)^{2R+3}. Вы можете найти более подробную информацию здесь .