Hybrid metaheuristics are algorithms that combine components of different techniques for optimization. Examples are combinations of metaheuristics with dynamic programming, contraint programming, and branch and bound. In this work we present a hybrid metaheuristic which is based on an iterative probabilistic reduction of the problem instance size, with a subsequent application of an integer linear programming (ILP) solver in order to find the best solution contained in the reduced problem instance. An experimental evaluation reveals that the proposed technique obtains state-of-the-art results for two different NP-hard combinatorial optimization problems: the minimum weight rooted arboresence problem and the minimum common string partition problem.