I remember somewhere seeing the following. If $x$ and $y$ are integer variables then we cannot multiply them easily unless we know a bound $B$ on them.

Suppose I have an array $\overline x=[x_1\dots x_n]\in\{0,1\}^n$ and $0\leq y\leq B_y$ holds and entries of $x$ and variable $y$ are integers then is it possible to multiply $y\cdot \overline x$ with no extra integer variables and only $O(n\log B_y)$ real variables in $MILP$? I want real variables $z_1,\dots,z_n$ that the $MILP$ should have with the result $z_1=y\cdot x_1,\dots,z_n=y\cdot x_n$.

  • $\begingroup$ What does it mean here to 'multiply $y\cdot x$' here? Have this expression in a constraint? In the goal? As the result of the linear program? Please specify. $\endgroup$ – Discrete lizard May 24 '18 at 17:48
  • $\begingroup$ @DiscreteLizard Do you know what MILP is? $\endgroup$ – Turbo May 24 '18 at 17:50
  • $\begingroup$ Yes, a mixed integer linear program. So, you want to use multiplication as a constraint on some real variables $z$. This is clearer, thanks. $\endgroup$ – Discrete lizard May 24 '18 at 18:27
  • $\begingroup$ @Discretelizard Both $y$ and $x_i$ are variables and that is the catch. $\endgroup$ – Turbo May 25 '18 at 3:15

Your Answer

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

Browse other questions tagged or ask your own question.