Разложение линейного Диофантового уравнения над натуральными

[Saxartur]

Здравствуйте!

Я занимаюсь задачей упаковки в контейнеры. Если быть точнее, я пытаюсь оценить нижнюю границу на количество контейнеров необходимых при "частичной доупаковке", то есть когда есть какое-то начальное решение и нам надо доупаковать оставшиеся предметы, минимизируя количество контейнеров. В целом, как искать нижнюю границу "полной упаковки" хорошо известно - с помощью генерации столбцов. Но, т.к. при частичной доупаковке теряется одинаковый размер контейнеров - это слегка проблематично.

Кроме прочего у меня чуть больше ограничений, чем в обычной задаче. К примеру ограничения не на один ресурс, а на два, конфликты и т.д., не буду вдаваться в подробности.

Я разработал некоторый алгоритм, который оценивает нижнюю границу и он даже иногда дает результат лучше, чем нижняя граница "полной упаковки".

Наконец, перейдем к моему вопросу. Мне кажется я могу сильно улучшить этот алгоритм и это улучшение сильно связано с задачей ниже:

Пусть даны $A$ - матрица $n\times m$, причем $a_{ij}\in \mathbb{N}$. И число $b\in \mathbb{N}$. Обозначим класс множеств $S_{b'}=\{x\in\mathbb{Z}_{\geq 0}| Ax=b'\}$.

Необходимо найти, такие $b_1,b_2\in\mathbb{N}:b_1+b_2=b$, что $S_{b}=S_{b_1}+S_{b_2}=\{x+y|x\in S_{b_1},~y\in S_{b_2}\}$.

То есть линейное диофантово уравнение над положительными натуральными числами $Ax=b$, должно раскладываться на две подзадачи $Ax=b_1$, $Ax=b_2$, что сумма множеств решений этих подзадач в точности равняется множеству решений первой задачи.

Такие разложения есть и на самом деле они не так редки. Естественно, можно просто найти это "перебором", с помощью солверов целочисленного программирования, но боюсь, что это будет достаточно долго считаться и не всегда такое разложение будет существовать. Кроме этого, я не до конца разобрался, возможно стоит рассматривать не равенство, а неравенство $b-a_1\leq Ax\leq b$, где $a_1$ - первый столбец матрицы $A$ (считаем, что в каждой строке элементы отсортированы), так или иначе решение первой задачи наверняка что-то скажет о второй. В идеале, если получится искать разложения не зная внутренней структуры множеств $S_b$.

Кроме этого, задачу можно сформулировать и так: Найти такой $b_1\in\mathbb{N}:\forall x\in S_{b}\exists x'\in S_{b_1}: x\geq x'$. Где $x\geq y \Leftrightarrow x-y\in \mathbb{Z}_{\geq 0}$.

Буду благодарен, если поделитесь своими мыслями по этой задаче!