TY - JOUR

T1 - Encoding binary arithmetic operations in integer programming formulations

AU - Conejeros, Raul

AU - Vassiliadis, Vassilios S.

AU - Pogiatzis, Thomas A.

N1 - Publisher Copyright:
© Springer Science+Business Media Dordrecht 2013.

PY - 2014/6

Y1 - 2014/6

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

VL - 13

SP - 143

EP - 167

JO - Journal of Mathematical Modelling and Algorithms

JF - Journal of Mathematical Modelling and Algorithms

SN - 1570-1166

IS - 2

M1 - A003

ER -