Graf złożony z ograniczeń

Graf złożony z ograniczeniami jest nieskierowanym grafem ważonym w węzłach, powiązanym z danym problemem optymalizacji kombinatorycznej postawionym jako ważony problem spełniania ograniczeń . Opracowany i wprowadzony przez Satisha Kumara Thittamaranahalli (TK Satish Kumar), pomysł złożonego grafu ograniczeń jest dużym krokiem w kierunku ujednolicenia różnych podejść do wykorzystania „struktury” w ważonych problemach spełniania ograniczeń.

Ważony problem spełnienia ograniczeń (WCSP) to uogólnienie problemu spełnienia ograniczeń, w którym ograniczenia nie są już „twarde”, ale są rozszerzone w celu określenia nieujemnych kosztów związanych z krotkami . Celem jest zatem znalezienie przypisania wartości do wszystkich zmiennych z ich odpowiednich dziedzin, tak aby zminimalizować całkowity koszt. Ważone problemy spełniania ograniczeń znajdują niezliczone zastosowania w sztucznej inteligencji i informatyce . Są one również różnie określane jako losowe pola Markowa (w statystyce i przetwarzaniu sygnałów ) oraz problemy minimalizacji energii (w fizyce ).

Podczas gdy problemy spełniania ograniczeń ważonych są ogólnie NP-trudne do rozwiązania, kilka podklas można rozwiązać w czasie wielomianowym , gdy ich ważone ograniczenia wykazują określone rodzaje struktury numerycznej. Podklasy możliwe do zastosowania można również zidentyfikować, analizując sposób, w jaki ograniczenia są nakładane na zmienne. W szczególności ważony problem spełniania ograniczeń można rozwiązać w czasie wykładniczym tylko w drzewie jego wykresu zmiennych interakcji (sieć ograniczeń). Jednak główną wadą sieci ograniczeń jest to, że nie zapewnia ona ram obliczeniowych do wykorzystania numerycznej struktury ważonych ograniczeń.

W przeciwieństwie do sieci ograniczeń, złożony wykres ograniczeń zapewnia ujednoliconą strukturę do reprezentowania zarówno graficznej struktury interakcji zmiennych, jak i struktury numerycznej ważonych ograniczeń. Można go skonstruować za pomocą prostej procedury czasu wielomianowego; a dany ważony problem spełnienia ograniczeń można zredukować do problemu obliczenia minimalnego ważonego pokrycia wierzchołków dla powiązanego z nim złożonego grafu ograniczeń. „Hybrydowe” właściwości obliczeniowe złożonego wykresu ograniczeń znajdują odzwierciedlenie w następujących dwóch ważnych wynikach:

(Wynik 1) Złożony graf ograniczeń dla danego ważonego problemu spełniania ograniczeń ma taką samą szerokość drzewa jak powiązana z nim sieć ograniczeń.

(Wynik 2) Wiele podklas problemów spełniania ważonych ograniczeń, które można rozwiązać dzięki numerycznej strukturze ich ważonych ograniczeń, ma powiązane złożone grafy ograniczeń, które są z natury dwudzielne .

Wynik 1 pokazuje, że złożony graf z ograniczeniami może być użyty do uchwycenia graficznej struktury interakcji zmiennych (ponieważ minimalne ważone pokrycie wierzchołków dla dowolnego grafu może być obliczone w czasie wykładniczym tylko w szerokości drzewa tego grafu). Wynik 2 pokazuje, że złożony graf ograniczeń może być również użyty do uchwycenia numerycznej struktury ważonych ograniczeń (ponieważ minimalne ważone pokrycie wierzchołków można obliczyć w czasie wielomianowym dla grafów dwudzielnych).

Empirycznie, podczas rozwiązywania WCSP wykazano, że korzystniejsze jest zastosowanie algorytmów przekazywania komunikatów i programowania liniowego liczb całkowitych na złożonym grafie z ograniczeniami WCSP niż bezpośrednio na WCSP.

^ Kumar, TKS (2008). „Struktura ramowa dla hybrydowych wyników w problemach spełnienia ograniczeń ważonych logicznie” . Materiały z XIV Międzynarodowej Konferencji na temat zasad i praktyki programowania z ograniczeniami (CP) . Notatki z wykładów z serii książek Informatyka. Tom. 5202. s. 282–297. doi : 10.1007/978-3-540-85958-1_19 . ISBN 978-3-540-85958-1 .
^ Kumar, TKS (2008). „Techniki podnoszenia w przypadku problemów ze spełnieniem ograniczeń ważonych” (PDF) . Materiały z dziesiątego Międzynarodowego Sympozjum Sztucznej Inteligencji i Matematyki (ISAIM'2008) .
Bibliografia _ Kumar, TK Satish; Koenig, Sven (2017). „Redukcja Nemhausera-Trottera i podniesione przekazywanie wiadomości dla ważonego CSP”. Materiały z 14. Międzynarodowej Konferencji Integracji Technik Sztucznej Inteligencji i Badań Operacyjnych w Programowaniu z Ograniczeniami (CPAIOR) . Notatki z wykładów z serii książek Informatyka. Tom. 10335. Zygmunt. s. 387–402. doi : 10.1007/978-3-319-59776-8_31 . ISBN 978-3-319-59776-8 .
Bibliografia _ Koenig, Sven; Kumar, TK Satish (2017). „Kodowanie ILP oparte na złożonym grafie z ograniczeniami dla CSP ważonego boolem” . Materiały z 23. Międzynarodowej Konferencji na temat zasad i praktyki programowania z ograniczeniami (CP) . Notatki z wykładów z serii książek Informatyka. Tom. 10416. Zygmunt. s. 630–8. doi : 10.1007/978-3-319-66158-2_40 . ISBN 978-3-319-66158-2 .

[1] Kumar, TKS (2008). „Struktura ramowa dla hybrydowych wyników w problemach spełnienia ograniczeń ważonych logicznie” . Materiały z XIV Międzynarodowej Konferencji na temat zasad i praktyki programowania z ograniczeniami (CP) . Notatki z wykładów z serii książek Informatyka. Tom. 5202. s. 282–297. doi : 10.1007/978-3-540-85958-1_19 . ISBN 978-3-540-85958-1 .

[2] Kumar, TKS (2008). „Techniki podnoszenia w przypadku problemów ze spełnieniem ograniczeń ważonych” (PDF) . Materiały z dziesiątego Międzynarodowego Sympozjum Sztucznej Inteligencji i Matematyki (ISAIM'2008) .

[3] Bibliografia _ Kumar, TK Satish; Koenig, Sven (2017). „Redukcja Nemhausera-Trottera i podniesione przekazywanie wiadomości dla ważonego CSP”. Materiały z 14. Międzynarodowej Konferencji Integracji Technik Sztucznej Inteligencji i Badań Operacyjnych w Programowaniu z Ograniczeniami (CPAIOR) . Notatki z wykładów z serii książek Informatyka. Tom. 10335. Zygmunt. s. 387–402. doi : 10.1007/978-3-319-59776-8_31 . ISBN 978-3-319-59776-8 .

[4] Bibliografia _ Koenig, Sven; Kumar, TK Satish (2017). „Kodowanie ILP oparte na złożonym grafie z ograniczeniami dla CSP ważonego boolem” . Materiały z 23. Międzynarodowej Konferencji na temat zasad i praktyki programowania z ograniczeniami (CP) . Notatki z wykładów z serii książek Informatyka. Tom. 10416. Zygmunt. s. 630–8. doi : 10.1007/978-3-319-66158-2_40 . ISBN 978-3-319-66158-2 .