The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities.
According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities and that it only took 1.5 years in 2006 to solve it.
How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller $n$ it would take million of years to find an optimal solution via brute force. How can $2^{85,900}$ tours be checked in 1.5 years?
You are asking about a very specific instance of the problem and the solution was published as a paper. If you're really interested you should read that.
The solution itself was done with linear programming relaxation techniques and branch-and-bound. There is also a proof which is 32 MB in size when not compressed.
The proof itself basically gives you a lot of inequalities for the LP instance and then for some of them proves (even by brute force) the soundness in this example. This should give you a lower bound of about 142,381,678.2 and you can relax the original problem to just 265,259 edges. Then using branch-and-bound you just need to check this much smaller instance and you can cut anything with the path being longer than the original solution, 142,382,641.
The paper is from 2008 and the authors checked the proof (just checked, not solved the original problem; solution took 136 CPU years) in about 570 hours, so if you have a reasonably strong computer this should be computable in a few days now.
To exactly answer your question, you can use LP and its dual problem to make upper and lower bounds on the solution. If you get good enough equalities for a given problem, you can reduce the instance dramatically.
They didn't use brute force to solve it. They used a smarter method than brute force. I think they used algorithms that don't have any theoretical guarantee that they'll work well on all graphs, but happened to be good enough on that particular graph.
Taken literally, the notion of "the largest instance of travelling salesman problem ever solved" is nonsense. I can easily invent an instance of TSP with one million nodes where I already know the answer, and then solve it immediately (because I know the answer); or invent an easy instance on one million nodes, and then solve it immediately. So I suspect Wikipedia's summary is leaving out important details. As always, don't rely on secondary sources (like Wikipedia or an encyclopedia); instead, follow their citations to the primary source where that claim comes from, and read it to understand more about what is being said.
