Postponing Branching Decisions

Details Postponing Branching Decisions Postponing Branching Decisions

2004-07-16

arxiv.org/abs/cs/0407042v1

Computer Science

Artificial Intelligence

11 pages, 3 figures

Scientific paper

Solution techniques for Constraint Satisfaction and Optimisation Problems often make use of backtrack search methods, exploiting variable and value ordering heuristics. In this paper, we propose and analyse a very simple method to apply in case the value ordering heuristic produces ties: postponing the branching decision. To this end, we group together values in a tie, branch on this sub-domain, and defer the decision among them to lower levels of the search tree. We show theoretically and experimentally that this simple modification can dramatically improve the efficiency of the search strategy. Although in practise similar methods may have been applied already, to our knowledge, no empirical or theoretical study has been proposed in the literature to identify when and to what extent this strategy should be used.

Affiliated with

Also associated with

No associations

Rating

Postponing Branching Decisions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Postponing Branching Decisions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Postponing Branching Decisions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636289