Составной граф ограничений - Constraint composite graph

В составной граф ограничений взвешенный по узлам неориентированный граф, связанный с данным комбинаторная оптимизация проблема поставлена ​​как взвешенная проблема удовлетворения ограничений. Идея составного графа ограничений, разработанная и представленная Сатишем Кумаром Титтамаранахалли (T. K. Satish Kumar), является большим шагом на пути к объединению различных подходов к использованию «структуры» в задачах взвешенного удовлетворения ограничений.[1][2]

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

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

В отличие от сети ограничений, составной граф ограничений обеспечивает объединяющую основу для представления как графической структуры взаимодействий переменных, так и числовой структуры взвешенных ограничений. Его можно построить, используя простую процедуру за полиномиальное время; и данная проблема удовлетворения взвешенного ограничения сводится к задаче вычисления минимально взвешенного крышка вершины для связанного с ним составного графа ограничений. «Гибридные» вычислительные свойства составного графа ограничений отражены в следующих двух важных результатах:

(Результат 1) Составной граф ограничений данной взвешенной задачи удовлетворения ограничений имеет ту же древовидную ширину, что и связанная с ним сеть ограничений.

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

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

Эмпирическим путем при решении WCSP было показано, что более выгодно применять алгоритмы передачи сообщений и целочисленное линейное программирование на составном графе ограничений WCSP, чем непосредственно на WCSP.[3][4].

Рекомендации

  1. ^ Кумар, Т. К. С. (2008), "Основа гибридной управляемости результатов в задачах удовлетворения булевых взвешенных ограничений ", Труды Четырнадцатой Международной конференции по принципам и практике ограниченного программирования (CP).
  2. ^ Кумар, Т. К. С. (2008), "Методы подъема для задач удовлетворения взвешенных ограничений ", Материалы Десятого Международного симпозиума по искусственному интеллекту и математике (ISAIM'2008).
  3. ^ Сюй, Хун; Кумар, Т. К. Сатиш; Кениг, Свен (2017). «Сокращение Немхаузера-Троттера и повышение передачи сообщений для взвешенного CSP». Материалы 14-й Международной конференции по интеграции искусственного интеллекта и методов исследования операций в программировании с ограничениями (CPAIOR). Springer. С. 387–402. Дои:10.1007/978-3-319-59776-8_31.
  4. ^ Сюй, Хун; Кениг, Свен; Кумар, Т. К. Сатиш (2017). «Кодирование ILP на основе составного графа для логического взвешенного CSP». Труды 23-й Международной конференции по принципам и практике программирования с ограничениями (CP). Springer. С. 630–638. Дои:10.1007/978-3-319-66158-2_40.