Principles of Constraint Processing

Principles of Constraint Processing

Roman Barták
Copyright: © 2008 |Pages: 44
ISBN13: 9781599047058|ISBN10: 1599047055|EISBN13: 9781599047072
DOI: 10.4018/978-1-59904-705-8.ch003
Cite Chapter Cite Chapter

MLA

Barták, Roman. "Principles of Constraint Processing." Artificial Intelligence for Advanced Problem Solving Techniques, edited by Ioannis Vlahavas and Dimitris Vrakas, IGI Global, 2008, pp. 63-106. https://doi.org/10.4018/978-1-59904-705-8.ch003

APA

Barták, R. (2008). Principles of Constraint Processing. In I. Vlahavas & D. Vrakas (Eds.), Artificial Intelligence for Advanced Problem Solving Techniques (pp. 63-106). IGI Global. https://doi.org/10.4018/978-1-59904-705-8.ch003

Chicago

Barták, Roman. "Principles of Constraint Processing." In Artificial Intelligence for Advanced Problem Solving Techniques, edited by Ioannis Vlahavas and Dimitris Vrakas, 63-106. Hershey, PA: IGI Global, 2008. https://doi.org/10.4018/978-1-59904-705-8.ch003

Export Reference

Mendeley
Favorite

Abstract

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.