Проблема удовлетворения взвешенных ограничений

В искусственного интеллекта и исследованиях операций проблема удовлетворения взвешенных ограничений ( WCSP ), также известная как проблема удовлетворения ограничений ( VCSP ), представляет собой обобщение проблемы удовлетворения ограничений (CSP), где некоторые ограничения могут быть нарушены (в соответствии с степень нарушения) и в чем могут быть выражены предпочтения среди решений. Это обобщение позволяет представить более реальные проблемы, в частности те, которые являются чрезмерно ограниченными (ни одно решение не может быть найдено без нарушения хотя бы одного ограничения), или те, где мы хотим найти решение с минимальной стоимостью (согласно функция стоимости ) среди множества возможных решений.

Формальное определение

Сеть взвешенных ограничений (WCN), также известная как Сеть функций стоимости (CFN), представляет собой тройку $\langle X,C,k\rangle$ где $X$ — конечный набор дискретных переменных, $C$ — конечный набор мягких ограничений и $k>0$ является либо натуральным целым числом, либо $\infty$ .

Каждое мягкое ограничение $c_{S}\in C$ включает в себя упорядоченный набор $S$ переменных, называемый его областью действия, и определяется как функция стоимости из $l(S)$ к $\langle 0,...,k\rangle$ где $l(S)$ - это набор возможных реализаций $S$ . Когда создание экземпляра $I\in l(S)$ задана стоимость $k$ , т.е. $c_{S}(I)=k$ , говорят, запрещено. В противном случае это допускается с соответствующей стоимостью (0 — полностью удовлетворительно).

В WCSP — особый подкласс Valued CSP (VCSP), ^[1] затраты суммируются с конкретным оператором $\oplus$ определяется как:

\forall \alpha ,\beta \in \langle 0,...,k\rangle ,\alpha \oplus \beta =\min(k,\alpha +\beta )

.

Частичная инверсия $\oplus$ является $\ominus$ определяется:

Если

0\leq \beta \leq \alpha <k

,

\alpha \ominus \beta =\alpha -\beta

и если

0\leq \beta <k

,

k\ominus \beta =k

.

Без ограничения общности существование нулевого ограничения $c_{\emptyset }$ (стоимость), а также наличие унарного ограничения $c_{x}$ для каждой переменной $x$ предполагается.

Общая стоимость полной реализации $I\in l(X)$ есть ограниченная сумма стоимости $I$ на $c_{S}$ для всех мягких ограничений $c_{S}\in C$ , включая нулевую стоимость $c_{\emptyset }$ и унарные затраты на $I$ переменных из $X$ .

При рассмотрении WCN/CFN обычная (NP-сложная) задача WCSP — найти полную реализацию с минимальной стоимостью. Могут быть определены и другие задачи в смежной области графической модели . ^[2]

Разрешение двоичных/троичных WCSP

Подход с операциями переноса затрат

Согласованность узла (NC) и согласованность дуги (AC), введенные для задачи удовлетворения ограничений (CSP), были изучены позже в контексте WCSP.Кроме того, было предложено несколько согласований наилучшей формы постоянства дуги: постоянство полной направленной дуги (FDAC) , ^[3] Согласованность экзистенциальной направленной дуги (EDAC) , ^[4] Согласованность виртуальной дуги (VAC) ^[5] и Оптимальная консистенция мягкой дуги (OSAC) . ^[6]

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

Проект: перенос затрат от ограничений к унарным ограничениям
ProjectUnary: перенос стоимости от унарного ограничения к нулевому ограничению.
Расширение: перенос стоимости от унарного ограничения к ограничению.

Основные преобразования, сохраняющие эквивалентность.

Цель преобразований, сохраняющих эквивалентность, — сконцентрировать затраты на нулевом ограничении. $c_{\emptyset }$ и эффективно удалять экземпляры и значения со стоимостью, добавленной к $c_{\emptyset }$ , которая больше или равна запрещенной стоимости или стоимости лучшего решения, найденного на данный момент. Для решения WCSP обычно используется метод ветвей и границ с нижней границей $c_{\emptyset }$ и верхняя граница $k$ .

Подход без операций переноса затрат

Альтернативой алгоритмам переноса затрат является алгоритм PFC-MRDAC. ^[7] который представляет собой классический алгоритм ветвей и границ, который вычисляет нижнюю границу $lb$ в каждом узле дерева поиска, что соответствует занижению стоимости любого решения, которое можно получить из этого узла. Стоимость найденного лучшего решения равна $ub$ . Когда $lb\geq ub$ , то дерево поиска из этого узла сокращается.

Другой, более поздний подход основан на суперрепараметризации. ^[8] что позволяет ослабить проблему и вычислить более точные границы.

Разрешение n-арных WCSP

Было показано, что алгоритмы переноса затрат особенно эффективны для решения реальной проблемы, когда мягкие ограничения являются двоичными или троичными (максимальная арность ограничений в задаче равна 2 или 3).Для мягких ограничений большой арности перенос затрат становится серьезной проблемой, поскольку риск комбинаторного взрыва необходимо контролировать .

Алгоритм под названием GAC ^В-ВСТР , ^[9] было предложено применить слабую версию свойства Generalized Arc Consistency (GAC) к мягким ограничениям, определенным экстенсионально, путем перечисления кортежей и их стоимости.Этот алгоритм сочетает в себе два метода, а именно простое табличное сокращение ( STR ). ^[10] и перенос затрат. Значения, которые больше не соответствуют GAC, выявляются ивычисляются минимальные стоимости ценностей. Это особенно полезно для эффективного выполнения операций прогнозирования, необходимых для создания GAC.

Также изучались глобальные функции стоимости со специальной семантикой (например, SoftAllDifferent, SoftAmong) и поливременной сложностью. ^[11]

Решатели

https://www.ics.uci.edu/~dechter/software.html
https://miat.inrae.fr/toulbar2 (на основе операций по переносу затрат)

Тесты

Многие реальные тесты WCSP доступны на http://genoweb.toulouse.inra.fr/~degivry/evalgm. ^[12] и https://forgemia.inra.fr/thomas.schiex/cost-function-library (более старая версия http://costfunction.org/en/benchmark ). Дополнительные тесты MaxCSP доступны на http://www.cril.univ-artois.fr/~lecoutre/#/benchmarks (устаревший сайт, см. также http://xcsp.org/series ).

См. также

Ссылки

^ MC Cooper, S de Givry и T Schiex. Проблемы удовлетворения ценных ограничений, страницы 185–207. Международное издательство Springer, 2020.
^ М. Купер, С. де Живри и Т. Шикс. Графические модели: Запросы, сложность, алгоритмы (учебник). На 37-м Международном симпозиуме по теоретическим аспектам информатики (STACS-20), том 154 LIPics, страницы 4:1–4:22, Монпелье, Франция, 2020 г.
^ М. Купер. Операции приведения при удовлетворении нечетких или значимых ограничений. Нечеткие множества иСистемы, 134(3):311–342, 2003.
^ С. де Живри, Ф. Эрас, М. Зитницки и Дж. Ларроса. Последовательность экзистенциальной дуги: приближаемсядо полной согласованности дуги в взвешенных CSP. В материалах IJCAI '05, страницы 84–89, 2005 г.
^ М. Купер, С. де Живри, М. Санчес, Т. Шикс, М. Зитницки. Согласованность виртуальной дуги для взвешенного CSP. В материалах AAAI '08, стр. 253–258, 2008 г.
^ М. Купер, С. де Живри, М. Санчес, Т. Шикс, М. Зитницки и Т. Вернер. Еще раз о стабильности мягкой дуги. Искусственный интеллект, 174(7-8):449–478, 2010.
^ EC Фрейдер и Р. Дж. Уоллес. Частичное удовлетворение ограничений. Искусственный интеллект, 58(1-3): 21–70, 1992.
^ Т. Дласк, Т. Вернер и С. де Живри. Границы взвешенных CSP с использованием распространения ограничений и суперрепараметризации. В Proc. CP-21, Монпелье, Франция, 2021 г.
^ К. Лекутр, Н. Пэрис, О. Руссель, С. Табари. Распространение мягких ограничений таблицы. В материалах CP'12, стр. 390–405, 2012 г.
^ К. Лекутр. STR2: Оптимизировано простое табличное сокращение для ограничения таблицы. Ограничения,16(4):341–371, 2011.
^ Д. Аллуш, К. Бессьер, П. Буазумо, С. де Живри, П. Гутьеррес, Дж. Х. М. Ли, К. Л. Люн, С. Лудни, Ж. П. Метивье, Т. Шиекс и Ю. Ву. Преобразования глобальных функций стоимости, сохраняющие управляемость. Искусственный интеллект, 238:166-189, 2016.
^ Б. Херли, Б. О'Салливан, Д. Аллуш, Г. Кацирелос, Т. Шиекс, М. Зитницки, С. де Живри. Многоязычная оценка точных решателей в дискретной оптимизации графической модели. Ограничения, 21(3):413–434, 2016.

[1] MC Cooper, S de Givry и T Schiex. Проблемы удовлетворения ценных ограничений, страницы 185–207. Международное издательство Springer, 2020.

[2] М. Купер, С. де Живри и Т. Шикс. Графические модели: Запросы, сложность, алгоритмы (учебник). На 37-м Международном симпозиуме по теоретическим аспектам информатики (STACS-20), том 154 LIPics, страницы 4:1–4:22, Монпелье, Франция, 2020 г.

[3] М. Купер. Операции приведения при удовлетворении нечетких или значимых ограничений. Нечеткие множества иСистемы, 134(3):311–342, 2003.

[4] С. де Живри, Ф. Эрас, М. Зитницки и Дж. Ларроса. Последовательность экзистенциальной дуги: приближаемсядо полной согласованности дуги в взвешенных CSP. В материалах IJCAI '05, страницы 84–89, 2005 г.

[5] М. Купер, С. де Живри, М. Санчес, Т. Шикс, М. Зитницки. Согласованность виртуальной дуги для взвешенного CSP. В материалах AAAI '08, стр. 253–258, 2008 г.

[6] М. Купер, С. де Живри, М. Санчес, Т. Шикс, М. Зитницки и Т. Вернер. Еще раз о стабильности мягкой дуги. Искусственный интеллект, 174(7-8):449–478, 2010.

[7] EC Фрейдер и Р. Дж. Уоллес. Частичное удовлетворение ограничений. Искусственный интеллект, 58(1-3): 21–70, 1992.

[8] Т. Дласк, Т. Вернер и С. де Живри. Границы взвешенных CSP с использованием распространения ограничений и суперрепараметризации. В Proc. CP-21, Монпелье, Франция, 2021 г.

[9] К. Лекутр, Н. Пэрис, О. Руссель, С. Табари. Распространение мягких ограничений таблицы. В материалах CP'12, стр. 390–405, 2012 г.

[10] К. Лекутр. STR2: Оптимизировано простое табличное сокращение для ограничения таблицы. Ограничения,16(4):341–371, 2011.

[11] Д. Аллуш, К. Бессьер, П. Буазумо, С. де Живри, П. Гутьеррес, Дж. Х. М. Ли, К. Л. Люн, С. Лудни, Ж. П. Метивье, Т. Шиекс и Ю. Ву. Преобразования глобальных функций стоимости, сохраняющие управляемость. Искусственный интеллект, 238:166-189, 2016.

[12] Б. Херли, Б. О'Салливан, Д. Аллуш, Г. Кацирелос, Т. Шиекс, М. Зитницки, С. де Живри. Многоязычная оценка точных решателей в дискретной оптимизации графической модели. Ограничения, 21(3):413–434, 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]