Programando con restricciones

Abstract

Muchas veces nos encontramos con problemas de combinatoria difíciles de resolver. Estos problemas aparecen comúnmente no solo en el ámbito académico (por ejemplo en los dominios de la inteligencia artificial, bases de datos, investigación operativa, etc.), sino también en el ámbito de nuestra vida cotidiana (por ejemplo en las áreas de planificación, programación de actividades, asignación de recursos, etc.). Programando con restricciones es posible en muchos casos encontrar, de manera altamente eficiente, soluciones a muchos de estos problemas manejando su complejidad de manera simple e, incluso, elegante. Este artículo es una introducción a la programación con restricciones. Describe de manera sencilla una buena parte de las técnicas y conceptos fundamentales que la sustentan a través de ejemplos abordados de manera clara y concisa. Finaliza con un ejemplo práctico y concreto, mostrando la resolución de un problema clásico usando C++.

Hard combinatorial problems are ubiquitous in our society. They arise in many application domains (e.g., artificial intelligence, data bases, operations research, etc.) and diverse real life settings (e.g., scheduling, timetabling, resource allocation, etc.). Constraint Programming is a technique that manages the complexity of these problems in a simple and even elegant manner. It usually allows us to highly efficiently find solutions to many hard combinatorial problems. This article is an introduction to Constraint Programming. It describes many of its fundamental concepts and techniques through clear and concise examples. It finishes with a practical example, solving a classical problem, using C++.