Binary Programming with nonlinear constraints

Question

i have the following type of problem i'm interested to solve:

Minimize the objective function: $f(x_1,\ldots, x_8) = \sum_{i=1}^8 a_i x_i$ with $a_i \in [0, \infty)$ and $x_i \in \{0,1\}$ and given constraints:$\\ \begin{align} x_1+x_2+x_3+x_4 &= 1\\ x_5+x_6+x_7+x_8 &= 1\\ x_1x_5 + x_2x_6 + x_4x_8 + x_4x_7 &= 1 \end{align}$

Later i want to solve this type of problem with say 200 variables. Is there a matlab implementation to this? I only know yet the binintprog function to solve linear binary programming. Also I think, that this could be computationally extremly hard to solve.

Answer 1

I've just noticed (thanks to @Macavity) that $x \in \{0,1\}$, not $x \in [0,1]$. Then, your system as it is, is trivial. The first equation says: exactly one of $x_i$ for $i \in \{1,2,3,4\}$ equals 1, and the second implies the same for $i \in \{5,6,7,8\}$. The third ensures that exactly one pair must be "enabled", so you need to find minimum of $a_i+a_j$ such that $x_ix_j$ term belongs to the third formula, that's it.

This easily extends to solutions with more variables and the same form. On the other hand, it might be very hard to find a solution for a general problem, the issue being you can easily embed any logical formula into it, particularly the SAT problem. Finally, there is a hope for some formulas, including those that can be converted to 2-SAT, for example, it is alright as long as your constraints mention at most two variables at a time.

I hope this helps ;-)

Answer 2

Try defining an auxiliary variable $y_{j,k}$ for each $j$ and $k$ with the constraints

$y_{j,k}\ge 0$

$y_{j,k}\le 1$

$y_{j,k}\le x_j$

$y_{j,k}\le x_k$

$y_{j,k}\ge x_j+x_k-1$

that force $y_{j,k}=x_jx_k$.

Then express your constraint $x_1x_5+x_2x_6+x_4x_8+x_4x_7$ = 1 as $y_{1,5}+y_{2,6}+y_{4,8}+y_{4,7} = 1$ yielding an equivalent binary linear programming problem.

You are right: in general these problem can be very hard to tackle.