Combinatorial Optimization Problems with Testing