Constraint Hierarchy and Stochastic Local Search for Solving Frequency Assignment Problem

T. V. Su and D. T. Anh ()
Additional contact information
T. V. Su: HoChiMinh City University of Technology
D. T. Anh: HoChiMinh City University of Technology

A chapter in Modeling, Simulation and Optimization of Complex Processes, 2008, pp 531-545 from Springer

Abstract: Abstract 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.

Keywords: Local Search; Constraint Satisfaction Problem; Local Search Algorithm; Soft Constraint; Generic Solver (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-3-540-79409-7_39

Ordering information: This item can be ordered from
http://www.springer.com/9783540794097

DOI: 10.1007/978-3-540-79409-7_39

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().