A Computational Model for Portfolios of Cooperative Heterogeneous Algorithms for Discrete Optimizatio

Discrete optimization problems arise throughout many real world domains including planning, decision making, and search. NP-hard in general, these problems require novel approaches to algorithm design and development. Algorithm portfolios which consist of multiple algorithm instances and types executing in parallel has been a key novel approach to these problems. We focus on cooperative portfolios where algorithms actively communicate and interact with one another during problem solving to more efficiently determine the optimal solution. Unfortunately, the added dimension of cooperation greatly complicates our understanding of the method. The goal of this paper is to provide the first comprehensive formal computational model of portfolios of cooperative heterogeneous algorithms in order to lay the foundations for rigorous analyses of these portfolios in hopes of eventually leading to provable guarante es of performance, effectiveness, and efficiency.