Eclipse CLP маркировка: исключить перестановки - PullRequest
Новая
       23

Eclipse CLP маркировка: исключить перестановки

2 голосов
/ 26 апреля 2019

Я решаю проблему планирования (кратко описано здесь: Планирование SWI Prolog CLP (FD) переключено на ECLP).

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

Часть строки проблемы / графика выглядит как D1,D2,N1,N2,A0,A1,A2,..,A9, где стоимость этих переменных равна C1,C1,C1,C1,C2,C2,C2,...,C2. Таким образом, с этой точки зрения любая перестановка присваиваний A0..A9 имеет одинаковую стоимость. Но, очевидно, в процессе маркировки решатель откатывает все возможности.

Краткое примечание: я вычисляю это только в моей голове, но я думаю, что пространство поиска только для этой описанной части похоже на число подмножеств размера 10 из области размера 15 * 10 ! . Это довольно много места для возврата. И с точки зрения затрат / оптимизации, а также удовлетворения ограничений, каждая перестановка имеет одинаковую стоимость / выполнимость - порядок переменных не имеет значения.

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

1 Ответ

3 голосов
/ 26 апреля 2019

То, о чем вы говорите, это вопрос симметрии в моделировании, и этому посвящена целая область исследований.Я бы сказал, что по существу есть три способа решения этой проблемы:

  1. переформулируйте модель с различными переменными , так что по сути меньше способов представления эквивалентных решений
  2. добавить ограничения, нарушающие симметрию , чтобы уменьшить общее число решений, но сохранить хотя бы один из каждого класса эквивалентности.Обычно это делается с помощью арифметических или лексикографических ограничений порядка, которые эффективно определяют, как должно выглядеть «каноническое» представление решения.
  3. попробуйте метод динамического нарушения симметрии , который предоставляет ваша система,такие как ldsb .Обычно они описывают симметрию и пытаются что-то с ней сделать (но не ожидайте чудес).

В вашем случае я бы начал с пункта 1: у вас в настоящее время есть переменные A [I, D] = W означает «слот I типа A в день D заполнен рабочим W», хотя все ваши A-слоты эквивалентны.

Вместо этого вы можете иметь двоичные переменные JobA [D, W] = 1"работник W выполняет задание типа A в день D" вместе с ограничением sum(JobA[D,*])#=10, чтобы убедиться, что у вас заполнено 10 слотов.

Другая модель, которую я могу себе представить, состоит в том, чтобы иметь переменные Job [D, W] = T «работник W выполняет задание типа T в день D» (кодируя ваши типы заданий T как 1..3) и использует вхождения / 3 или gcc / 2 для обеспечения выполнения ваших различных условий.

...