1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Apr 20 '17 at 17:12
  • $\begingroup$ 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. $\endgroup$ – Cromack Apr 21 '17 at 15:04
  • $\begingroup$ 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! $\endgroup$ – D.W. Apr 21 '17 at 15:24
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.