Subset selection problems involve finding an optimal feasible subset of an initial set of objects with respect to an objective function and/or some constraints. Many well-known combinatorial problems are members of this class, e.g., maximum clique problems, knapsack problems, boolean satisfiability problems, constraint satisfaction problems, and graph matching problems.

In this paper we define a generic ant colony optimization (ACO) algorithm for this class of problems. Basically, this algorithm successively generates subsets through the repeated selection of objects, and uses ``pheromone trails'' as a greedy heuristic to choose, at each step, the next object to be selected. The algorithm is parameterized by a pheromonal strategy and we propose and compare two different instantiations of it: a first one where pheromone is laid on objects and a second one where pheromone is laid on cliques of objects. The proposed algorithm is also parameterized by problem-specific features, and we present and evaluate instantiations of it for solving maximum clique problems, knapsack problems and constraint satisfaction problems.