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.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-00688739
Contributor : Ist Rennes <>
Submitted on : Wednesday, April 18, 2012 - 1:39:02 PM
Last modification on : Wednesday, March 13, 2019 - 3:02:07 PM

Links full text

Identifiers

Collections

Citation

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, ⟨10.1109/IPDPS.2009.5160879⟩. ⟨hal-00688739⟩

Share

Metrics

Record views

221