How slow are direct solutions of NP-complete problems on computers? Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. Are there any? Are there any NP-complete problems with not very bad performance?
 A: This 2003 paper shows there has been quite a bit of work. The focus is on 
"fast" exponential-time solutions to NP-hard problems, including the TSP,
SAT, knapsack problems, graph coloring, to mention a few:

Woeginger, Gerhard J. "Exact algorithms for NP-hard problems: A survey." Combinatorial Optimization—Eureka, You Shrink!. Springer Berlin Heidelberg, 2003. 185-207. PDF download

For example, there is an exact algorithm for the Euclidean TSP in the plane (ETSP)
with time complexity $O(2^{\sqrt{n} \log n})$.
But as is well-known, S. Arora and J.S.B. Mitchell found 
PTAS's to solve ETSP.
This paper has been cited over 500 times since,
showing there has been significant subsequent work.
A: For Boolean Satisfiability (SAT), there is Sat Competition: http://www.satcompetition.org/
State of the art SAT solvers often perform very efficiently, far faster than exponential. At the above link there should be results to see how large instances were solved.
Sucess story: Using SAT solver, important partial results about a conjecture of Erdos were found. The formula was quite big, for details see here: http://cgi.csc.liv.ac.uk/~konev/SAT14/
Sometimes heuristic algorithms perform very fast on graph problems.
For SAT, if you generate random SAT instance, very likely state of the art SAT solver will solve it very fast. (There was very similar question about this here).
A: In full generality, the closest vector problem (CVP) is NP-complete. The LLL algorithm gives an approximate solution in polynomial time. The LLL-BKZ variant gives better approximations as the block size increases (the "B" stands for "Block"). Eventually, when the blocksize equals the dimension, the algorithm solves CVP (in exponential time). There has certainly been lots of experimentation benchmarking run-time (which is more-or-less exponential in the blocksize) versus how good the output is. This has also been done with lattices that have some "smaller than expected" vectors hidden in them. (There are applications in cryptography.) 
