L15: Variable Heuristics

Question 1

What are static heuristics?

Answer 1

Order in which variables/values selected/assigned chosen before search.
- Order is set before search starts.
- Order is fixed for entire search

E.g.
- Assign variables in order x1, x2, x3
- Assign variables in ascending order

Question 2

What are some operations we can order heuristically?

Answer 2

1. Variable assignment order.
2. Value assignment order.
3. Constraint checking order.

Question 3

What are dynamic heuristics?

Answer 3

• Examine the state of the problem during the search
• Decide on the ‘best’ variable/value to assign next

E.g.
- ’Smallest domain’ variable ordering (Affected by FC/MAC propagation, which differs based on the assignments made)
- ‘Min-conflicts’ value ordering

Question 4

How do we know which type of heuristic to choose?

Answer 4

• Make the most difficult choice first (variables).
• Have the most far-reaching consequences for the rest of the problem.
• Narrows down easy choices.
• If we make the easy choices first, we can paint ourselves into a corner, as in the previous example.
• For the most difficult choice choose the option most likely to succeed (values).

Question 5

What is first ordering?

Answer 5

For each variable, the first value we assign that is compatible with the past assignments is part of the solution.

Question 6

What is second ordering?

Answer 6

Because of the variable assignment order, we make assignments that ‘look good’ but turn out to have no solutions and backtracking is required. (e.g. thrashing- repeated failure for the same reason)

Question 7

How can we look at static variable heuristics?

Answer 7

Using a graph that represents the constraints

Question 8

What is a primal graph?

Answer 8

The primal graph has an edge between two nodes if they are in a constraint together (unlike the constraints graph where each edge represents a constraint)

Question 9

What is a hypergraph?

Answer 9

A graph that describes an area rather than just an edge between 2 nodes.

Question 10

What is maximum degree ordering?

Answer 10

Order variables in decreasing order of their degrees in the graph (break ties arbitrarily).

Question 11

What is the degree of a variable?

Answer 11

How many edges the variable has

Question 12

How does maximum degree fit with the rationale of making hard choices first?

Answer 12

Variables in a lot of constraints may be highly constrained. However they may not, constraints vary in tightness.

Highly constrained may be the hardest choices.

Question 13

What is maximum cardinality ordering?

Answer 13

1. Select the first variable arbitrarily
2. Repeat until there are no more variables: append to the order a variable connected to the largest group among those already selected.

We want to prioritise the nodes with the most constraints that are related to past variables.
E.g., when picking node 4, we would prefer to pick a node with constraints to nodes 1, 2, 3 as much as possible.

Question 14

How does maximum cardinality fit with the rationale of making hard choices first?

Answer 14

After assigning some variables, the next hard choice is the one most constrained by the existing assignment (after all we need to make choices compatible with the existing assignment).

Question 15

What is the width at an ordered node?

Answer 15

Number of arcs/edges linking back to a previous variable in the ordering.

Question 16

What is the width of an ordering?

Answer 16

Maximum width at any node.

Question 17

What is the width of a constraint graph?

Answer 17

Minimum width of all its orderings (that is not 0).
1. Identify all possible orderings.
2. For each ordering, identify the width of the nodes and the ordering.
3. Identify the ordering with the minimum width.

Question 18

What is an ordered graph?

Answer 18

An arrangement of graph nodes in a fixed linear order.

Question 19

What is minimum width ordering?

Answer 19

We want to achieve an ordered graph with a minimum width.

Question 20

How does minimum width fit with the rationale of making hard choices first?

Answer 20

The nodes with the greater widths are prioritised and therefore the harder choices are selected first.

Question 21

What are 3 static variable orderings?

Answer 21

• Maximum degree
• Maximum cardinality
• Minimum width

Question 22

What are 3 dynamic variable orderings?

Answer 22

• Smallest domain first
• Brelaz
• dom/deg

Question 23

What is smallest domain ordering?

Answer 23

Select the variable with the smallest number of
values compatible with past assignments.

Dynamic because selection made based on state during search.

Question 24

What is Brelaz ordering?

Answer 24

Select the variable with the smallest
number of values compatible with past
assignments. So far, same as Smallest Domain

Break ties by selecting the variable with
the maximum degree in the constraint
sub-graph of the future variables.

Question 25

What is dom/deg ordering?

Answer 25

Select the variable that minimises the quotient
domain size/degree in future constraint graph.

When constraint graph is sparse, minimum domain less useful than an ordering based on degree. When constraint graph is dense, minimum domain much better than degree alone. Rather than break ties with one or the other, this heuristic combines them.

Question 26

Compare the performance of static and dynamic heuristics.

Answer 26

• In studies on random problems, dynamic
  orderings often seen to do better.
• On structured problems, static orderings can
  often perform very well.
• Part of the art of constraint programming is
  choosing an appropriate heuristic for your
  problem.

Question 27

What are some types of value ordering?

Answer 27

• Ascending value
• Min-conflicts
• Geelen’s value-ordering heuristics

Question 28

What is ascending value assignment ordering?

Answer 28

Given an ordered domain, assign values lowest-first.

Question 29

What is min-conflict ordering?

Answer 29

Having chosen a variable, consider each of its domain elements. Count the number of incompatible vales in the domains of future variables.

Assign domain elements in increasing order of this count, i.e. least constraining first.