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$ Commented 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$ Commented Nov 5, 2015 at 22:12
  • $\begingroup$ OK, stay tuned. $\endgroup$ Commented Nov 5, 2015 at 22:12

1 Answer 1

Reset to default
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$ Commented 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$ Commented 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$ Commented Nov 6, 2015 at 20:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.