2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Are $a,\dots, g$ positive? This matters. $\endgroup$ Nov 5, 2015 at 22:10
  • $\begingroup$ @MichaelGrant Yes -- let's suppose they are. Though I'd also be curious to know why it's different if they're not. $\endgroup$
    – Shane
    Nov 5, 2015 at 22:12
  • $\begingroup$ OK, stay tuned. $\endgroup$ Nov 5, 2015 at 22:12

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This is brilliant. I'm a little embarrassed it didn't occur to me. Thanks very much. Now I can go back to my problem and leave polynomials of higher order to people who are smarter than I. $\endgroup$
    – Shane
    Nov 6, 2015 at 0:25
  • $\begingroup$ You say I don't need quadratic support if the coefficients are positive, but it seems from your solution that it's fine also if the coefficients are negative -- it just costs me multiple constraints instead of one. So I don't need coefficients to be positive, per se -- it's just that negative coefficients require more constraints. Do I understand correctly, or is there an additional cost to negative coefficients that I'm missing? $\endgroup$
    – Shane
    Nov 6, 2015 at 20:49
  • $\begingroup$ I think that's right. When I wrote the part about positive coefficients I hadn't worked out the negative case yet. $\endgroup$ Nov 6, 2015 at 20:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .