# Algorithms for searching in high-dimensional binary data spaces

Is there any algorithm that can learn/search efficiently the best sequence of 1's and 0's of length $n$ to fulfill certain performance? The search is performed in a high-dimensional binary data space. This means that the search space is of $2^n$ where $n$ usually is in the order of hundreds. I know that Discrete Particle Swarm Optimization, Simulated Annealing or Genetic Algorithms can be used for this purpose, but I'm afraid they tend to get stuck in local optima and/or can not work efficiently in high-dimensional spaces.

• without info about your specific problem, this is hard to answer. Care to elaborate? – Memming Dec 9 '16 at 5:11

## 2 Answers

This question could search for be the analog of a (almost-polynomial) n-SAT algorithm, but no such algorithm is currently available (or may never be if P <> NP), so an optimisation method like SA or GA, should be the best option under your requirements

Additionaly, there is an algorithm called Deterministic Annealing (DA) which performs quite well on many circumstances, maybe check it out

You may be able to formulate your problem as a binary integer program, which even though in general they are NP hard, some instances can be solved very quickly through branch and cut algorithms (if the problem is linear). If your problem is non linear there are MINLP solvers that can give you an optimal answer. Nonetheless I must say that if your problem is particularly hard the most appropriate way to proceed will be metaheuristic.

I suggest that you attempt a linear or quadratic formulation of you problem and try some of the MILP/MIQP solvers available out there. If you are having issues formulating your problem in this framework check some linear programming/integer programming modeling books or post a question here.