Linearizing Nonlinear 0-1 Programs.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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 set of generalized covering inequalities defined by Granot and Hammer. Several results concerning the relative strengths of inequalities within this family are presented. An algorithm for the general multilinear 0-1 program is given, and computational experience with the algorithm applied to randomly generated problems is discussed. The use of the general procedure as an effective heuristic for multilinear 0-1 programs is also demonstrated. Author
- Theoretical Mathematics