ISSN:
1436-6304
Keywords:
CSP
;
Logik-orientierte Programmiersprachen
;
Constraint Propagation
;
Backtracking
;
Arc-Konsistenz
;
Path-Konsistenz
;
CSP
;
logic programming
;
constraint propagation
;
Backtracking
;
Arc-Consistency
;
Path-Consistency
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Abstract Constraint logic programming is a relatively new area of research in Artficial 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 implicity introduced in recent constraint based logic programming languages. CHARME [7, 8] 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.
Notes:
Zusammenfassung Constraint-basierte Logikprogrammierung ist ein neues und auch für das Operations Research vielversprechendes Gebiet der Künstlichen Intelligenz. Eine logikorientierte Programmiersprache generiert zulässige Lösungen eines Constraint-Satisfaction-Problems, dessen Beschreibung auf einer Menge logischer Aussagen und einer Anzahl von Nebenbedingungen basiert. Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Variablen sowie einer Menge von Nebenbedingungen über diesen Variablen. Gesucht ist eine zulässige Wertezuweisung der Variablen, als Teilmenge des cartesischen Produkts der Variablenwertebereiche, die allen Nebenbedingungen genügt. Traditionelle Lösungsverfahren basieren auf einer Suche mittels Backtracking. Konsistenzprüfungen von Variablenwertzuweisungen können dabei die Effizienz des Suchverfahrens wesentlich erhöhen, da neues, implizit vorhandenes Wissen über den Suchraum aus der Menge der Nebenbedingungen erschlossen und genutzt wird. Constraint-basierte Logiksprachen reduzieren während der Lösungssuche die Variablenwertebereiche automatisch, so daß nur noch node- und arc-konsistente Relationen betrachtet werden. CHARME [7, 8] ist eine derartige Programmiersprache, in der modellnahe Implementierungen parametergesteuerte Suchstrategien zulassen, die u. U. Probleme der Kombinatorischen Optimierung effizient lösbar machen.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01720708
Permalink
