Guide to Constraint Programming

© Roman Barták, 1998

Contents

Prev
Up

Next

Over-Constrained Problems

Partial Constraint Satisfaction Problems

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.

A theory of Partial Constraint Satisfaction Problems (PCSPs) has been developed to weaken systems of constraints which have no solutions (over-constrained systems), or for which finding a solution would take too long. Instead of searching for a solution to a complex problem, it is considered searching for a simpler problem which we know we can solve.

The notion of a partial CSP is formalized by considering three components:

<(P,U), (PS,<=), (M,(N,S))>

where

A solution to a PCSP is a problem P' from the problem space and its solution, where the distance between P and P' is less than N. If the distance between P and P' is minimal, then this solution is optimal.

The problem space

A problem space PS is a partially-ordered set of CSPs where the order <= is defined as follows (sols(P) denotes the set of solutions to a CSP called P):
P1<=P2 iff sols(P1) is a superset of sols(P2)

Note that the ordering is over problems, but defined in terms of solutions.

The problem space for a PCSP must contain the original problem P, which can provide the maximal element in the order. The obvious problem space to explore when trying to weaken a problem is the collection of all problems Q such that Q<=P, but it may be useful to consider only some of these Qs, i.e., those problems which have been weakened in a particular way.

Weakening a problem

There are four ways to weaken a CSP:
  1. enlarging the domain of a variable (e.g., buy new shoes; see above example),
  2. enlarging the domain of a constraint (e.g., certain shoes do, after all, go with a certain shirt),
  3. removing a variable (e.g., decide not to wear shoes at all),
  4. removing a constraint (e.g., ignore clashes between shoes and shirts).

Freuder shows that all cases can be considered in terms of case 2 above, i.e.,

  1. the domain of the variable is defined by an unary constraint, so enlarge the domain of this constraint,
  2. ---
  3. remove all constraints on the variable (see 4),
  4. enlarge a constraint until it equals to the Cartesian product of domains of all involved variables.

The distance function

Different distance functions are possible, but the obvious one is derived from the partial order on the problems space.
  1. M(P,P') equals the number of solutions not shared by P and P' (when P'<=P then the distance function measures how many solutions have been added by the relaxation of P)
  2. M(P,P') equals the number of constrain values not shared by P and P'.

 

Example in PCSP

Consider the problem of choosing matching clothes from the introductory section to over-constrained problems.
S::{r,w}, F::{c,s}. T::{b,d,g} 
CST::{(r,g),(w,b),(w,d)}
CFT::{(s,d),(c,g)}
CSF::{(w,c)}.

We will only augment constraints with pairs whose elements are in the domain of variables concerned. Here are examples of such weakened problems (additional pairs are in bold):

CST::{(r,g),(w,b),(w,d)}

CFT::{(s,d),(c,g)}

CSF::{(w,c),(w,s)}

CST::{(r,g),(w,b),(w,d),(w,g)}

CFT::{(s,d),(c,g),(s,b)}

CSF::{(w,c),(w,s)}

CST::{(r,g),(w,b),(w,d),(r,b)}

CFT::{(s,d),(c,g),(c,d)}

CSF::{(w,c),(r,s)}

CST::{(r,g),(w,b),(w,d),(w,g),(r,b)}

CFT::{(s,d),(c,g),(s,b),(c,d)}

CSF::{(w,c),(w,s),(r,s)}

Assuming a simple distance function, namely that we prefer solutions involving the smallest total number of augmentations, we discover there are five equally good solutions, each with just one of the constraints receiving one extra pair of values. One solution is (S,F,T)=(w,s,d), the other four solutions are (w,c,b), (w,c,d), (w,c,g), (r,c,g) including some involving augmentations not listed above.

 

Contents

Prev
Up

Next
Designed and maintained by Roman Barták