Negative Effects of Modeling Techniques on Search Performance

S. Prestwich ()

Annals of Operations Research, 2003, vol. 118, issue 1, 137-150

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. Copyright Kluwer Academic Publishers 2003

Keywords: symmetry breaking; implied constraints; modeling; search (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1021809724362 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:118:y:2003:i:1:p:137-150:10.1023/a:1021809724362

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1021809724362

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().