| On 2006-05-26 at 16:00:00 (Brussels Time) |
Abstract
This talk presents an algorithm for the Set Covering Problem whose centerpiece is a new primal-to-dual scheme aimed at linking any primal solution to the dual feasible vector that best reflects the quality of the primal solution. This new mechanism is used to intertwine a tabu search based primal intensive scheme with a lagrangian based dual intensive scheme to design a dynamic primal-dual algorithm that progressively reduces the gap between upper and lower bound. Results on benchmark problems from the OR-Library will be presented. The objective of the talk is to identify possible avenues of research to come up with an algorithm especially suited for very large scale instances of SCP, perhaps via an implementation of a parallel algorithm based upon the ACO paradigm. The new algorithm would be used in the context of Data Mining and Knowledge Discovery for the identification of the smallest set of features needed to describe a given population.
Keywords
Set Covering Problem, primal-to-dual scheme, tabu search
