The saying goes, “All roads lead to Rome.” However, in programming, particularly in constraint programming, the approach taken to reach a solution is crucial. In an ideal declarative world, a constraint solver would solve any problem optimally and as soon as possible, regardless of its specific formulation. In reality, however, the performance of a constraint program is highly dependent on the structure of its problem modeling. The performance of a constraint model can often be improved either by transforming the entire constraint problem (e.g. in SAT problems) or by converting subproblems into single constraints (e.g. table or regular constraints). While the first method improves the solution speed only for very specific problems, the second method requires a great deal of expert knowledge on the part of the modeler regarding the solution processes of a constraint problem. This paper is based on the dissertation [1] and explores various approaches to transforming any finite domain constraint satisfaction problem into linear pseudo-Boolean CSPs. These transformations have a direct impact on the solution speed and enable the use of linear pseudo-Boolean solvers or even more specific solvers for the entire problem.

Indoor location is a growing topic for hospitals, retirement homes and in case of emergency. For the resource efficient (indoor) positioning of mobile individuals an optimized distribution of the used sensors is necessary. The placement of beacons (sensors) in a building (indoor positioning) can be a difficult and laborious task, especially if done by hand. Multiple researchers already tried to tackle this problem using different algorithms and under the consideration of distinct use cases. However, none of the currently known methods incorporate constraint programming by using only Boolean variables. In this paper we tried to develop a new method for an efficient placement of Bluetooth Low Energy (BLE) beacons in an indoor scenario. More specifically, we try to optimize the beacons for a trilateration algorithm used for indoor positioning. This algorithm requires that three beacons should be in range for every possible position in the building. In a next step the initially calculated beacon positions are further optimized. This is done by trying to reduce the number of beacons used. Afterwards we evaluate the quality of the beacon placements by comparing it against a manually optimized beacon placement and evaluating it in an existing building by checking the quality of multiple sample positions.

This paper describes a new approach on optimization of regular constraint satisfaction problems (rCSPs) using an auxiliary constraint satisfaction optimization problem (CSOP) that detects areas with a potentially high number of conflicts. The purpose of this approach is to remove conflicts by the combination of regular constraints with intersection and concatenation of their underlying deterministic finite automatons (DFAs). This, eventually, often allows to significantly speed-up the solution process of the original rCSP.

This paper describes a new approach to decompose constraint satisfaction problems (CSPs) using an auxiliary constraint satisfaction optimization problem (CSOP) that detects sub-CSPs which share only few common variables. The purpose of this approach is to find sub-CSPs which can be solved in parallel and combined to a complete solution of the original CSP. Therefore, our decomposition approach has two goals: 1. to evenly balance the workload distribution over all cores and solve the partial CSPs as fast as possible and 2. to minimize the number of shared variables to make the join process of the solutions as fast as possible.