Browse our site
About
People
Research Areas
Projects
Publications
Seminars
Future
Past
News
You are here:
Home
Seminars
Past
A Constraint Composition Approach for Numeric...
A Constraint Composition Approach for Numerical CSPs
Main information
By:
Jorge Cruz
(
CENTRIA
)
Date:
Wednesday, 23rd of June 2010, 14h00
Location:
FCT/UNL, Seminar Room (Ed. II)
Abstract
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.
Short-bio
Jorge Cruz is (since November 2003) an Assistant Professor of Computer Science in the Department of Computer Science of the FCT/UNL. He obtained his PhD in Computer Science at the UNL in 2003, with the dissertation "Constraint Reasoning for Differential Models" supervised by Prof. Pedro Barahona. Before that, he obtained an MSc in Computer Science at the UNL in 1995 and is a Computer Science Engineer since 1989. His primary research interests include: nonlinear constraints over continuous domains, uncertainty representation and reasoning with interval constraints, constraints for differential equations, probabilistic constraint reasoning.
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541
