Методы распространения ограничений

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

Сущность этого метода заключается в сужении допустимых интервалов управляемых переменных с помощью учета (распространения) исходных ограничений на выходные параметры и .

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

(1)

(2)

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

Метод легко распространяется на задачи с нечисловыми параметрами. В этом случае вместо сокращения числовых интервалов уменьшают мощности допустимых подмножеств значений параметров.

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

Пример 1

Рассмотрим фрагмент структуры, состоящий из трех компонентов , и , причем , , . Заданы списки допустимых сочетаний компонентов в синтезируемой структуре:

Сокращение первого списка выполняется путем поочередного выбора в нем , фиксации в соответствующих значений , а затем в сопряженных с значений . Если в имеется элемент , , то он сохраняется в сокращенном списке, остальные сочетания c из удаляются. В нашем примере, поскольку значения в нет, то сочетание недопустимо и из удаляется. Далее для символа фиксируем в значение , ему в соответствует только значение . Поэтому — также недопустимое сочетание. Обработав подобным образом все списки, получаем результат распространения ограничений в виде .

Следовательно, решение состоит из единственной допустимой структуры, включающей компоненты .

В общем случае сокращение списков выполняется в итерационном процессе до совпадения их содержимого на двух последних итерациях.

На базе метода распространения ограничений компанией ILOG создан программный комплекс оптимизации и синтеза проектных решений, состоящий из подсистем Solver, Configurator, Scheduler и др.