An extension to Simply for solving Weighted Constraint Satisfaction Problems with Pseudo-Boolean Constraints
Miquel Bofill, Joan Espasa, Miquel Palahand, Mateu Villaret · 2012
Abstract: Max-Simply is a high-level programming framework for modelling and solving weighted CSP. Max-Simply can also deal with meta-constraints, that is, con-straints on constraints. The technology currently used to solve the generated prob-lem instances is SMT. In this paper we present a variant of Max-Simply which is able to generate not only SMT instances but also pseudo-Boolean instances for cer-tain modellings. Since there are problems that are more naturally encoded using pseudo-Boolean variables, the possibility of generating pseudo-Boolean instances can result in a more efficient and natural fit in some situations. We illustrate the expressiveness of the Max-Simply language by modelling some problems, and pro-vide promising performance results on the corresponding generated pseudo-Boolean instances using state-of-the-art pseudo-Boolean solvers.