Encoding binary arithmetic operations in integer programming formulations

Raul Conejeros, Vassilios S. Vassiliadis, Thomas A. Pogiatzis

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

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.

Idioma originalInglés
Número de artículoA003
Páginas (desde-hasta)143-167
Número de páginas25
PublicaciónJournal of Mathematical Modelling and Algorithms
Volumen13
N.º2
DOI
EstadoPublicada - jun 2014
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Encoding binary arithmetic operations in integer programming formulations'. En conjunto forman una huella única.

Citar esto