The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
Principles of Constraint Processing
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.
Related Content
|
Kamel Mouloudj, Vu Lan Oanh LE, Achouak Bouarar, Ahmed Chemseddine Bouarar, Dachel Martínez Asanza, Mayuri Srivastava.
© 2024.
20 pages.
|
|
José Eduardo Aleixo, José Luís Reis, Sandrina Francisca Teixeira, Ana Pinto de Lima.
© 2024.
52 pages.
|
|
Jorge Figueiredo, Isabel Oliveira, Sérgio Silva, Margarida Pocinho, António Cardoso, Manuel Pereira.
© 2024.
24 pages.
|
|
Fatih Pinarbasi.
© 2024.
20 pages.
|
|
Stavros Kaperonis.
© 2024.
25 pages.
|
|
Thomas Rui Mendes, Ana Cristina Antunes.
© 2024.
24 pages.
|
|
Nuno Geada.
© 2024.
12 pages.
|
|
|