Combining Multiple Heuristics on Discrete Resources

Abstract : In this work we study the portfolio problem which is to find a good combination of multiple heuristics to solve given instances on parallel resources in minimum time. The resources are assumed to be discrete, it is not possible to allocate a resource to more than one heuristic. Our goal is to minimize the average completion time of the set of instances, given a set of heuristics on homogeneous discrete resources. This problem has been studied in the continuous case in [T. Sayag et al., 2006]. We first show that the problem is hard and that there is no constant ratio polynomial approximation unless P = NP in the general case. Then, we design several approximation schemes for a restricted version of the problem where each heuristic must be used at least once. These results are obtained by using oracle with several guesses, leading to various tradeoff between the size of required information and the approximation ratio. Some additional results based on simulations are finally reported using a benchmark of instances on SAT solvers.
Type de document :
Communication dans un congrès
IPDPS, May 2009, Rome, Italy. pp.1-8, 2009, 〈10.1109/IPDPS.2009.5160879〉
Liste complète des métadonnées
Contributeur : Ist Rennes <>
Soumis le : mercredi 18 avril 2012 - 13:39:02
Dernière modification le : jeudi 11 janvier 2018 - 06:22:02




Marin Bougeret, Pierre-Francois Dutot, A. Goldman, Yanik Ngoko, Denis Trystram. Combining Multiple Heuristics on Discrete Resources. IPDPS, May 2009, Rome, Italy. pp.1-8, 2009, 〈10.1109/IPDPS.2009.5160879〉. 〈hal-00688739〉



Consultations de la notice