Beyond quadratic in binary integer programming If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. But what if my objective function is a polynomial of degree 3:
$$U(x,y,z) = ax + by + cz + dxy + eyz+ fxz + gxyz $$
where $a,...,g$ are constants and $x,y,z$ are binary choice variables. Does that extra $gxyz$ term render simplex or IP algorithms that solve the sub-problem of the branch and bound ineffective? If so, is there any intuition for why that is?
Also, what if my my objective function is quadratic but I have a constraint that includes a polynomial of degree 3 such as $xyz=0$? Am I out of luck?
Is there some work-around for solving either of these problems? (Yes, I know there are only 8 possible outcomes, so brute force would be fine here, but I'm looking for answers for larger problems.)
 A: You don't even need quadratic support if all of your variables are binary and the coefficients $a,\dots, g$ are positive. Linear inequalities are sufficient.
Consider the binary product $xy$. This quantity is 1 if and only if $x=y=1$. Create a new binary variable $t_1$, and consider the inequality $x+y\leq t_1+1$. If $x=y=1$, it must be the case that $t_1=1$ as well. 
If $d>0$ in your objective, then you can replace $dxy$ with $dt_1$, and the solver will seek the smallest value of $t_1$ that satisfies the constraint. Thus if $xy=0$, the solver will indeed select $t_1=0$.
Similarly, for the $gxyz$ term, define a binary variable $t_2$ and add the inequality $x+y+z\leq t_2+2$. The constraint ensures that $t_2=1$ if $xyz=1$, and $g>0$ ensures that $t_2=0$ if $xyz=0$.
If one or more of the coefficients is negative you have more work to do. For the $dxy$ case, you need to add the constraints $x\geq t_1$, $y\geq t_1$. That way, if $x=0$ or $y=0$, it must be the case that $t_1=0$ as well. Likewise, for $gxyz$ you need $x\geq t_2$, $y\geq t_2$, $z\geq t_2$ to ensure that $t_2=0$ if $x=0$ or $y=0$ or $z=0$.
