MiniBrass: Soft constraints for MiniZinc

• Published in: Constraints : an international journal 2018-10, Vol.23 (4), p.403-450
• Main Authors: Schiendorfer, Alexander, Knapp, Alexander, Anders, Gerrit, Reif, Wolfgang
• Format: Article
• Language: English
• Subjects: Adequacy; Algebra; Artificial Intelligence; Computer Science; Constraint modelling; Domains; Modelling; Operations Research/Decision Theory; Optimization; Solvers
• ISSN: 1383-7133; 1572-9354
• DOI: 10.1007/s10601-018-9289-2

Over-constrained problems are ubiquitous in real-world decision and optimization problems. Plenty of modeling formalisms for various problem domains involving soft constraints have been proposed, such as weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures. In terms of modeling languages, however, the field of soft constraints lags behind the state of the art in classical constraint optimization. We introduce MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially ordered valuation structures (PVS) that is implemented as an extension of MiniZinc and MiniSearch. We first demonstrate the adequacy of PVS to naturally augment partial orders with a combination operation as used in soft constraints. Moreover, we provide the most general construction of a c-semiring from an arbitrary PVS. Both arguments draw upon elements from category theory. MiniBrass turns these theoretical considerations into practice: It offers a generic extensible PVS type system, reusable implementations of specific soft constraint formalisms as PVS types, operators for complex PVS products, and morphisms to transform PVS. MiniBrass models are compiled into MiniZinc to benefit from the wide range of solvers supporting FlatZinc. We evaluated MiniBrass on 28 “softened” MiniZinc benchmark problems with six different solvers. The results demonstrate the feasibility of our approach.