History of Constraint Programming

Abstract Constraint programming is a technology for solving combinatorial optimization problems. It appeared in the 1960s in systems such as Sketchpad, and core ideas such as arc and path consistency techniques were proposed and developed in the 1970s. The real landmark of constraint programming was in the 1980s when researchers realized that unification in logic programming is a special form of constraint solving, and constraint logic programming appeared. Since that time, many solving techniques and approaches were studied, but the core idea of constraint programming remains the same—it is a technology based on integration of search techniques with special inference techniques exploiting the structure of constraints in the problem. Constraint programming is successful in many application areas. Scheduling is probably the most prominent one, but constraints are also applied when solving problems in planning, configuration, vehicle routing, networking, bioinformatics, and so on. This article describes how constraint programming evolved since its beginnings to the current state.