Accession Number:

AD0781269

Title:

On Defining Sets of Vertices of the Hypercube by Linear Inequalities.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Jeroslow,R. G.

Report Date:

1974-04-01

Pagination or Media Count:

13.0

Abstract:

The paper shows that for any subset S of vertices of the n-dimensional hypercube, indS or 2 supn-1, where indS is the minimum number of linear inequalities needed to define S. Furthermore, for any k in the range 1 or k or 2 supn-1, there is an S with indS k, with the defining inequalities taken as canonical cuts. Other related results are included and all are proven by explicit constructions of the sets S or explicit definitions of such sets by linear inequalities. The paper is aimed at researchers in bivalent programming, since it provides upper bounds on the performance of algorithms which combine several linear constraints into one, even when the given constraints have a particularly simple form. Author

Descriptors:

• *Mathematical programming
• *Inequalities
• Convex sets
• Theorems

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE