A large class of facets for the K-median polytope |
| |
Authors: | Wenhui Zhao Marc E. Posner |
| |
Affiliation: | 1. Olin Business School, Washington University in St. Louis, 1 Brookings Dr, St. Louis, MO, 63130, USA 2. Department of Integrated Systems Engineering, The Ohio State University, 1971 Neil Avenue, Columbus, OH, 43210, USA
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|