Binary programming problem. Any closed solution and/or lower bound for this particular case?

Question

Consider the following problem:

$$\begin{array}{ll} \underset{{\bf x} \in \{0, 1\}^N}{\text{minimize}} & {\bf x}^\top {\bf A} \, {\bf x}\\ \text{subject to} & {\bf B} {\bf x} = {\bf c}\end{array}$$

where ${\bf A} \in \{0, 1\}^{N \times N}$ is symmetric, ${\bf B} \in \{0, 1\}^{M \times N}$ and ${\bf c} \in \{0, 1\}^{M}$. Additionally, $N = kM$.

I'm wondering if this kind of problem has been studied. Has this problem a name? Does this problem have a closed form solution? Alternatively, is there some results on the lower bound of this problem? I.e., does there exist a number $\phi$ such that the following holds?

$$\min_{{\bf x} \in \{0, 1\}^N} {\bf x}^\top {\bf A} \, {\bf x} \geq \phi$$

---

I'm not looking for an algorithm for the solution of a specific instance. Rather, I'm looking for theoretical results on this kind of problem.

Answer 1

You can simplify this "quadratic binary programming" (QBP) problem by using any $c_i=0$ to eliminate all $x_j$ for which $B_{i,j}=1$. Hence you can reduce to $Bx=1$. Any such constraints $i$ with only one nonzero value of $B_{i,j}$ then force $x_j=1$, and you can eliminate $x_j$ and any constraints that involve $x_j$. After repeating these preprocessing steps until nothing changes, you are left with $Bx=1$, where each row of $B$ contains at least two nonzero values. You can call a QBP solver or linearize as follows. Introduce a binary variable $y_{i,j}$ to represent the product $x_i x_j$, together with linear constraints $y_{i,j} \le x_i$, $y_{i,j} \le x_j$, and $y_{i,j} \ge x_i + x_j-1$, and then call an integer linear programming solver.

Answer 2

First, there is an obvious reduction of the problem. Suppose that $c_i=0$, and let $S=\lbrace j\in \lbrace 1,\dots,n\rbrace : B_{ij}=1\rbrace.$ If $S=\emptyset,$ the $i$-th constraint reduces to $0 = 0$ and can be dropped. Otherwise, a necessary condition for feasibility is that $x_i=0\ \forall i\in S,$ which lets you reduce the number of variables (and drop the constraint). After applying this for each 0 component in $c$, you are left either with an infeasible problem (because a constraint now reads $0=1$) or a version of the problem where all right hand side values are 1.

Assuming the problem did not implode, you now have a variant of the exact cover problem. The variation is that you have a quadratic rather than linear objective function. The exact cover problem (also known in optimization contexts as the equality-constrained set covering problem, the exact hitting set problem and probably six other things) with a linear objective has been studied. See, for instance, this paper by Balas and Padberg. I don't know whether the quadratic case has been studied.