Accession Number:

ADA094190

Title:

Linearizing Nonlinear 0-1 Programs.

Descriptive Note:

Management sciences research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1980-10-01

Pagination or Media Count:

65.0

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 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE