| Popis: |
Over-constrained problems are ubiquitous in real-world decision and optimization problems, in particular, those emerging from self-organizing, autonomous systems where the full problem specification is only available at runtime. To address over-constrainedness, several theoretical formalisms to describe soft constraints have been proposed, including weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures such as valuation structures or c-semirings. In terms of implemented modeling languages and solvers, however, the field of soft constraints lags far behind the state of the art in classical constraint optimization. Therefore, this dissertation describes MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially-ordered valuation structures (PVS). It is implemented as an extension of MiniZinc and MiniSearch. The most important characteristics of MiniBrass, and the ones that distinguish it from previous work, are that it is extensible and modular, supports a variety of concrete soft constraint formalisms, works with many solvers (inherited from MiniZinc), admits a graphical modeling language, and has been applied to several real-life case studies. Contributions of this dissertation include the following: (1) The design, implementation, and performance evaluation of MiniBrass using 28 benchmark problems and six solvers, (2) A formal foundation that includes the systematic derivation of partially-ordered valuation structures and c-semirings from partial orders using basic category theory, (3) The qualitative soft constraint formalism constraint preferences, and (4) concepts for multiagent optimization with (possibly) antagonistic preferences, including lexicographic and Cartesian products as well as voting operators. Zahlreiche Entscheidungs- und Optimierungsprobleme in praktischen Anwendungen sind überbestimmt, also unlösbar mit der gegebenen Menge an Nebenbedingungen (Constraints). Im Besonderen betrifft dies jene Probleme, die dem Umfeld selbstorganisierender oder autonomer Systeme entstammen und deren Parameter erst zur Laufzeit vollständig bekannt sind. Zur Spezifikation und Lösung solcher Probleme wurden mehrere theoretische Formalismen vorgestellt, wie zum Beispiel gewichtete, unscharfe oder probabilistische Constraints, welche die Beschreibung weicher Bedingungen ermöglichen, um Probleme lösbar zu machen. All diese Formalismen lassen sich als Instanzen algebraischer Strukturen wie Bewertungsstrukturen oder C-Halbringen ausdrücken. Was tatsächlich implementierte Modellierungssprachen betrifft, hinkt das Gebiet der weichen Bedingungen allerdings weit dem Stand der Technik in klassischer Constraint-Optimierung hinterher. Zu diesem Zweck stellt diese Dissertation MiniBrass vor, eine vielseitige Modellierungssprache für weiche Bedingungen, die auf dem vereinheitlichenden algebraischen Rahmen der partiell geordneten Bewertungsstrukturen (eng. PVS) aufsetzt. Sie ist als Erweiterung zu MiniZinc und MiniSearch implementiert. Die wichtigsten Eigenschaften des MiniBrass-Systems (und zugleiche jene, die es von vorherigen Ansätzen abgrenzen) sind, dass es erweiterbar und modular ist, eine Vielzahl von konkreten Formalismen unterstützt, für zahlreiche Solver übersetzen kann (durch die Übersetzung nach MiniZinc), eine grafische Modellierungsform erlaubt und auf mehrere Fallstudien angewandt wurde. Zu den Beiträgen dieser Dissertation zählen: (1) der Entwurf, die Implementierung und die experimentelle Evaluation der Leistungsfähigkeit von MiniBrass auf 28 Benchmark-Problemen mit sechs Solvern; (2) eine formale Fundierung, welche die systematische Konstruktion partiell geordneter Bewertungsstrukturen und von C-Halbringen basierend auf partiellen Ordnungen mittels elementarer Kategorientheorie umfasst; (3) der qualitative Spezifikationsformalismus Constraint-Präferenzen; sowie (4) Konzepte und Algorithmen zur Optimierung in Multiagenten-Systemen mit (möglicherweise antagonistischen) Präferenzen unter Verwendung von lexikographischen und kartesischen Produkten sowie sozialen Auswahlfunktionen. |
