Выборка из взвешенного решения ограничений в Minizinc?

Question

Немного необычная проблема решения ограничений, которую я пытаюсь реализовать в MiniZinc: у меня есть CSP, который имеет некоторые жесткие ограничения и мягкое ограничение, согласно которому отношения в решении должны иметь статистически подобный профиль для примера решения. То есть, если на входе есть 5 «красных» и 12 «зеленых», найденное решение не обязательно должно иметь ровно 5 и 12, но должно иметь статистическую вероятность того, что оно будет иметь аналогичное распределение ... но также разрешать редкие решения, которые , например, не имеют красного.

Хотя у меня может быть жесткое ограничение на то, что дистрибутив должен точно соответствовать распределению, или получить все возможные решения и пример из этого, я бы предпочел стратегию поиска, которая может получить одно решение, которое Статистически вероятно, чтобы иметь аналогичное распределение (но может варьироваться). Или способ сделать это эквивалентным производительности.

Использование indomain random для assignmentannotation может показаться работоспособным, но, насколько я понимаю, единственный способ использовать взвешивание с ним - это заполнить домены несколькими значениями, чтобы выделить домен с правильным взвешиванием.

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

Answer 1

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

• Учитывая проблему, кажется, что вы действительно можете выполнить обработку мягких ограничений самостоятельно. Учитывая, что модель относительно легко решить, вы можете запустить модель только с жесткими ограничениями, используя флаг -a, чтобы дать вам все решения, а затем выбрать ранжирование решений, используя собственный скрипт. (Возможно, обратите внимание на расширение IPython для MiniZinc, которое облегчит обработку решений). Это, пожалуй, самое гибкое решение, и на самом деле вам решать, как вы хотите использовать мягкие ограничения. Я думаю, что этот подход хорошо работает для вашей проблемы, поскольку ваши мягкие ограничения кажутся скорее механизмом ранжирования решений.
• Модель с фактическими мягкими ограничениями и формулировка целевой функции. Мягкие ограничения могут быть смоделированы с помощью слабых переменных или логических выражений. Недавно даже появился специализированный язык для программных ограничений: MiniBrass . При моделировании с мягкими ограничениями часто сложно сформулировать целевую функцию. Непросто решить, какая комбинация мягких ограничений будет лучше, чем другие. Эта техника все еще часто используется, поскольку она может быть намного более эффективной, чем первая.

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

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