People routinely solve quadratic assignment problems (perhaps not provably optimal, but finding good solutions within a small bound of optimality) where the search space is greater than 10^3000 [0], using relatively simple heuristics like simulated annealing.

[0] e.g. any of the QAPLIB instances in Goh et al. Proceedings of the 2022 Genetic and Evolutionary Computation Conference