In this talk, I will describe some anytime tree search algorithms introduced in my phd thesis. These branch-and-bound methods obtain near-optimal solutions in a reasonable time, and, in some sense, are similar to classical meta-heuristics. They obtained state-of-the-art performance on some combinatorial optimization problems (EURO/ROADEF challenge, sequential ordering problem, permutation flowshop, longest common subsequence problem).