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

• 成果类型: Article
• 署名作者: Adams, Warren P.; Henry, Stephen M.
• 署名单位: Clemson University; United States Department of Energy (DOE); Sandia National Laboratories
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1106
• 发表日期: 2012
• 页码: 1477-1490
• 关键词: superior representation method; global optimization; DESIGN

摘要

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.