Logo des Repositoriums

Auflistung nach Schlagwort "CSP"

1 - 3 von 3
  • Textdokument
    The Power of Regular Constraints in CSPs
    (INFORMATIK 2017, 2017) Löffler, Sven; Liu, Ke; Hofstedt, Petra
    This paper discusses the use of the regular membership constraint as a replacement for other (global) constraints. The goal is to replace some or all constraints of a constraint satisfaction problem (CSP) with regular constraints and to combine them into a new regular constraint to remove redundancy and to improve the solution speed of CSPs. By means of a rostering problem as an example it is shown that our approach allows a significant improvement of the solution performance due to a reduction of the size of the search tree.
  • Textdokument
    A Survey of Constraint Transformation Methods
    (INFORMATIK 2021, 2021) Löffler, Sven; Becker, Ilja; Kroll, Franz; Hofstedt, Petra
    The solution performance of finite domain (FD) constraint problems can often be improved by either transforming particular constraints or sub-problems into other FD constraints like binary, table or regular membership constraints, or by transformation of the complete FD problem into an equivalent problem but of another domain, e.g. in a SAT problem. Specialized constraint solvers (like binary or SAT solvers) can outperform general constraint solvers for certain problems. However, this comes with high efforts for the transformation and/or other disadvantages such as a restricted set of constraints such specialized solvers can handle or limitations on the variables domains. In this paper we give an overview of CSP and constraint transformations and discuss applicabilibty and advantages and disadvantages of these approaches.
  • Textdokument
    Using Hypertree Decomposition for Parallel Constraint Solving
    (INFORMATIK 2017, 2017) Liu, Ke; Loeffler, Sven; Hofstedt, Petra
    Multi-core processors or many-core processors have become the standard configuration for computers nowadays. Yet, the mainstream constraint solvers have not fully utilized these available computation resources due to the intrinsic difficulty on decomposing constraint satisfaction problems (CSPs). This paper reviews the previous research in parallel constraint solving and proposes a new approach for mapping constraint networks on multi-core or many-core processors by means of hypertree decomposition. We give theoretical considerations and our plans for future research.