Negative effects of modeling techniques on search performance

Negative effects of modeling techniques on search performance

0.00 Avg rating0 Votes
Article ID: iaor20033299
Country: Netherlands
Volume: 118
Issue: 1
Start Page Number: 137
End Page Number: 150
Publication Date: Feb 2003
Journal: Annals of Operations Research
Authors:
Abstract:

Symmetries occur in many combinatorial problems, and a great deal of research has been done on symmetry breaking techniques for backtrack search. However, few results have been reported on the use of symmetry breaking with local search. On four classes of problem we find that adding symmetry breaking constraints to a model impairs local search performance, in terms of both execution time and search steps. We also find that implied constraints can impair backtrack search performance. These results show that modeling techniques and search heuristics should be combined with caution. They also motivate a novel modeling technique for local search: removing constraints to add new symmetries.

Reviews

Required fields are marked *. Your email address will not be published.