Article ID: | iaor20073078 |
Country: | France |
Volume: | 40 |
Issue: | 4 |
Start Page Number: | 381 |
End Page Number: | 401 |
Publication Date: | Oct 2006 |
Journal: | RAIRO Operations Research |
Authors: | Jussien Narendra, Cambazard Hadrien |
Keywords: | combinatorial optimization |
Identifying structure in a given combinatorial problem is often a key step for designing efficient search heuristics or for understanding the inherent complexity of the problem. Several Operations Research approaches apply decomposition or relaxation strategies upon such a structure identified within a given problem. The next step is to design algorithms that adaptively integrate that kind of information during search. We claim in this paper, inspired by previous work on impact-based search strategies for constraint programming, that using an explanation-based constraint solver may lead to collect invaluable information on the intimate dynamic and static structure of a problem instance.