The goal of this work is to study the portfolio problem which consists in finding a good combination of multiple heuristics given a set of a problem instances to solve. We are interested in a parallel context where the resources are assumed to be discrete and homogeneous, and where it is not possible to allocate a given resource (processor) to more than one heuristic. The objective is to minimize the average completion time over the whole set of instances. We extend in this paper some existing analysis on the problem. More precisely, we provide a new complexity result for the restricted version of the problem, then, we generalize previous approximation schemes. In particular, they are improved using a guess approximation technique. Experimental results are also provided using a benchmark of instances on SAT solvers.

Keywords:

References

S. Albers, Algorithmica 18, 283 (1997), DOI: 10.1007/PL00009158. Crossref, Web of Science, Google Scholar
P. Anet al., Lecture notes in computer science 193 (2003), DOI: 10.1007/3-540-35767-X_13. Google Scholar
S. Bhowmick, V. Eijkhout, Y. Freund, E. Fuentes, and D. Keyes. Application of machine learning to the selection of sparse linear solvers , www.tacc.utexas.edu/~eijkhout/Articles/2006-bhowmick.pdf . Google Scholar
M. Bougeret et al. , Combining multiple heuristics on discrete resources , 11th Workshop on Advances in Parallel and Distributed Computational Models APDCM, (IPDPS) . Google Scholar
M. Bougeret, P.-F. Dutot, A. Goldman, Y. Ngoko, and D. Trystram. Experiments on approximating the discrete resource sharing scheduling problem , http://moais.imag.fr/membres/yanik.ngoko/index.php?view=experiment . Google Scholar
M. Bougeret , P.-F. Dutot and D. Trystram , The guess approximation technique and its application to the discrete resource sharing scheduling problem , Models and Algorithms for Planning and Scheduling Problems (MAPSP) . Google Scholar
V. Cicirello. Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance. PhD thesis, Carnegie Mellon University, 2003 . Google Scholar
J. Dongarraet al., IBM Journal of Research and Development 50(2-3), 223 (2006), DOI: 10.1147/rd.502.0223. Crossref, Web of Science, Google Scholar
P. Fraigniaudet al., Distributed computing with advice: Information sensitivity of graph coloring, International Colloquium on Automata, Languages and Programming (ICALP) (2007) pp. 231–242. Google Scholar
P. Fraigniaud , D. Ilcinkas and A. Pelc , Oracle size : a new measure of difficulty for communication tasks , 25th ACM Symposium on Principles Of Distributed Computing (PODC) . Google Scholar
M. Garey et al. , Computers and Intractability: A Guide to the Theory of NP-Completeness ( Springer , 1979 ) . Google Scholar
C. Gomes and B. Selman, Artificial Intelligence 126(1), 43 (2001), DOI: 10.1016/S0004-3702(00)00081-3. Crossref, Web of Science, Google Scholar
B. Huberman, R. Lukose and T. Hogg, Science 275(5296), 51 (1997), DOI: 10.1126/science.275.5296.51. Crossref, Web of Science, Google Scholar
H. Markowitz, Financial Analysts Journal 5 (1999), DOI: 10.2469/faj.v55.n4.2281. Google Scholar
T. Sayag, S. Fine and Y. Mansour, Combining multiple heuristics, STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science3884, LNCS, eds. Durand and Thomas (Springer, 2006) pp. 242–253. Google Scholar
P. Schuurman and G. Woeginger, Lectures on Scheduling (2000). Google Scholar
H. Shachnai and T. Tamir , Handbook of Approximation Algorithms and Metaheuristics ( Chapman & Hall , Boca Raton , 2007 ) . Google Scholar
L. Simon and P. Chatalic, Electronic Notes in Discrete Mathematics 9, 129 (2001). Crossref, Web of Science, Google Scholar
M. Streeter, D. Golovin and S. Smith, Combining multiple heuristics online, proceedings of the national conference on artificial intelligence22 (AAAI Press; MIT Press, Menlo Park, CA; Cambridge, MA; London, 1999) p. 1197. Google Scholar
S. Talukdaret al., Journal of Heuristics 4(4), 295 (1998), DOI: 10.1023/A:1009669824615. Crossref, Web of Science, Google Scholar
S. Weerawaranaet al., ACM Transactions on Mathematical Software 22(4), 447 (1996), DOI: 10.1145/235815.235820. Crossref, Web of Science, Google Scholar
H. Yu and L. Rauchwerger, Adaptive reduction parallelization techniques, Proceedings of the 14th international conference on Supercomputing (ACM, New York, NY, USA, 2000) pp. 66–77. Google Scholar
F. Zheng, Y. Xu and E. Zhang, Information Processing Letters 106 (2008). Google Scholar