Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Constraint Hierarchy and Stochastic Local Search for Solving Frequency Assignment Problem
verfasst von : T. V. Su, D. T. Anh
Erschienen in: Modeling, Simulation and Optimization of Complex Processes
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
One approach for modeling over-constrained problems is using constraint hierarchies. In the constraint hierarchy framework, constraints are grouped into levels, and appropriate solutions are selected using a comparator which takes into account the constraints and their levels. Finite domain constraint hierarchy is one of the NP-hard optimization problems that have been studied for a long time due to its relevance to various application areas. Nevertheless, stochastic local search methods for solving finite domain constraint hierarchies remain largely unexplored. In this paper, we develop a variant of WSAT algorithm that can solve constraint hierarchies over finite domains. We experiment this generic algorithm in a real world application: solving Frequency Assignment Problem in the area of wireless communication. Experiments on benchmark Philadelphia instances of realistic sizes show that the proposed algorithm is an efficient heuristic to find good approximate solutions.