COMPUTER SCIENCE COLLOQUIUM

On the clustering of approximate solutions in
multiobjective combinatorial optimization problems

Luis Paquete Faculdade de Economia and Centro de Sistemas Inteligentes University of Algarve, Portugal

Tuesday, May 8, 2007, at 14:15 IMADA's Seminar Room

ABSTRACT

Given an efficient or approximate solution set of a multiobjective combinatorial optimization problem, a complete weighted graph can be constructed such that each node represents a solution and each edge weight corresponds to the distance between a pair of solutions under a given neighborhood function. For a given distance, an eventually disconnected graph can be devised by removing from the complete graph those edges whose weights exceed that distance. Of particular interest is the identification of clusters, i.e., maximally connected components of this disconnected graph, since local search algorithms would be able to explore them effectively. In this talk we review and discuss some results available in the literature, with particular emphasis on experimental results recently obtained for the biobjective versions of the Traveling Salesman Problem and the Quadratic Assignment Problem.

Host: Marco Chiarandini

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: Mon Apr 16 10:41:26 CEST 2007

Joan Boyar (joan@imada.sdu.dk)