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.)
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$.