*Guide to Constraint
Programming*
*©
Roman Barták, 1998*
**Up**

In many real-life applications,
there does not exist solution, i.e., valuation of variables that
satisfies all the constraints. Such systems of constraints are called
**over-constrained systems**, opposite to **under-constrained
systems** of constraints that have many solutions satisfying all
the constraints.

Example:Consider the problem of choosing matching clothes (shirt, shoes and trousers) that can be easily modeled using three finite domain variables with a number of binary constraints between them:shirtsS::{r,w} for red and white respectively,

shoes(footwear) F::{c,s} for cordovans and sneakers

trousersT::{b,d,g} for blue, denim, and greymatching constraints (C

_{SF}denotes matching pairs of shirts and shoes):C

_{ST}::{(r,g),(w,b),(w,d)}

C_{FT}::{(s,d),(c,g)}

C_{SF}::{(w,c)}.Visibly, this problem is over-constrained; it has no solutions. Therefore we need to consider some way of relaxing or weakening the problem until solutions can be found.

The traditional algorithms for constraint satisfaction are not able solve over-constrained systems although the stochastic algorithms can maximize the number of satisfied constraints. Therefore, some alternative approaches have been proposed to solve over-constrained systems or to generalize the notion of constraint respectively.

The constraints in classical constraint satisfaction problems are crisp, i.e., they allow a tuple (of values of involved variables) or not. Alternative approaches to constraint satisfaction were proposed to enable non-crisp constraints, probabilities or weights respectively.

The Partial Constraint Satisfaction (PCSP) scheme of Freuder and Wallace is an interesting extension of CSP, which allows the relaxation and optimization of problems via weakening the original CSP.

Constraint hierarchies have been proposed to describe over-constrained systems of constraints by specifying constraints with hierarchical preferences, i.e., hard and soft constraints. While the hard (required) constraints must hold, the soft (preferential) constraints should be satisfied as much as possible depending on the criterion used.

Overview of algorithms for solving constraint hierarchies (refining algorithm - DeltaStar; local propagation - DeltaBlue, SkyBlue, Indigo, Houria; others - IHCS, projection).

To model features of various CSP systems, the general frameworks have been proposed. Among them the compositional theory for reasoning about over-constrained systems and the semiring-based constrained satisfaction are the most popular.

**Up**
*Designed and
maintained by **Roman
Barták*