Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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.
