**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 **choueiry@cse.unl.edu**
## Tel: +1(402)472-5444
**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 ## 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]** ## 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 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…
**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*?
**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**
**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** ## 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
**Dostları ilə paylaş:** |