Minizinc, Gecode, как получить идентичные решения для распределенных серверов, с моделью нескольких решений?

Question

Я использую minizinc и gecode, чтобы решить проблему минимизации распределенным способом. У меня есть несколько распределенных серверов, которые решают одну и ту же модель с одинаковым вводом, и я хочу, чтобы все серверы получили одно и то же решение.

Проблема состоит в том, что модель имеет несколько решений, что периодически заставляет серверы независимо предлагать разные решения. Не имеет значения, какое решение будет выбрано, если оно одинаково для всех серверов. Я также использую аргументы "-p" с gecode для использования нескольких потоков (если это актуально).

Есть ли способ, которым я мог бы решить эту проблему?

Например, я думал о выводе всех решений, а затем сортировал их по алфавиту на каждом сервере.

Спасибо!

Answer 1

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

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

Ваше предложение сортировки решения возможно, но будет стоить дорого. Есть два способа сделать это. Вы можете найти все решения, используя -a помечайте и сортируйте их впоследствии, или вы можете изменить свою модель, чтобы решение было первым решением, если вы их отсортируете. Этот второй вариант может быть достигнут путем изменения стратегии поиска. Оба эти решения могут быть очень дорогими и могут (более чем) экспоненциально увеличить время выполнения.

Если вы вообще обеспокоены временем выполнения, то я советую вам посоветоваться с Патриком Трентином, запустить модель на главном узле и распространить решение. Это будет наиболее эффективным во время вычислений и, скорее всего, таким же эффективным во время выполнения.