References for Functions of Binary Variables Setup: Let $x_i\in\{0,1\}$ for $i=1,...,n$ and $f:\{0,1\}^n\rightarrow \mathbb{R}$. We wish to find the extrema for this function for all $x\in\{0,1\}^n$. 
Questions: I am very interested in any related results and or references. A google search did not yield anything that appears to relate to this problem.
Thoughts: At first glance, it seem that we could extend to $\mathbb{R}^n$ and then somehow transition back to $\{0,1\}^n$. However, it is not obvious (to me) how this transition might be done if at all possible.
 A: Finding the maximum of $f(x)$ where $x \in \{0, 1\}^n$ is a fundamental integer optimisation problem, and no algorithm currently exists to find the solution quickly1.
There are some methods to find approximations to the maximum in polynomial time, and what you're suggesting is part of a method called linear relaxation - you solve the easier problem of optimising the equivalent function for $x \in [0, 1]^n$ (i.e. where $x$ takes real values in the interval), and then make some assumptions about how close the optimal solution of the integer problem is to that point. Depending on the problem, this can be quite a good approximation (for example, some solutions can guarantee to get within a factor of $1+\epsilon$ of the true optimum for arbitrarily small $\epsilon$), and in other cases you find you can't do better than, say, being within a factor of $\log(n)$ of the true optimum.
If you're interested in learning more, there are a lot of online courses on optimization problems and the associated approximation techniques on sites like Coursera.
1 Where "quickly" means in a time that is polynomial in $n$. As pointed out in a comment, it's possible to find a solution in a time that is of the order of $2^n$, which is pretty terrible once $n$ gets big enough.
