A large class of facets for the K-median polytope
成果类型：
Article
署名作者：
Zhao, Wenhui; Posner, Marc E.
署名单位：
Washington University (WUSTL); University System of Ohio; Ohio State University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-009-0301-x
发表日期：
2011
页码：
171-203
关键词：
摘要：
The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant.