A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1programming problems

Operations Research Letters. 2016. Vol. 44. No. 4. P. 479–486.

Borrero J. S., Gillen C., Прокопьев О. А.

We consider reformulations of fractional (hyperbolic) 0-1 programming problems as equivalent mixed-integer linear programs (MILP). The key idea of the proposed technique is to exploit binary representations of certain linear combinations of the 0-1 decision variables. Consequently, under some mild conditions, the number of product terms that need to be linearized can be greatly decreased. We perform numerical experiments comparing the proposed approach against the previous MILP reformulations used in the literature. 

Ключевые слова: linearization, Binary representations, Fractional 0-1programming, Hyperbolic 0-1 programming, Mixed integer linear programs