1
$\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$
  • $\begingroup$ Are $a,\dots, g$ positive? This matters. $\endgroup$ – Michael Grant Nov 5 '15 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 '15 at 22:12
  • $\begingroup$ OK, stay tuned. $\endgroup$ – Michael Grant Nov 5 '15 at 22:12
2
$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\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 '15 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 '15 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$ – Michael Grant Nov 6 '15 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.