Программное обеспечение Solver для поиска ВСЕХ решений для целочисленного MIP

Question

У меня есть ряд задач (наборов уравнений и неравенств), для которых я знаю, что все переменные должны быть целыми числами и иметь конечное число решений. Я знаю, что если я возьму любую случайную целевую функцию и позволю ей решить lp или mip, то она найдет решение, однако мне нужны все решения проблемы, и, конечно, как можно более эффективно. Я действительно не беспокоюсь об оптимизации чего-либо, но, очевидно, большинство программного обеспечения, которое занимается этим, делает. Есть ли решатель, который может это сделать? Если да, то какой из них самый лучший / самый простой или какой вы бы порекомендовали? В лучшем случае тот, который может быть использован в качестве библиотеки C/C++.

Answer 1

Есть хорошая запись в блоге Пола Рубина о том, как найти K лучшие решения, которые можно легко обобщить, чтобы получить все решения. Как предложил Али, одним из подходов является использование пула решений. Два других подхода:

1. Используйте действующий обратный вызов для отслеживания и отклонения решений.
2. Используйте действующий обратный вызов с инъекцией раствора.

Смотрите сообщение в блоге для деталей.

Answer 2

IBM ILOG CPLEX имеет функцию пула решений и является бесплатной для академических целей.

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