Principles of Constraint Processing

Principles of Constraint Processing

Roman Barták (Charles University in Prague, Czech Republic)
Copyright: © 2008 |Pages: 44
DOI: 10.4018/978-1-59904-705-8.ch003
OnDemand PDF Download:


Solving combinatorial optimization problems such as planning, scheduling, design, or configuration is a non-trivial task being attacked by many solving techniques. Constraint satisfaction, that emerged from AI research and nowadays integrates techniques from areas such as operations research and discrete mathematics, provides a natural modeling framework for description of such problems supported by general solving technology. Though it is a mature area now, surprisingly many researchers outside the CSP community do not use the full potential of constraint satisfaction and frequently confuse constraint satisfaction and simple enumeration. This chapter gives an introduction to mainstream constraint satisfaction techniques available in existing constraint solvers and answers the question “How does constraint satisfaction work?”. The focus of the chapter is on techniques of constraint propagation, depth-first search, and their integration. It explains backtracking, its drawbacks, and how to remove these drawbacks by methods such as backjumping and backmarking. Then, the focus is on consistency techniques; it explains methods such as arc and path consistency and introduces consistencies of higher level. It also presents how consistency techniques are integrated with depth-first search algorithms in a look-ahead concept and what value and variable ordering heuristics are available there. Finally, techniques for optimization with constraints are presented.

Complete Chapter List

Search this Book:
Table of Contents
Dimitris Vrakas, Ioannis Vlahavas
Chapter 1
Johan Baltié, Eric Bensana, Patrick Fabiani, Jean-Loup Farges, Stéphane Millet, Philippe Morignot, Bruno Patin, Gerald Petitjean, Gauthier Pitois, Jean-Clair Poncet
This chapter deals with the issues associated with the autonomy of vehicle fleets, as well as some of the dimensions provided by an Artificial... Sample PDF
Multi-Vehicle Missions: Architecture and Algorithms for Distributed Online Planning
Chapter 2
Antonio Garrido, Eva Onaindia
The recent advances in AI automated planning algorithms have allowed to tackle with more realistic problems that involve complex features such as... Sample PDF
Extending Classical Planning for Time: Research Trends in Optimal and Suboptimal Temporal Planning
Chapter 3
Roman Barták
Solving combinatorial optimization problems such as planning, scheduling, design, or configuration is a non-trivial task being attacked by many... Sample PDF
Principles of Constraint Processing
Chapter 4
Alexander Mehler
We describe a simulation model of language evolution which integrates synergetic linguistics with multiagent modelling. On the one hand, this... Sample PDF
Stratified Constraint Satisfaction Networks in Synergetic Multi-Agent Simulations of Language Evolution
Chapter 5
Zhao Lu, Jing Sun
As an innovative sparse kernel modeling method, support vector regression (SVR) has been regarded as the state-of-the-art technique for regression... Sample PDF
Soft-constrained Linear Programming Support Vector Regression for Nonlinear Black-box Systems Identification
Chapter 6
Ioannis Partalas, Dimitris Vrakas, Ioannis Vlahavas
This article presents a detailed survey on Artificial Intelligent approaches, that combine Reinforcement Learning and Automated Planning. There is a... Sample PDF
Reinforcement Learning and Automated Planning: A Survey
Chapter 7
Stasinos Konstantopoulos, Rui Camacho, Nuno A. Fonseca, Vítor Santos Costa
This chapter introduces Inductive Logic Programming (ILP) from the perspective of search algorithms in Computer Science. It first briefly considers... Sample PDF
Induction as a Search Procedure
Chapter 8
Kiruthika Ramanathan, Sheng Uei Guan
In this chapter we present a recursive approach to unsupervised learning. The algorithm proposed, while similar to ensemble clustering, does not... Sample PDF
Single- and Multi-order Neurons for recursive unsupervised learning
Chapter 9
Malcolm J. Beynon
This chapter investigates the effectiveness of a number of objective functions used in conjunction with a novel technique to optimise the... Sample PDF
Optimising Object Classification: Uncertain Reasoning-Based Analysis Using CaRBS Systematic Research Algorithms
Chapter 10
P. Vasant, N. Barsoum, C. Kahraman, G.M Dimirovski
This chapter proposes a new method to obtain optimal solution using satisfactory approach in uncertain environment. The optimal solution is obtained... Sample PDF
Application of Fuzzy Optimization in Forecasting and Planning of Construction Industry
Chapter 11
Malcolm J. Beynon
This chapter investigates the modelling of the ability to improve the rank position of an alternative in relation to those of its competitors.... Sample PDF
Rank Improvement Optimization Using PROMETHEE and Trigonometric Differential Evolution
Chapter 12
Iker Gondra
Genetic Algorithms (GA), which are based on the idea of optimizing by simulating the natural processes of evolution, have proven successful in... Sample PDF
Parallelizing Genetic Algorithms: A Case Study
Chapter 13
Daniel Rivero, Miguel Varela, Javier Pereira
A technique is described in this chapter that makes it possible to extract the knowledge held by previously trained artificial neural networks. This... Sample PDF
Using Genetic Programming to Extract Knowledge from Artificial Neural Networks
About the Contributors