Constraint Satisfaction Problems E-Book

Khaled Ghedira

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 211

Veröffentlichungsjahr: 2013

Beschreibung

A Constraint Satisfaction Problem (CSP) consists of a set of variables, a domain of values for each variable and a set of constraints. The objective is to assign a value for each variable such that all constraints are satisfied. CSPs continue to receive increased attention because of both their high complexity and their omnipresence in academic, industrial and even real-life problems. This is why they are the subject of intense research in both artificial intelligence and operations research. This book introduces the classic CSP and details several extensions/improvements of both formalisms and techniques in order to tackle a large variety of problems. Consistency, flexible, dynamic, distributed and learning aspects are discussed and illustrated using simple examples such as the n-queen problem.

Leseprobe

Contents

Preface

Introduction

Chapter 1. Foundations of CSP

1.1. Basic concepts

1.2. CSP framework

1.3. Bibliography

Chapter 2. Consistency Reinforcement Techniques

2.1. Basic notions

2.2. Arc consistency reinforcement algorithms

2.3. Bibliography

Chapter 3. CSP Solving Algorithms

3.1. Complete resolution methods

3.2. Experimental validation

3.3. Bibliography

Chapter 4. Search Heuristics

4.1. Organization of the search space

4.2. Ordering heuristics

4.3. Bibliography

Chapter 5. Learning Techniques

5.1. The “nogood” concept

5.2. Nogood-recording algorithm

5.3. The nogood-recording-forward-checking algorithm

5.4. The weak-commitment-nogood-recording algorithm

5.5. Bibliography

Chapter 6. Maximal Constraint Satisfaction Problems

6.1. Branch and bound algorithm

6.2. Partial Forward-Checking algorithm

6.3. Weak-commitment search

6.4. GENET method

6.5. Distributed simulated annealing

6.6. Distributed and guided genetic algorithm

6.7. Bibliography

Chapter 7. Constraint Satisfaction and Optimization Problems

7.1. Formalism

7.2. Resolution methods

7.3. Bibliography

Chapter 8. Distributed Constraint Satisfaction Problems

8.1. DisCSP framework

8.2. Distributed consistency reinforcement

8.3. Distributed resolution

8.4. Bibliography

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2013

The rights of Khaled Ghédira to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2012952416

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-460-6

Preface

This book is essentially based on a course offered for several years as part of the Master of Research in Sciences and Techniques for decision-making computing at the Higher Institute of Management, Tunis, and also of the Master of Research in Software Engineering and Decision-Support Systems at the National School of Computer Sciences, Tunis. It is also the reflection of research carried out in the SOIE (Stratégies d’Optimisation et Informatique intelligentE1) laboratory.

The book is intended for engineers, beginners or expert researchers, as well as teachers. For engineers it will make this field more accessible; for researchers it will outline basic notions and provide them with an extensive bibliography; and for teachers it will act as a course support.

First of all this book introduces the CSP formalism and its foundations in order to deal with Constraint Satisfaction Problems. Then it presents the main CSP based techniques which consist in either solving such problems by BT-like algorithms or speeding up this resolution by consistency enforcing and/or heuristics using and/or learning.

This book also reviews the extensions of CSP in terms of formalisms and techniques. A particular focus is given to the most known ones, namely Constraint Satisfaction and Optimization Problems (CSOP), Max-CSP and Distributed CSP.

The book is organized so as to be as most didactic possible. Indeed all the concepts and techniques are illustrated with simple examples. For more clarity, most of the algorithms are drawn on the example of the four-queens problem and the graph-coloring problem.

1 Optimization strategies and intelligent computing.

Introduction

The CSPs are ubiquitous in both the academic and industrial world and even in our everyday lives. The concept of constraint is a very old one. It has been used in many fields to represent various problems: textbook examples such as the n-queens game and the graph-coloring or cryptarithmetic problems, design issues such as VLSI, and industrial applications such as scene analysis and interpretation, planning, scheduling and allocation of resources.

Our aim is to express a problem as a set of variables and as a set of constraints on these variables. One of the most targeted objectives is the satisfaction of all the constraints (CSP). However, we will, in fact, see that many other objectives may be targeted. Many works have been carried out in this context, the main obstacle being combinatorics.

The first discipline to be interested in problems under constraints was indisputably operational research. Several models were developed; unfortunately, these were called into question owing to their difficulties in formalizing and solving real-life situations. In fact, operational research provides rigorous algorithmic techniques that are often unsuited to real-life problems: the difficulty of taking into account the specific characteristics of each problem, etc. New approaches usually placed under the banner of artificial intelligence (AI) helped to complete and improve these techniques, which gave impetus to the study of problems under constraints.

Among these approaches, we will focus in this book on the one that was developed around a simple and generic formalism: the CSP formalism. A CSP consists of a set of variables and a set of constraints. A finite and discreet domain of values is associated with each variable. A constraint is defined by a relation on a subset of the set of variables. We will go into more detail on this definition in Chapter 1. We can, however, on the basis of this definition, already target several objectives: the existence of a solution or not, producing a solution, producing all solutions, does a given variable’s value belong to a given solution or all solutions, etc.

On the basis of this formalism and given the NP-complete aspect of this type of problem, a wide range of techniques had been developed by the artificial intelligence community: backtrack and its variants, coherence reinforcement or filtering, backtrack-filtering hybridization, etc. These techniques are grouped under the terms of approaches, methods or CSP techniques.

The CSP solving methods are generally categorized into two families: the first family includes the complete or the so-called exact methods, which ensure completeness. These are dedicated to strict CSPs, namely complete satisfaction, i.e. satisfaction of all the constraints. The second family includes incomplete or approximate methods that sacrifice quality in favor of time complexity and that can then obtain a “good” solution in a “reasonable” time but cannot, in practice, ensure completeness and/or optimality. Instead, they are dedicated to maximum constraint satisfaction problems (max-CSPs) and constraint satisfaction and optimization problems (CSOP), which are extensions of CSP. Hence, we devote an entire chapter to the basic CSPs, a chapter to max-CSPs, and another to CSOPs, to focus on the most appropriate solving methods.

Learning mechanisms were also integrated into these techniques to intelligently solve CSPs by storing information deemed useful for pruning the search space. We then devote a chapter to describe these mechanisms and the underlying algorithms in more detail.

Despite the wealth of literature, the basic CSP approach unfortunately still presents some limitations in particular at the level of the following points:

– the formalism: this essentially focuses only on constraints and not on the expression of preferences;

– the resolution: neither the previous reasoning nor the previous solution is reused to take into account, and optimally deal with, the dynamic aspect; the case of the problem changes linked to unforeseen events or imprecise knowledge;

– the objectives: the objectives are primarily looking for one or several solutions, the user’s preferences for a particular solution not being possible.

Many studies have proposed extensions and brought enhancements to the basic CSP approach. They are particularly concerned with taking preferences, dynamicity and distribution into account.

As a result, other approaches such as distributed constraint satisfaction problems (DisCSPs) offer a new way to more efficiently apprehend the complexity of CSPs or the distributed aspect inherent to some real-life CSP applications. An extension is then proposed to give rise to the DisCSP formalism. This extension is discussed in more detail in Chapter 8.

As a result, other approaches such as distributed constraint satisfaction problems (DisCSPs) offer a new way to more efficiently apprehend the complexity of CSPs or the distributed aspect inherent to some real-life CSP applications. An extension is then proposed to give rise to the DisCSP formalism. This extension is discussed in more detail in Chapter 8.

This book is organized into eight chapters. The first chapter discusses the basic foundations of CSP formalism through a variety of definitions and examples of application. The second chapter is devoted to coherence reinforcement techniques. The third chapter describes the different methods for the complete resolution of the CSPs. The fourth chapter focuses on different heuristics and search approaches relating to CSPs to speed up the resolution and to better organize the route of the search space. In the fifth chapter, we draw up other approaches enhanced by storage and learning mechanisms.

Subsequently, we describe some extensions of CSPs. Thus, the sixth chapter discusses maximum constraint satisfaction problems (max-CSPs), while the seventh chapter discusses constraint satisfaction and optimization problems (CSOPs). Finally, we conclude the book with a chapter discussing an extension, based on the multi-agent approach, known as DisCSP.

Chapter 1

Foundations of CSP

Various real-life problems, considered as problems within artificial intelligence (AI) and operational research (OR), are solved via the constraint satisfaction problem (CSP) formalism that provides a tool for modeling and handling knowledge, and is simple, general, expressive and efficient in the sense that it is able to represent multiple and various types of knowledge. This formalism, introduced in the 1970s, is used in many domains, including task scheduling and the management and allocation of resources [GHÉ 06].

In this chapter, we begin by refining the definition of these CSPs as well as the associated basic notions. Then, we present the application areas of CSPs illustrated with examples prior to exposing the variants and extensions of the CSP formalism.