Constraint Programming, Research Paper Example

Abstract

Constraint satisfaction is arguably the most relevant and practical facet of programming in operational research. As a branch of constraint programming, it has received unprecedented application in airline, shipping and freight industries particularly in scheduling and rostering. The formulation and research into algorithms for constraint satisfaction problems solution has received a lot of interest among researchers owing to the robustness of solutions that can be harnessed. Beginning with an introduction on constraint programming, the paper defines and isolates a typical constraint satisfaction problem. It then delves into the topic of constraint satisfaction as a branch of constraint programming, the modes of algorithm formulation to solve constraint satisfaction problems and its applicability in real life scenarios.

Constraint programming is a programming paradigm in which constraints are used to state or define the relationships between variables. Constraint programming uses various types of variables such as variables emergent from the solution of simplex algorithms, variables that satisfy a constraint among others (ETAPS, 2003). By definition, a constraint refers to a relation in logic, of several variables (which are unknown) for which, each assumes a value in a specific domain. It restricts the values that can be assigned to a specific variable, thereby providing partial details on the given variable. The programming process in constraint programming entails building or coming up with requirements, also referred to as constraints, and then by use of constraint solvers, coming up with a solution to the previously specified requirements. Constraint programming is divided into two major branches, Constraint Satisfaction and Constraint Solving (Bartak, 1998).

Figure 1: Relationships between constraints and variables

(Source: http://www.doc.ic.ac.uk/~sgc/teaching/pre2012/v231/lecture15.html)

This paradigm of programming has received widespread applicability especially in the areas of scheduling and planning. In a constraint programming perspective, this can be viewed as constraint satisfaction problems, which is squarely within the constraint satisfaction branch of constraint programming. A typical definition of a constraint satisfaction problem can be expressed as follows; a situation that provides a definite set of variables and values that can be assigned to the variables. In addition, there is a set of constraints, the solution is to find values from the given set to be assigned to the variables and satisfy the constraints (Brailsford, Pott & Smith, 1998).

Problems in constraint satisfaction are combinatorial in nature, and thus existence of an effective algorithm is unlikely. To find a solution to such problems, the algorithms are enumerative, and their time requirement is exponential. The manner by which these algorithms come up with a solution is either, Consistency driven, Backtracking or Generate and Test (Constraint Satisfaction Problems, n.d.). Based on the information available in the constraints, algorithms that are consistency based minimize the solution-search space at the very initial levels. An example is the Arc consistency algorithm which when described in the simplest form means, if all constraints in a problem affect only 2 variables (binary), a constraint graph can be used to represent the constraints and variables. On the graph, the variables are represented by nodes, and on the condition that there is a constraint between two variables, there is an edge joining the two nodes that represent the variables (Brailsford, Pott & Smith, 1998).

In a backtracking algorithm, the variables in the problem are ordered starting with the ones that have a smaller range or are highly constrained. This ordering fashion greatly increases the efficiency of the algorithm. By checking that constraints are satisfied at the earliest possible stage, it assigns values to variables for constraints that involve bound variables at these early stages. This mode employs chronological backtracking (involves unbinding variables inversely to the order they were bound) and dependency directed backtracking (similar to chronological backtracking but identifies and corrects failures resulting from chronological backtracking).

Generate and test algorithms are the simplest but are intolerably slow. They entail generating of all possible combinations of variable assignments and testing them to see if they fulfill the constraints. These algorithms generally make use of nested loops where testing of the constraints condition is done in the innermost loop (Constraint Satisfaction Problems, n.d.).

Scheduling, timetabling, and rostering are practical examples of constraint satisfaction problem solving. In scheduling, an example is where scheduling jobs are to be done by machines given that a machine can only handle a job at a time, and different jobs have different priorities. In timetabling, an example involves creating an exam timetable where different exams have to be done in different periods, by different students, in different rooms of different room sizes and many other constraints around the problem. Crewe rostering is an example application in rail and air transport industries (Brailsford, Pott & Smith, 1998).

References

Bartak, R., (1998). Constraint Programming. On-Line Guide to Constraint Programming. Retrieved from http://ktiml.mff.cuni.cz/~bartak/constraints/

Brailsford, S.C., (1998). Constraint Satisfaction Problems: Algorithms and Applications. University of Southampton. Leeds: UK.

ETAPS, (2003). Foundations of Constraint Programming. Warshaw, Poland. Constraint Satisfaction Problems. n.d. Retrieved from http://www.cis.temple.edu/~giorgio/cis587/readings/constraints.html