Compiling Solution Configurations in Semiring Valuation Systems

Abstract. This paper describes a new method for solving optimization queries in semiring valuation systems. In contrast to existing techniques which focus essentially on the identification of solution configurations, we propose foremost the construction of an implicit representation of the solution configuration set in the shape of a Boolean function. This intermediate compilation step allows then to efficiently execute many further relevant queries that go far beyond the traditional task of enumerating solution configurations.