# 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>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>i}b_ib_jx_{ij}$$

I can think of greedy heuristics (for example, identify the $x_{ij}<0$ and then set either $b_i$ or $b_j$ to zero if $x_i<0$ or $x_j<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?

• What are the inputs, and what are the desired outputs? Are we allowed to choose all of the $x_i,x_{ij},b_i$ freely? Or are some of them (e.g., $x_i,x_{ij}$) provided as the input and fixed, and then we need to choose $b_i$'s to maximize that expression, without being able to change the $x_i,x_{ij}$'s? – D.W. Apr 20 '17 at 17:12
• The $x_i,x_{ij}$'s are the inputs, so you need to choose the $b_i$'s to maximize the expression without being able to change the $x_i,x_{ij}$'s. The desired output can be either the boolean combination or the result of the expression when maximized. – Cromack Apr 21 '17 at 15:04
• Thanks, Cromack. Can you edit the question to include that information? We want questions here to be self-contained, so that people don't have to read the comments to understand what you are asking. Thank you! – D.W. Apr 21 '17 at 15:24

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$.)