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

Warren P. Adams () and Stephen M. Henry ()
Additional contact information
Warren P. Adams: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634
Stephen M. Henry: System Readiness and Sustainment Technologies Group, Sandia National Laboratories, Albuquerque, New Mexico 87123

Operations Research, 2012, vol. 60, issue 6, 1477-1490

Abstract: 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.

Keywords: programming; integer; nonlinear; theory (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1106 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:6:p:1477-1490

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().