Soft Constraints in MiniBrass: Foundations and Applications

Author: 

Alexander Schiendorfer

School: 

University of Augsburg

Supervisors: 

Wolfgang Reif

Abstract: 

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.

Graduated: 

Monday, November 12, 2018

PDF of thesis: