4
$\begingroup$

Given two numbers in binary representation $b_1,b_2$ and let $k_1, k_2$ be the number of digits.

What would be an integer program that models the multiplication of these two numbers? The restriction is that the variables as well as the coefficients of the variables are not allowed to take huge values (that it is still solvable in floating point arithmetic for large numbers).

The integer program needs at least $k_1+k_2$ binary variables to model the result of the multiplication.

$\endgroup$
  • $\begingroup$ Are $b_1$ and $b_2$ constant or variable? Is $2^{k_1+k_2-1}$ considered huge as a coefficient? $\endgroup$ – RobPratt Jul 7 at 15:24
  • $\begingroup$ @RobPratt i would be interested in both version. Yes this is really large! I am looking for something that still works for $k_1=100$. $\endgroup$ – user3680510 Jul 7 at 16:05
  • 2
    $\begingroup$ As a warmup, I recommend considering addition (with binary carryover variables) instead of multiplication. $\endgroup$ – RobPratt Jul 7 at 16:32
3
$\begingroup$

If the numbers are small enough, you can model the multiplication $z=xy$ in a quadratic program, and add the equality $x = \sum2^i b_i$ to relate each number $x$ to its binary representation.

If the numbers are too big, you may run into numerical precision issues with the above. A possible method would be to implement the circuit for a multiplier (for example). You just need to model the linearization of the full-adder. Anecdotally, this is how Minisat+ models linear constraints.

I am almost certain that this second method would NOT work in practice: showing equivalence of multiplier circuits has a reputation for being hard even for SAT solvers and model checkers. A MIP solver is not designed to handle this.

| improve this answer | |
$\endgroup$

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.