Accession Number:

AD1021104

Title:

On the Rank of Mixed 0,1 Polyhedra

Descriptive Note:

Journal Article

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA PITTSBURGH United States

Personal Author(s):

Report Date:

2001-07-01

Pagination or Media Count:

9.0

Abstract:

For a polytope in the 0 1n cube, Eisenbrand and Schulz showed recently that the maximum Chvatal rank is bounded above by On2logn and bounded below by 1 e n for some e 0. Chvatal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE