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

Solution 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.