Is there any way to solve an linear optimization problem with quadratic integer constraint?
E.g. $\max a^Tx$, $x=\langle x_1,x_2,\cdots,x_n \rangle$
s.t. $x_ix_j<b_{ij}$, $\forall x_i,x_j \in x$
$x_i \in \{0,1\}, \forall x_i \in x$
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Since $x$ is binary and the product only can be $0$ or $1$, your model is a bit odd with the strict inequality. If $b_{ij} >1$ then $x_i$ and $x_j$ are arbitrary, and if $b_{ij} \leq 1$ then you must model the fact that one of the terms has to be zero, which you can do by $x_i + x_j \leq 1$.
-
$\begingroup$ I see what you mean… I also realized my model looks weird with the 0 or 1 value for $x_i$… But if $b_{ij}=1$ then $x_i$ and $x_j$ can be 1 at the same time $\endgroup$MonsterWhat– MonsterWhat2018-05-06 16:05:05 +00:00Commented May 6, 2018 at 16:05
-
$\begingroup$ For $b_{ij}=1$, $x_i$ and $x_j$ can also be arbitrary. So is there any way to mathematically specify the constraint to $b_{ij}<1$? $\endgroup$MonsterWhat– MonsterWhat2018-05-06 16:12:45 +00:00Commented May 6, 2018 at 16:12
-
1$\begingroup$ No, for $b_{ij}=1$ one of them has to be zero, since the product has to be $0$ in that case $\endgroup$Johan Löfberg– Johan Löfberg2018-05-06 18:12:25 +00:00Commented May 6, 2018 at 18:12
-
1$\begingroup$ ...for $0 < b_{ij} < 1$ the product has to be $0$. For $b\leq 0$ the problem is infeasible. You seem to fail to appreciate that you have a strict inequality (which I commented upon in my answer) $\endgroup$Johan Löfberg– Johan Löfberg2018-05-06 18:15:53 +00:00Commented May 6, 2018 at 18:15