Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Benchmarking algorithms for distributed constraint optimization problems in Signal/Collect
Organization Unit
Authors
  • Robin Hafen
Supervisors
  • Coralia-Mihaela Verman
  • Abraham Bernstein
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 62
Date 2013
Abstract Text Many real world problems, such as network congestion control, can be mapped to the concept of a distributed constraint optimization problem (DCOP). By analyzing a class of DCOP algorithms known as local iterative approximate best-response (LIBR) algorithms, [Chapman et al., 2011b] constructed a framework enabling the study and modular design of new hybrid algorithms. In [Chapman et al., 2011a], several classical, as well as new hybrid algorithms, were benchmarked in a series of graph coloring experiments. It was found that the modular approach to algorithm design allowed the creation of new, better performing algorithms. In this thesis a similar approach was taken: selected existing LIBR algorithms, such as the distributed stochastic algorithm and distributed simulated annealing, were implemented and benchmarked using a graph processing framework called Signal/Collect [Stutz et al., 2010], with which no such benchmark has ever been conducted. As a further contribution, an existing, non-distributed algorithm from computer science literature called tabu search [Nurmela, 1993] was modularized and distributed in the same manner.
Zusammenfassung Viele Probleme in der Informationstechnologie, wie zum Beispiel das Stausteuerungsproblem in Computernetzwerken, lassen sich als verteilte Bedingungsoptimierungsprobleme darstellen. [Chapman et al., 2011b] erstellten ein Rahmenwerk zur Analyse und modularen Konstruktion von neuen Hybridalgorithmen zum Lösen solcher Probleme. In [Chapman et al., 2011a] wurden mehrere solche Hybridalgorithmen in einer Serie von Graphfärbungsexperimenten auf ihre Leistungseigenschaften untersucht. Es wurde festgestellt, dass die modulare Konstruktionsweise die Erstellung von besseren Algorithmen ermöglicht. In dieser Arbeit wurde ein ähnlicher Ansatz gewählt: Ausgewählte klassische Algorithmen wie der distributed stochastic algorithm und distributed simulated annealing sowie mehrere Hybridalgorithmen wurden anhand eines Programmierungsmodells namens Signal/Collect [Stutz et al., 2010] in einem bislang nicht existierenden Benchmark-Test evaluiert. Als ein weiterer Beitrag wurde ein zentraliserter Algorithmus namens tabu search in der gleichen Weise modularisiert und getestet.
PDF File Download
Export BibTeX