Algorithm Selection for Constraint Optimization Domains
International Journal of Advanced Computer Science and Applications(IJACSA), (2013)Abstract
In this paper we investigate methods for selecting
the best algorithms in classic distributed constraint optimization
problems. While these are NP-complete problems, many heuristics
have nonetheless been proposed. We found that the best
method to use can change radically based on the specifics of
a given problem instance. Thus, dynamic methods are needed
that can choose the best approach for a given problem. We
found that large differences typically exist in the expected utility
between algorithms, allowing for a clear policy. We present a
dynamic algorithm selection approach based on this realization.
As support for this approach, we describe the results from
thousands of trials from Distributed Constraint Optimization
problems that demonstrates the strong statistical improvement
of this dynamic approach over the static methods they are based
on.