Enhancing set constraint solvers with lexicographic bounds |
| |
Authors: | Andrew Sadler Carmen Gervet |
| |
Institution: | (1) Imperial College, SW7 2AZ London, UK |
| |
Abstract: | Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems,
such as bin-packing, set partitioning, circuit and combinatorial design. In this paper we present and evaluate a new means
towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems
with a particular attention to the challenging symmetrical set problems often cast as Combinatorial Design Problems (CDPs).
While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are
often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs
that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends
the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality
restrictions applied to the variable, and allow for active symmetry breaking using ordering constraints. Our contribution
includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical
evaluation on benchmark CDPs. |
| |
Keywords: | Constraint programming Artificial intelligence Modelling languages |
本文献已被 SpringerLink 等数据库收录! |
|