FACET OBTAINING PROCEDURES FOR SET PACKING PROBLEMS

摘要

New results concerning the facial structure of set packing polyhedra are presented. In particular, new methods are given to obtain facets from the subgraphs of the intersection graph associated with a set packing polyhedron that properly subsume several other methods in the literature. A new class of facet defining graphs, termed fans, is also introduced, as well as a procedure to link any graph to a certain claw K_(1,κ) in order to obtain a new graph and an associated facet.