Article ID: | iaor19952190 |
Country: | Germany |
Volume: | 16 |
Issue: | 3 |
Start Page Number: | 193 |
End Page Number: | 202 |
Publication Date: | Apr 1994 |
Journal: | OR Spektrum |
Authors: | Pesch E., Drexl A., Kolen A. |
Keywords: | constraint handling languages |
Constraint logic programming is a relatively new area of research in Artificial Intelligence that holds an immense promise for Operations Researchers. The idea is to provide a logic programming language that accepts a series of logic statements and (arithmetic) constraints and then is capable to generate a feasible solution to the underlying constraint satisfaction problem. Informally, a constraint satisfaction problem is posed as follows. Given a set of variables and a set of constraints, each specifying a relation on a particular subset of the variables, find the relation on the set of all variables which satisfies all the given constraints. The required solution relation is a subset of the cartesian product of the variable domains. Traditionally, backtrack search is used to solve constraint satisfaction problems. In order to overcome the inefficiency of a simple backtrack search consistency checks among variable value assignments were incorporated introducing new knowledge by constraint based reasoning to reduce the search space and discover failures earlier. Most common are node- and arc-consistency checks the only ones which are also implicitly introduced in recent constraint based logic programming languages. CHARME is such a programming language, a general modeling language and problem solver that allows to find model-based implementations and provides guided backtrack search which can lead to efficient and competitive search strategies for certain problems in combinatorial optimization.