Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2003 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Essentials of Constraint Programming

verfasst von: Thom Frühwirth, Slim Abdennadher

Verlag: Springer Berlin Heidelberg

Buchreihe : Cognitive Technologies

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and specify problems with uncertain, incomplete information and to solve combi­ natorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis. This book is a short, concise, and complete presentation of constraint programming and reasoning, covering theoretical foundations, algorithms, implementations, examples, and applications. It is based on more than a decade of experience in teaching and research about this subject. This book is intended primarily for graduate students, researchers, and practitioners in diverse areas of computer science and related fields, including programming languages, computational logic, symbolic computation, and ar­ tificial intelligence. The book is complemented by a web-page with teaching material, software, links, and more. We take the reader on a step-by-step journey through the world of constraint-based programming and constraint reasoning. Feel free to join in ... Acknowledgements Thorn thanks his wife Andrea and his daughter Anna - for everything. He dedicates his contribution to the book to the memory of his mother, Grete. Slim thanks his wife N abila and his daughters Shirine and Amira for their ongoing support and patience.

Inhaltsverzeichnis

Frontmatter

Introduction

1. Introduction
Abstract
The idea of constraint-based programming is to solve problems by simply stating constraints (conditions, properties) which must be satisfied by a solution of the problem. For example, consider a bicycle number lock. We forgot the first digit, but remember some constraints about it: The digit was an odd number, greater than 1, and not a prime number. Combining the pieces of partial information expressed by these constraints (digit, greater than 1, odd, not prime) we are able to derive that the digit we are looking for is “9”.
Thom Frühwirth, Slim Abdennadher

Constraint Programming

Frontmatter
2. Algorithm = Logic + Control
Abstract
With this statement Robert Kowalski [35] stressed the difference between what (logic) and how (control) in implementing an algorithm in a computer program. A program consists of a logical component, which specifies the knowledge of the problem, and a control component, which determines how this knowledge is used in order to solve a problem.
Thom Frühwirth, Slim Abdennadher
3. Preliminaries of Syntax and Semantics
Abstract
In general, the term logic-based programming languages refers to computer languages that make (a subset of) a logic executable. There are languages based on non-classical logics like higher order logic and modal or temporal logic, but, like in this book, logic programming is mostly used as a synonym for computing in classical first-order predicate logic. A brief review of first-order logic and its notation as it forms the basis of this book can be found in Appendix A.
Thom Frühwirth, Slim Abdennadher
4. Logic Programming
Abstract
The first and most popular logic programming (LP) language is Prolog. It is still the basis of most constraint programming languages. Prolog’s origins can be traced back to early work in automated theorem proving and planning (Fig. 4.1). Prolog was developed in the early 1970’s, first independently and then jointly by Alain Colmerauer (Marseille) and Robert Kowalski (Edinburgh). Then David Warren (London) defined the Warren Abstract Machine (WAM) that lead to an efficient implementation of Prolog. The ideas behind the WAM strongly influenced the implementation of more recent languages like Java.
Thom Frühwirth, Slim Abdennadher
5. Constraint Logic Programming
Abstract
Constraint logic programming (CLP) was developed in the mid-1980’s as a natural combination of two declarative paradigms: constraint solving and logic programming (Fig. 5.1). This makes constraint logic programs more expressive, flexible, and in general more efficient than logic programs.
Thom Frühwirth, Slim Abdennadher
6. Concurrent Constraint Logic Programming
Abstract
At the end of the 1980’s, concurrent constraint logic programming (CCLP) integrated ideas from concurrent LP [52] and CLP (Fig. 6.1).
Thom Frühwirth, Slim Abdennadher
7. Constraint Handling Rules
Abstract
One lesson learned from applications is that constraints are often heterogeneous and application specific. In the beginning of constraint programming, constraint solving was “hard-wired” in a built-in constraint solver written in a low-level language. While efficient, this approach makes it hard to modify a solver or build a solver over a new domain, let alone reason about and analyze it. As the behavior of the solver can neither be inspected by the user nor explained by the computer, debugging of constraint-based programs is hard.
Thom Frühwirth, Slim Abdennadher

Constraint Systems

Frontmatter
8. Constraint Systems and Constraint Solvers
Abstract
In this part of the book, we introduce the most common constraint systems. They are the result of taking a data type together with its operations and interpreting the resulting expressions as constraints. These constraint systems use the universal data types of numbers (integers or reals) to represent scalar data or terms to represent structured data.
Thom Frühwirth, Slim Abdennadher
9. Boolean Algebra B
Abstract
We start with the Boolean constraint system that admits a simple algorithm to solve constraints [41].
Thom Frühwirth, Slim Abdennadher
10. Rational Trees RT
Abstract
We have already introduced the constraint system E dealing with Herbrand terms (or: first-order terms, finite trees) and the syntactic equality constraint. Here, we consider an important variation of E.
Thom Frühwirth, Slim Abdennadher
11. Linear Polynomial Equations ℜ
Abstract
One motivation for introducing constraints in the LP language Prolog was the non-declarative nature of the built-in predicates for arithmetic computations. Therefore, the first CLP languages included constraint solvers for linear polynomial equations and inequations over the real numbers (CLP(ℜ) [33]) or rational numbers (Prolog-III [15], CHIP [20]).
Thom Frühwirth, Slim Abdennadher
12. Finite Domains FD
Abstract
In this constraint system, variables are constrained to take their value from a given, finite set. Choosing integers for values allows for arithmetic expressions as constraints. Constraint propagation proceeds by removing values from the sets of possible values that do not participate in any (partial) solution.
Thom Frühwirth, Slim Abdennadher
13. Non-linear Equations I
Abstract
A simple way to tackle nonlinear polynomial equations is to replace nonlinear expressions by variables such that as many equations as possible become linear (as in CLP(ℛ) [33]). As with the introduction of slack variables, solving linear equations alone does not yield a complete method.
Thom Frühwirth, Slim Abdennadher

Applications

Frontmatter
14. Market Overview
Abstract
This part of the book presents uses of constraint techniques in three classes of application: timetabling, optimal placement, and reasoning with imprecise and incomplete information. The three applications involved the authors of this book and were implemented in Prolog and CHR at the Ludwig-Maximilians-Universität of Munich (LMU) and at the European Computer Industry Research Center (ECRC) in Munich, Germany.
Thom Frühwirth, Slim Abdennadher
15. Optimal Sender Placement for Wireless Communication
Abstract
Mobile communications comes to company sites. Be it as digital cordless telecommunication (DECT) or as wireless local area networks (W-LAN). No cabling is required, but access points, i.e., small, local radio transmitters (senders) have to be installed. They should cover the installation site. Planning their locations is difficult, since the specifics of radio wave propagation have to be taken into account.
Thom Frühwirth, Slim Abdennadher
16. The Munich Rent Advisor
Abstract
The Munich Rent Advisor (MRA) [24], developed by the European Computer Industry Research Center (ECRC) and the Ludwig-Maximilians-Universität of Munich (LMU), is the electronic version of the “Mietspiegel” (MS) for Munich. MSs are published regularly by German cities. They are basically a written description of an expert system that allows to estimate the maximum fair rent for a flat. These estimates are legally binding.
Thom Frühwirth, Slim Abdennadher
17. University Course Timetabling
Abstract
University course timetabling problems are combinatorial problems, which consist in scheduling a set of courses within a given number of rooms and time periods. Solving a real-world timetabling problem manually often requires a significant amount of time, sometimes several days or even weeks. Therefore, a lot of research has been invested in order to provide automated support for human timetablers. Contributions come from the fields of operations research (e.g., graph coloring, network flow techniques) and artificial intelligence (e.g., simulated annealing, tabu search, genetic algorithms, constraint satisfaction) [50].
Thom Frühwirth, Slim Abdennadher
Backmatter
Metadaten
Titel
Essentials of Constraint Programming
verfasst von
Thom Frühwirth
Slim Abdennadher
Copyright-Jahr
2003
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-05138-2
Print ISBN
978-3-642-08712-7
DOI
https://doi.org/10.1007/978-3-662-05138-2