On the relationship between disjunctive relaxations and minors in packing and covering problems

V. LEONI, G. NASINI

REVISTA DE LA UNIóN MATEMáTICA ARGENTINA

de la Universidad Nacional del Sur

Lugar: Bahía Blanca, Argentina; Año: 2005 vol. 46 p. 11 - 22

0041-6932

In 2002, Aguilera et al. analyzed theperformance of the disjunctive lift-and-project operator defined by Balas, Ceria andCornuéjols on covering and packing polyhedra, in the context ofblocking and antiblocking duality. Their results generalize Lovász´sPerfect Graph Theorem and a theorem of Lehman on ideal clutters.This study motivated many authors to work on the same ideas, providing alternative proofs and analyzing the behaviour of other lift-and-project operators in the same context. In this paper, we give a survey of the results in the subject and add some new results, showing that the key of the behaviour of the disjunctiveoperator on these particular classes of polyhedra is the strong relationshipbetween disjunctive relaxations and original relaxations associated to some minors.