Constraint Networks

Targeting Simplicity for Techniques and Algorithms

Christophe Lecoutre

• Publisher: Wiley-ISTE
• Year: 2013
• Print ISBN: 9781848211063
• eBook ISBN: 9781118617915
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Engineering
• Index: Computer Science

A major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP). With this aim in mind, this book provides an accessible synthesis of the author's research and work in this area, divided into four main topics: representation, inference, search, and learning. The results obtained and reproduced in this book have a wide applicability, regardless of the nature of the problem to be solved or the type of constraints involved, making it an extremely user-friendly resource for those involved in this field.

Chapter 1

Constraint Networks

This chapter introduces the formalism of constraint networks, which can abstractly represent many academic and real-world problems. Section 1.1 introduces variables and constraints, which are the main ingredients of constraint networks. This introduction includes different representations of constraints as well as the vital concept of constraint support. In section 1.2, we formally define constraint networks. Moreover, we present the (hyper)graphs that can be associated with any constraint network, and introduce instantiations. Section 1.3 provides some illustrative examples of problems that can be easily represented by means of constraint networks. For simplicity and entertainment, these examples are based on logic puzzles. Section 1.4 is concerned with partial orders in constraint networks, decisions and general properties of values and variables. Finally, section 1.5 introduces some data structures that can be employed to represent constraint networks in computer programs.

1.1. Variables and constraints

Here we will define variables and constraints, which are the main ingredients of constraint networks. They constitute the surface part of a problem representation, whereas domains and relations constitute the underlying part. In object-oriented design, we would certainly build up a class for variables and another for constraints, and represent all relevant information about variables and constraints in terms of attributes (maybe introducing additional classes) for these objects: identifier, domain, scope, relation, etc.

DEFINITION 1.1.– [Variable] A variable, which is a component of an abstract system, is an object that has a name and is able to take different values. In our context, a variable (whose name is) x must be given a value from a set, which is called the current domain of x and is denoted by dom(x). The domain of a variable x may evolve over time, but it is always included in a set called the initial domain of x.¹ This initial domain, which is denoted by dom^init(x), represents the full universe of the variable x.

A continuous variable has an infinite initial domain, usually defined in terms of real intervals. Continuous variables are outside the scope of this book, which only considers discrete variables. A discrete variable is a variable whose initial domain contains a finite number of values.

We use letters x, y, z (and when necessary u, v, w), possibly subscripted or primed, to denote variables. Without any loss of generality, our variables can be assumed to have integer values in their domains when necessary. Quite often, letters a, b, c, possibly subscripted or primed, will be used to denote values. For example, x and y such that dom^init(x) = {a,b} and dom^init(y) = {1,2,…,100} are two discrete variables whose initial domains contain 2 and 100 values, respectively.

Domains are dynamic sets, i.e. they may change over time. A variable is said to be fixed when its current domain only contains one value, and unfixed otherwise. A variable can be fixed either explicitly or implicitly (incidentally). When a variable x is explicitly given a value a from its current domain dom(x) during the progression of a scenario or an algorithm, every other value b ≠ a is considered to be removed from dom(x). In this case we say that the variable x is instantiated; otherwise, we say that x is uninstantiated. We also say that the variable x is assigned (the value a) or that the value a is assigned to x. Assigning a value to a variable is called a variable assignment. Implicitly fixed variables occur when deduction (inference) mechanisms are used. For example, consider the equality x = y between two variables x and y whose (common) current domain is {1, 2}. If the variable x is assigned the value 1, by reasoning from the equality we can deduce that y must also be equal to 1, i.e. the value 2 can be removed from dom(y) by deduction. The two variables are then fixed, the first one explicitly and the second one implicitly. However, only the first variable is considered to be instantiated (or assigned).

A value a is said to be valid for a variable x iff a ∈ dom(x). Because of changes in dom(x), a value that is valid for x at time t may be invalid at another time t′. To keep track of those changes, it can be helpful to use a superscript t to denote the time at which we refer to a domain: dom^t(x) is the domain of x at tim...

Table of contents

• Cover
• Title Page
• Copyright
• Acknowledgements
• Notation
• Main Acronyms
• List of Algorithms
• Introduction
• Chapter 1: Constraint Networks
• Chapter 2: Random and Structured Networks
• PART ONE: Inference
• PART TWO: Search
• Appendix A: Mathematical Background
• Appendix B: XML Representation of Constraint Networks
• Bibliography
• Back Cover
• Index