TY - JOUR
T1 - Encoding binary arithmetic operations in integer programming formulations
AU - Conejeros, Raul
AU - Vassiliadis, Vassilios S.
AU - Pogiatzis, Thomas A.
PY - 2014
Y1 - 2014
N2 - This paper presents the encoding of binary arithmetic operations within Integer Programming (IP) formulations, specifically the encoding of binary multiplication and addition/subtraction. This allows the direct manipulation of integer quantities represented as binary strings of arbitrary size. Many articles published in the past within the Chemical Engineering community have used this representation of integer quantities within Mixed-Integer formulations for Process Optimization and Design. Applications such as these can benefit from the formulations derived in this work. As a demonstrative application we consider the simple number factorization problem, according to which given an odd number C factors A and B are to be found such that C equals their product. If any such factors are found the number is factorable, else it is proven to be prime. An IP formulation is derived involving upper and lower bounding logical constraints to encode for the value of the binary string digits. The formulation involves O(logC) binary variables, O((logC)2) continuous variables, and O((logC)2) constraints to describe the problem. Computational results demonstrate the validity of this approach, highlighting also the fact that such formulations are not very tight thus resulting in large numbers of iterations of the Branch and Bound algorithm used. It is also observed that the formulations become significantly tighter if logical upper bounding constraints forcing continuous variables involved to be zero are included.
AB - This paper presents the encoding of binary arithmetic operations within Integer Programming (IP) formulations, specifically the encoding of binary multiplication and addition/subtraction. This allows the direct manipulation of integer quantities represented as binary strings of arbitrary size. Many articles published in the past within the Chemical Engineering community have used this representation of integer quantities within Mixed-Integer formulations for Process Optimization and Design. Applications such as these can benefit from the formulations derived in this work. As a demonstrative application we consider the simple number factorization problem, according to which given an odd number C factors A and B are to be found such that C equals their product. If any such factors are found the number is factorable, else it is proven to be prime. An IP formulation is derived involving upper and lower bounding logical constraints to encode for the value of the binary string digits. The formulation involves O(logC) binary variables, O((logC)2) continuous variables, and O((logC)2) constraints to describe the problem. Computational results demonstrate the validity of this approach, highlighting also the fact that such formulations are not very tight thus resulting in large numbers of iterations of the Branch and Bound algorithm used. It is also observed that the formulations become significantly tighter if logical upper bounding constraints forcing continuous variables involved to be zero are included.
KW - Binary arithmetic
KW - Binary strings
KW - Integer programming
KW - Number factorization
UR - http://www.scopus.com/inward/record.url?scp=84946549071&partnerID=8YFLogxK
U2 - 10.1007/s10852-013-9225-9
DO - 10.1007/s10852-013-9225-9
M3 - Article
AN - SCOPUS:84946549071
SN - 1570-1166
VL - 13
SP - 143
EP - 167
JO - Journal of Mathematical Modelling and Algorithms
JF - Journal of Mathematical Modelling and Algorithms
IS - 2
M1 - A003
ER -