Maximizing the boolean combination of given real numbers with dependencies Let $x_i,x_{ij}\in\mathbb{R}$ and $b_i\in\{0,1\}$ for all $i,j\in\{1,2,\ldots,n\}$ and $j&gt;i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: $$\sum_i b_ix_i+\sum_{j&gt;i}b_ib_jx_{ij}$$

I can think of greedy heuristics (for example, identify the $x_{ij}&lt;0$ and then set either $b_i$ or $b_j$ to zero if $x_i&lt;0$ or $x_j&lt;0$, respectively), but these don't necessarily have always to give the best answer. Is there any optimal algorithm for this or, at least, an approximation one?
It is often more natural to consider $b_i \in \{\pm 1\}$ rather than $b_i \in \{0,1\}$, and it is not difficult to convert your formulation to an equivalent one which uses $\pm 1$ variables rather than $0/1$ variables, using essentially the substitution $b'_i = 2b_i-1$. It is then possible to eliminate the linear term by adding a new variable $b_0$ and replacing $x_i$ with $x_{0i}$. The new problem can be formulated as:


  Maximize $x' M x$ over $\{\pm1\}^n$, where $M$ is a symmetric matrix with zeroes on the diagonal.


(We can assume without loss of generality that $M$ is symmetric and that its diagonal elements are zero, the latter since $(\pm 1)^2 = 1$.)

This problem is known variously as quadratic programming, binary quadratic programming, Boolean quadratic programming, unconstrained binary quadratic programming, and so on; only the first term is ambiguous, since it could also refer to the continuous version of the problem.

Binary quadratic programming generalizes MAX-CUT, and so is NP-hard. In general it is (almost) NP-hard to approximate to within any constant factor, see for example On Non-Approximability for Quadratic Programs by Arora et al. For an up-to-date survey taking a more practical perspective, see The Unconstrained Binary Quadratic Programming Problem: A Survey by Kochenberger et al.