I am specially indebted to Pedro Barahona who supported me, not only as the supervisor of this work, but also in all my academic formation. He is an excellent supervisor which I greatly recommend to any one intending to start a PhD in constraint programming. He has the rare ability of being open minded with respect to new ideas and contribute diligently to their success. Despite his overbooked schedule, he was always present whenever needed. He is a good friend and is a pleasure to work with him.

I am very grateful to Frédéric Benhamou and all his research team for their good hospitality and their crucial support in the early phases of this work. Thanks to Frédéric Goualard and Laurent Granvilliers for their friendship and all our valuable discussions.

Special thanks to Luís Moniz Pereira, for his careful reading and comments on the introduction and conclusions of this work, but above all, for his excellent work in promoting Artificial Intelligence which attracted me in the first place for taking a computer science degree.

My acknowledgements to the Computer Science Department for having conceded me three sabbatical years which were extremely important for the progress of this work.

Many thanks to my colleagues in the Computer Science Department and CENTRIA for their companionship, trust and concern. In particular, I am grateful to the constraint research group for creating a stimulating working environment. Thanks to my good friends Anabela and Cecília for their sincere care and help, promptly sharing with me their own resources whenever I needed.

Thanks to all my family for their love and precious help in handling so many practical problems which allowed me to fully concentrate on my work. I am particularly grateful to my parents for their continuous support and belief on my own choices.

Finally, I am deeply grateful to my wife Teresa, who, from the beginning of this work, has always been by my side, giving me confidence and encouragement in difficult moments and a good reason to keep on searching for success. I can never thank her enough for all the days, weekends and holidays that she has sacrificed for helping me.