Linearizing Nonlinear 0-1 Programs.

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1980
Accession Number
ADA094190

Entities

People

  • Egon Balas
  • Joseph B. Mazzola

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Contracts
  • Coverings
  • Inequalities
  • Iterations
  • Linear Programming
  • Linear Systems
  • Military Research
  • Notation
  • Numbers
  • Permutations
  • Preprocessing
  • Real Numbers
  • Sequences

Fields of Study

  • Mathematics

Readers

  • Operations Research