  In this paper, we explore the automation of services' compositions. We focus
on the service selection problem. In the formulation that we consider, the
problem's inputs are constituted by a behavioral composition whose abstract
services must be bound to concrete ones. The objective is to find the binding
that optimizes the {\it utility} of the composition under some services level
agreements. We propose a complete solution. Firstly, we show that the service
selection problem can be mapped onto a Constraint Satisfaction Problem (CSP).
The benefit of this mapping is that the large know-how in the resolution of the
CSP can be used for the service selection problem. Among the existing
techniques for solving CSP, we consider the backtracking. Our second
contribution is to propose various backtracking-based algorithms for the
service selection problem. The proposed variants are inspired by existing
heuristics for the CSP. We analyze the runtime gain of our framework over an
intuitive resolution based on exhaustive search. Our last contribution is an
experimental evaluation in which we demonstrate that there is an effective gain
in using backtracking instead of some comparable approaches. The experiments
also show that our proposal can be used for finding in real time, optimal
solutions on small and medium services' compositions.
