[Zurück]

N. Musliu:
"Local Search Algorithm for Unicost Set Covering Problem";
Vortrag: 19th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Annecy, Frankreich; 27.06.2006 - 30.06.2006; in: "Advances in Applied Artificial Intelligence", M. Ali, R. Dapoigny (Hrg.); Springer, LNAI 4031 (2006), ISBN: 3-540-35453-0; S. 302 - 311.

The unicost set covering problem is a NP-hard and it has many applications. In this paper we propose a new algorithm based on local search for solving the unicoat set covering problem. A fitness function is proposed for this problem and different neighborhood relations are considered for the exploration of the neighborhood of the current solution. A new approach is introduced for the effective exploration of the neighborhood during the improvement phase. This approach is based on the upper bound of the best cover, which is found during the search, and using only determined moves. Additionally, in order to avoid cycles during the search, a search history is used. Thte proposed algorithm is experimentally evaluated for 85 well-known random and combinatiorial problems in the literature, and it gives very satisfactory reesults in a reasonable amount of time. The proposed algorithm improves the best existing solutions for 8 problems in the literature. For a class of combinatorial problems, the best existing results are improved significantly.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC06586787

Projektleitung Georg Gottlob:
Komplementäre Ansätze für Constraint Satisfaction