Foundations of Constraint Processing

Yüklə 256 Kb.
ölçüsü256 Kb.

Foundations of Constraint Processing

  • Foundations of Constraint Processing

  • CSCE421/821, Fall 2005:


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

  • Avery Hall, Room 123B


  • 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]

  • 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

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

Kataloq: ~choueiry

Yüklə 256 Kb.

Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2023
rəhbərliyinə müraciət

    Ana səhifə