Accession Number : ADA019445

Title :   Lifting the Facets of 0-1 Polytopes.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Zemel,Eitan

Report Date : NOV 1974

Pagination or Media Count : 37

Abstract : In this report the author discusses a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general 0-1 program. The procedure starts with a given facet (valid inequality) defined on a lower dimensional set of solutions and characterizes all the full dimensional facets (valid inequalities) which can be obtained by lifting it. The procedure subsumes the previous results concerning lifting lower dimensional facets (valid inequalities) for 0-1 programs and obtains many new facets (valid inequalities) unobtained by other methods.

Descriptors :   *Linear programming, Convex sets, Inequalities, Integer programming, Theorems

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE