Создание уникальных решений с помощью программирования ограничений

У меня было краткое знакомство с CP и MiniZinc, но я не эксперт.

У меня есть модель CP, которую я не могу разместить здесь, банкомат, реализованный в MiniZinc. Мне нужно найти все возможные решения проблемы. Мы ожидаем, что их будет всего «несколько», скажем, менее 1000, более 100.

Я попытался решить модель с флагом -a, переданным в minizinc ver. 1.6, но я заметил, что многие печатаемые решения идентичны.

Здесь они относятся к «проекции». В другой статье, которую я читал, они использовали некий «механизм возврата».

Мне все еще непонятно.

Мои вопросы таковы:

  1. как лучше всего генерировать только уникальные решения из модели CP?
  2. Есть ли стандартный механизм, реализованный в библиотеках CP, таких как SCIP или Gecode? У него есть общее название?
  3. Насколько это эффективно с вычислительной точки зрения?
  4. это поддерживает minizinc? Как мне получить доступ к этой функции?

constraint-programming minizinc gecode
person a.tavs    schedule 23.09.2014    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Обычно системы CP дают вам только отдельные решения. Я подозреваю, что у вас есть переменные решения, которые не печатаются (не в разделе вывода), и вы не видите, что, если эти значения будут включены в решение, это будут уникальные решения.

В вопросе, с которым вы связались (это недавнее обсуждение), упоминается, что решатель Gecode FlatZinc (по крайней мере версия SVN) теперь генерирует отдельные решения с учетом подмножества переменных решения в выходной секции. Другой решатель FlatZinc, похоже, не имеет этой функции.

Если это не отвечает на ваши вопросы, опишите подробнее модель и пример вывода (включая раздел вывода).

person hakank    schedule 24.09.2014
comment
Indedd. В моей модели я написал ограничение типа MIP в форме a[t] >= b[t]-b[t-1], чтобы указать, что a [t] измеряет изменения между значениями b от времени t-1 до t. Я заменил его на a[t] = max(0, b[t]-b[t-1]) и работает как положено. Я задаюсь вопросом, нет ли лучшего способа выразить ограничение более эффективным способом. - person a.tavs; 02.10.2014