Malleable resource sharing algorithms for cooperative resolution of problems

International audienceGiven multiple parallel heuristics solving the same problem, we are interested in combining them for taking advantage of their diversity. We propose to use the algorithm portfolio model of execution. In this model, we have multiple resources on which the candidate heuristics can be executed. An instance is solved through a concurrent execution of heuristics (each on a fraction of resources) that is stopped as soon as one of them completes its execution. The efficiency of this model depends among other things of the resource sharing adopted in a concurrent execution. In most algorithm portfolio studies, the resources fraction of a heuristic is fixed. In this paper, we consider malleable algorithm portfolio. In this portfolio model, the fraction of resources of a heuristic can be changed during its execution. We extend the computational model proposed in [1] to formalize the problem of resource sharing construction in malleable portfolio. We then propose an efficient algorithm based on the combination of two guaranteed approximation algorithms for solving it. Finally, we evaluate the proposed algorithm with multiple simulations on a database of SAT solvers. The obtained results show that even in considering that the resource allocation of a heuristic can just be changed once, malleable allocations in comparison to static ones lead to an improvement of the spent time for solving an instance in algorithm portfolio.time for solving an instance in algorithm portfolio