Detail

A Constraint Composition Approach for Numerical CSPs

Traditional algorithms for enforcing hull-consistency on numerical CSPs rely on the decomposition of the original constraints into a set of primitive constraints for which the inverse with respect to each variable can be easily computed. The decomposition of the constraints has the main disadvantage of worsening the dependency problem due to the addition of new variables and consequent loss of the dependency between values of related variables. This talk presents a new approach where the main idea is exactly the opposite, i.e., to try to compose equality constraints reducing the dependency problem. Such composition may be effective if hull-consistency can still be enforced on the resulting composite constraint. In fact, recent research shows that hull-consistency enforcement does not require the decomposition into primitive constraints as long as the original constraint function is monotonic with respect to each variable. The proposed algorithm is able to make constraint compositions dynamically during the solving process, according to the monotonicity properties of each box, and to use the composite constraints to prune the variable domains. Additionally, the splitting strategy is tuned to obtain sub-boxes with the required monotonicity conditions. As such, both branching and pruning are dynamically adapted according to the monotonic properties identified at each region of the search space. The advantages and limitations of the proposed approach will be discussed on a set of illustrative examples.