Программное обеспечение Solver для поиска ВСЕХ решений для целочисленного MIP
У меня есть ряд задач (наборов уравнений и неравенств), для которых я знаю, что все переменные должны быть целыми числами и иметь конечное число решений. Я знаю, что если я возьму какую-либо случайную целевую функцию и позволю на нее решить lp или mip, она решение, однако я хочу все решения проблемы, и, конечно же, максимально эффективно. Я действительно не беспокоюсь об оптимизации чего-либо, но, очевидно, большинство программного обеспечения, которое имеет дело с этим, делает. Есть ли решатель, который может это сделать? Если да, какой из них самый лучший / самый простой, или какой вы бы порекомендовали? В лучшем случае тот, который может быть использован в качестве библиотеки C / C ++.
Решение
Есть хороший Сообщение блога Пол Рубин о том, как найти K лучшие решения, которые можно легко обобщить, чтобы получить все решения. Как предложил Али, одним из подходов является использование пула решений. Два других подхода:
- Используйте действующий обратный вызов для отслеживания и отклонения решений.
- Используйте действующий обратный вызов с инъекцией раствора.
Увидеть Сообщение блога для деталей.
Другие решения
IBM ILOG CPLEX имеет пул решений особенность, и это бесплатно для академических целей.
Я думаю, что вы, вероятно, можете получить все решения, если вы установите максимальный размер пула достаточно большим. Я не знаю точно, никогда не пытался.