Nonlinear 0-1 Programming: I. Linearization Techniques. Revision.
Abstract
Any real-valued nonlinear function in 0-1 variables can be rewritten as a multilinear function. We discuss classes of lower and upper bounding linear expressions for multilinear functions in 0-1 variables. For any multilinear inequality in 0-1 variables, we define an equivalent family of linear inequalities. This family contains the well known system of generalized covering inequalities, as well as other linear equivalents of the multilinear inequality that are more compact, i.e., of smaller cardinality. In a companion paper, we discuss dominance relations between various linear equivalents of a multilinear inequality, and describe a class of algorithms for multilinear 0-1 programming based on these results. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1983
- Accession Number
- ADA150960
Entities
People
- E. Balas
- J. P. Mazzola
Organizations
- Carnegie Mellon University