Zusammengesetztes Diagramm für Einschränkungen - Constraint composite graph

Der zusammengesetzte Beschränkungsgraph ist ein knotengewichteter ungerichteter Graph, der einem gegebenen kombinatorischen Optimierungsproblem zugeordnet ist , das als gewichtetes Beschränkungserfüllungsproblem gestellt wird . Die von Satish Kumar Thittamaranahalli (TK Satish Kumar) entwickelte und eingeführte Idee des zusammengesetzten Constraint-Graphen ist ein großer Schritt zur Vereinheitlichung verschiedener Ansätze zur Nutzung der "Struktur" bei gewichteten Constraint-Zufriedenheitsproblemen.

Ein gewichtetes Einschränkungszufriedenheitsproblem (WCSP) ist eine Verallgemeinerung eines Einschränkungszufriedenheitsproblems, bei dem die Einschränkungen nicht mehr "hart" sind, sondern erweitert werden, um nicht negative Kosten anzugeben , die mit den Tupeln verbunden sind . Ziel ist es dann, eine Zuordnung von Werten zu allen Variablen aus ihren jeweiligen Domänen zu finden, um die Gesamtkosten zu minimieren. Probleme mit der Zufriedenheit mit gewichteten Einschränkungen finden unzählige Anwendungen in der künstlichen Intelligenz und in der Informatik . Sie werden auch verschiedentlich als Markov-Zufallsfelder (in der Statistik und Signalverarbeitung ) und Energie-Minimierungsprobleme (in der Physik ) bezeichnet.

Während Probleme mit der Zufriedenheit mit gewichteten Einschränkungen im Allgemeinen NP-schwer zu lösen sind, können mehrere Unterklassen in Polynomzeit gelöst werden, wenn ihre gewichteten Einschränkungen bestimmte Arten von numerischen Strukturen aufweisen. Traktierbare Unterklassen können auch identifiziert werden, indem analysiert wird, wie Einschränkungen über die Variablen gelegt werden. Insbesondere kann ein gewichtetes Problem der Einschränkungszufriedenheit zeitlich exponentiell nur in der Baumbreite seines Diagramms mit variabler Interaktion (Einschränkungsnetzwerk) gelöst werden . Ein Hauptnachteil des Einschränkungsnetzwerks besteht jedoch darin, dass es keinen Rechenrahmen zum Nutzen der numerischen Struktur der gewichteten Einschränkungen bereitstellt.

Im Gegensatz zum Constraint-Netzwerk bietet das Constraint-Composite-Diagramm einen einheitlichen Rahmen für die Darstellung sowohl der grafischen Struktur der variablen Interaktionen als auch der numerischen Struktur der gewichteten Constraints. Es kann unter Verwendung eines einfachen Polynomzeitverfahrens konstruiert werden; und ein gegebenes gewichtetes Beschränkungszufriedenheitsproblem kann auf das Problem des Berechnens der minimalen gewichteten Scheitelpunktabdeckung für seinen zugeordneten zusammengesetzten Beschränkungsgraphen reduziert werden . Die "hybriden" Berechnungseigenschaften des zusammengesetzten Constraint-Graphen spiegeln sich in den folgenden zwei wichtigen Ergebnissen wider:

(Ergebnis 1) Der zusammengesetzte Einschränkungsgraph eines gegebenen gewichteten Einschränkungserfüllungsproblems hat dieselbe Baumbreite wie das zugehörige Einschränkungsnetzwerk.

(Ergebnis 2) Viele Unterklassen von Problemen mit der Erfüllung gewichteter Einschränkungen, die aufgrund der numerischen Struktur ihrer gewichteten Einschränkungen nachvollziehbar sind, haben zusammengesetzte grafische Abhängigkeitsgraphen zugeordnet, die zweiteiliger Natur sind.

Ergebnis 1 zeigt, dass das zusammengesetzte Constraint-Diagramm verwendet werden kann, um die grafische Struktur der Variableninteraktionen zu erfassen (da eine minimal gewichtete Scheitelpunktabdeckung für jedes Diagramm nur in der Baumbreite dieses Diagramms zeitlich exponentiell berechnet werden kann). Ergebnis 2 zeigt, dass der zusammengesetzte Constraint-Graph auch verwendet werden kann, um die numerische Struktur der gewichteten Constraints zu erfassen (da für bipartite Graphen eine minimale gewichtete Vertex-Abdeckung in Polynomzeit berechnet werden kann).

Empirisch hat sich beim Lösen eines WCSP gezeigt, dass es vorteilhafter ist, Message-Passing-Algorithmen und ganzzahlige lineare Programmierung auf den zusammengesetzten Constraint-Graphen des WCSP anzuwenden als direkt auf den WCSP.

Verweise

  1. ^ Kumar, TKS (2008). "Ein Framework für hybride Traktierbarkeit führt zu Problemen bei der Zufriedenheit mit booleschen gewichteten Einschränkungen" . Vorträge der 14. Internationalen Konferenz über Prinzipien und Praktiken der Constraint-Programmierung (CP) . Lecture Notes in der Buchreihe Informatik. 5202 . S. 282–297. doi : 10.1007 / 978-3-540-85958-1_19 . ISBN   978-3-540-85958-1 .
  2. ^ Kumar, TKS (2008). "Hebetechniken für Probleme mit der Zufriedenheit mit gewichteten Einschränkungen" (PDF) . Vorträge des 10. Internationalen Symposiums für Künstliche Intelligenz und Mathematik (ISAIM'2008) .
  3. ^ Xu, Hong; Kumar, TK Satish; Koenig, Sven (2017). "Die Nemhauser-Trotter-Reduzierung und die Aufhebung der Nachrichtenübermittlung für den gewichteten CSP". Vorträge der 14. Internationalen Konferenz zur Integration von Techniken der künstlichen Intelligenz und der Operationsforschung in die Constraint-Programmierung (CPAIOR) . Lecture Notes in der Buchreihe Informatik. 10335 . Springer. S. 387–402. doi : 10.1007 / 978-3-319-59776-8_31 . ISBN   978-3-319-59776-8 .
  4. ^ Xu, Hong; Koenig, Sven; Kumar, TK Satish (2017). "Eine auf Constraint-Composite-Graphen basierende ILP-Codierung des Booleschen gewichteten CSP". Vorträge der 23. Internationalen Konferenz über Prinzipien und Praktiken der Constraint-Programmierung (CP) . Lecture Notes in der Buchreihe Informatik. 10416 . Springer. S. 630–8. doi : 10.1007 / 978-3-319-66158-2_40 . ISBN   978-3-319-66158-2 .