Web service evaluation is a phase in Web service selection where discovered Web services are evaluated with respect to user requests, which means that the non functional properties (NFPs) offered by Web services are compared with the non functional properties requested by users. NFPs cover Quality of Service (QoS) aspects, but also other business-related properties, such as pricing, and properties not directly related to the service functionalities. The fact that users and providers can express their NFPs in very flexible ways makes the management of NFP a very complex task. The Policy Centered Meta-model (PCM) is a semantic-oriented model for sophisticated NFP descriptions that can be exploited to support Web service evaluation. In this paper, we propose a novel approach based on Hierarchical Constraint Logic Programming to handle PCM-based NFP descriptions along the Web service evaluation phase.