Base-2 Expansions for Linearizing Products of Functions of Discrete Variables

This paper presents an approach for representing functions of discrete variables, and their products, using logarithmic numbers of binary variables. Given a univariate function whose domain consists of n distinct values, it begins by employing a base-2 expansion to express the function in terms of the ceiling of log(2) n binary and n continuous variables, using linear restrictions to equate the functional values with the possible binary realizations. The representation of the product of such a function with a nonnegative variable is handled via an appropriate scaling of the linear restrictions. Products of m functions are treated in an inductive manner from i = 2 to m, where each step i uses such a scaling to express the product of function i and a nonnegative variable denoting a translated version of the product of functions 1 through i - 1 as a newly defined variable. The resulting representations, both in terms of one function and many, are important for reformulating general discrete variables as binary, and also for linearizing mixed-integer generalized geometric and discrete nonlinear programs, where it is desired to economize on the number of binary variables. The approach provides insight into, improves upon, and subsumes related linearization methods for products of functions of discrete variables. Subject classifications: programming: integer, nonlinear, theory: Area of review: Optimization. History: Received January 2011; revision received July 2011; accepted October 2011. Published online in Articles in Advance November 20, 2012.