Foundations of Constraint Processing

Foundations of Constraint Processing

• Foundations of Constraint Processing

• CSCE421/821, Fall 2005:

• www.cse.unl.edu/~choueiry/F05-421-821/

• Berthe Y. Choueiry (Shu-we-ri)

• Avery Hall, Room 123B

• [e-mail]

• Tel: [phone]

• Context

• Finite domains
• Binary constraints

• Required reading

• Chapter 6 of Tsang’s book (web accessible)

• Recommended reading

• Dual viewpoint heuristics for binary Constraint Satisfaction Problems [Geelen, ECAI 92]
• In my experience the most powerful, but also the most costly (require lots of constraint checks)

Motivation for ordering heuristics

• In BT, there are fewer backtracks under some orderings than others

• In look-ahead, failure can be detected earlier under some orderings than others

• When searching for one solution, value ordering may speed up search as branches that have a better chance to reach a solution are explored first

• Dynamic ordering often reduce (remove?) the need for intelligent backtracking (personal experience)

Value ordering: get quickly to a solution

• Min-conflict heuristic: orders values according to the conflicts in which they are involved with the future variables (most popular) [Minton]

• Cruciality [Keng & Yu ’89]

• Promise (most powerful) [Geelen ’92]

• Etc.

Variable Ordering: Fail-first principle

• Recognize dead-ends ASAP to save search effort

• Terminology (FFP) is historic, currently contested

• If you are on

• a correct path, stay on it
• an incorrect path, ‘fail’ on it

• Problem:

• How to guess whether a path is correct?

• Advice:

• choose the ordering that reduces the branching factor, the enemy of search..

Variable ordering heuristics

• Least domain (LD), a.k.a. smallest domain first

• Minimal degree first (degree: deg, ddeg)

• Minimal ratio domain size over degree (ddr, dom/deg, dom/ddeg)

• Brélaz heuristic (originally for graph coloring)

• Weighted degree (wdeg) [Boussemart et al, ECAI 04]

• Minimal width ordering (MWO)

• Maximal cardinality ordering (MCO)

• Minimal bandwidth ordering (BBO)

• Alert: Exploit domino effect (domain has 1 value)

• In general:

• Cheap and effective
• Suitable for both static and dynamic ordering

Brélaz CACM, 79

• Originally designed for coloring. Assigns the most constrained nodes first (i.e., those with the most distinctly colored neighbors), breaking ties by choosing nodes with the most uncolored neighbors.

• Arrange the variables in decreasing order of degrees

• Color a vertex with maximal degree with color 1.

• Choose a vertex with a maximal saturation degree (number of different colors to which is it adjacent). If there is equality, choose any vertex of maximal degree in the uncolored graph

• Color the chosen vertex (with the lowest numbered color)

• If all vertices are colored, stop. Otherwise, return to 3.

wdeg [Boussemart et al, ECAI 04]

• All constraints are assigned a weight, first set to 1

• Every time a constraint is broken during propagation with look-ahead (constraint causing domain wipe-out), its weight is increased

• The weight of an un-assigned variable is defined as the sum of the weights of the constraints that apply to the variable

• The variable with largest weight is chosen for instantiation

• Refinement: dom/wdeg, dom/dwdeg (dynamic)

• Historically: inspired by breakout heuristic of [Morris, AAAI 93], commonly used in local search

Graph-based heuristics

• Minimal width ordering (MWO)

• Maximal cardinality ordering (MCO)

• Minimal bandwidth ordering (BBO)

Width of a graph

• A graph-theoretic criterion

• Constraint graph

• Ordering of nodes how many possible orderings?

• Width of an ordering

• Width of the graph (independent of the ordering)

Minimal width ordering (MWO)

• Reduces the chance of backtracking:

• Variables at the front of the ordering are in general more constrained

• Variables that have more variables depending on them are labeled first

• Finding minimum width ordering: O(n2)

Procedure: Width or a graph G

• Remove from the graph all nodes not connected to any others

• Set k  0

• Do while there are nodes left in the graph

• Set k  (k+1)
• Do While there are nodes not connected to more than k others
• Remove such nodes from the graph, along with any edges connected to them

• Return k

• The minimal width ordering of the nodes is obtained by taking the nodes in the reverse order than they were removed

Variations on MWO

• When removing a node, add a fill-in edge between every two nodes connected to the node but not connected between themselves

• Remove the node that, after removal, yields the smallest number of fill-in edges

• Etc.

Maximal cardinality ordering

• An approximation of min. width ordering

• Choose a node arbitrarily

• Among the remaining nodes, choose the one that is connected to the maximum number of already chosen nodes, break ties arbitrarily

• Repeat…

• Reverse the final order

Minimal bandwidth ordering

• Localizes/confines backtracking

• The smaller the bandwidth, the sooner one could backtrack to relevant decisions

• Finding minimum bandwidth ordering is NP-hard 

• Is there an ordering of a given bandwidth k?

• O(nk+1), i.e. polynomial

Ordering heuristics: how, when?

• How

• Static variable, value ordering
• Dynamic variable (static value)
• Dynamic variable, dynamic value (dynamic vvp)

• When

• Finding one solution
• Finding all solutions

Computing the orders

• Static

• Sort all variables, at pre-processing
• Based on:
• Initial domain (for LD, ddr, etc.)
• All neighbors of a variable (for deg, ddr, etc.)

• Dynamic

• Select one variable, during search
• Based on:
• Current domain (for LD, ddr, etc.)
• All un-instantiated neighbors of a variable (for deg, ddr, etc.)
• Exploit the domino effect.
• When the domain of any future variable has a single value, instantiate this variable first.

Search & ordering heuristics

• At a given level h of the search tree, we encounter:

Static variable, static value

• vvps pertaining to the same variable across a given level

Dynamic variable, static value

• vvps pertaining to the same variable for nodes with a common parent, but possibly to different variables for nodes with different parents

Dynamic vvp

• vvps pertaining to different variables

Side comment

• Common wisdom: When looking for all solutions, value ordering does not matter

• This wisdom holds k-way branching

• [Smith, IJCAI 05] showed that this is not true for 2-way branching, which, apparently, is used in commercial products such as ECLiPSe and Ilog

• The benefits (if any) and implications of 2-way branching versus k-way branching are not fully studied yet