| Pattern name |
DualHeuristics. |
| Context |
A model in which both primal and dual viewpoints are possible. |
| Problem |
Choosing a good variable and value to branch upon. |
| Forces |
Branching heuristics need to be accurate to reduce search. Branching heuristics need to be cheap to reduce runtimes. |
| Solution |
Consider a combined model with channelling between
the primal and dual variables. Use a variable ordering heuristic like smallest-domain to choose a primal or dual variable. Then use a variable ordering heuristic like smallest-domain again to pick a value for this variable from the dual viewpoint. |
| Example |
Any permutation problem (e.g. Langford's number problem,
prob024 in
CSPLib). |
| References |
Models of Permutation and Injection Problems
(ps)
Brahim Hnich, Barbara Smith, and Toby Walsh. Submitted to Journal of AI Research (JAIR), 2003
|