CHAPTER 1. INTRODUCTION TO CONSTRAINT PROGRAMMING AND CHOCO
• constraints are non-directional, typically a constraint on (say) two variables X, Y can be used to
infer a constraint on X given a constraint on Y and vice versa,
• constraints are declarative, i.e. they specify what relationship must hold without specifying a
computational procedure to enforce that relationship,
• constraints are additive, i.e. the order of imposition of constraints does not matter, all that matters
at the end is that the conjunction of constraints is in effect,
• constraints are rarely independent, typically constraints in the constraint store share variables.
Constraints arise naturally in most areas of human endeavor. The three angles of a triangle sum to
180 degrees, the sum of the currents floating into a node must equal zero, the position of the scroller in
the window scrollbar must reflect the visible part of the underlying document, these are some examples
of constraints which appear in the real world. Thus, constraints are a natural medium for people to
express problems in many fields.
1.1.2 Constraint Programming
Constraint programming is the study of computational systems based on constraints. The idea of con-
straint programming is to solve problems by stating constraints (conditions, properties) which must be
satisfied by the solution.
Work in this area can be tracked back to research in Artificial Intelligence and Computer Graphics in
the sixties and seventies. Only in the last decade, however, has there emerged a growing realization that
these ideas provide the basis for a powerful approach to programming, modeling and problem solving
and that different efforts to exploit these ideas can be unified under a common conceptual and practical
framework, constraint programming.
If you know sudoku, then you know constraint programming. See
why here.
1.2 Modeling with Constraint programming
The formulation and the resolution of combinatorial problems are the two main goals of the constraint
programming domain. This is an essential way to solve many interesting industrial problems such as
scheduling, planning or design of timetables. The main interest of constraint programming is to propose
to the user to model a problem without being interested in the way the problem is solved.
1.2.1 The Constraint Satisfaction Problem
Constraint programming allows to solve combinatorial problems modeled by a Constraint Satisfaction
Problem (CSP). Formally, a CSP is defined by a triplet (X, D, C):
• Variables: X = {X
1
, X
2
, . . . , X
n
} is the set of variables of the problem.
• Domains: D is a function which associates to each variable X
i
its domain D(X
i
), i.e. the set
of possible values that can be assigned to X
i
. The domain of a variable is usually a finite set of
integers: D(X
i
) ⊂ Z (integer variable). But a domain can also be continuous (D(X
i
) ⊆ R for a
real variable) or made of discrete set values (D(X
i
) ⊆ P(Z) for a set variable).
• Constraints: C = {C
1
, C
2
, . . . , C
m
} is the set of constraints. A constraint C
j
is a relation defined
on a subset X
j
= {X
j
1
, X
j
2
, . . . , X
j
n
j
} ⊆ X of variables which restricts the possible tuples of values
(v
1
, . . . , v
n
j
) for these variables:
(v
1
, . . . , v
n
j
) ∈ C
j
∩ (D(X
j
1
) × D(X
j
2
) × · · · × D(X
j
n
j
)).
Such a relation can be defined explicitely (ex: (X
1
, X
2
) ∈ {(0, 1), (1, 0)}) or implicitely (ex: X
1
+
X
2
≤ 1).
CHOCO solver documentation
BSD licence 2012
-8/214- 22/2/2012
3星 · 超过75%的资源 需积分: 11 98 浏览量
更新于2024-07-28
收藏 1.91MB PDF 举报 
我的内容管理
展开
