A large class of facets for the \(K\)-median polytope (Q543406)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A large class of facets for the \(K\)-median polytope |
scientific article |
Statements
A large class of facets for the \(K\)-median polytope (English)
0 references
17 June 2011
0 references
The \(K\)-median problem is formulated as a minimization problem (IP) with 0-1 variables. Ignoring the integrality restrictions, one gets a linear relaxation whose polytope is not always integral. The authors develop an extended integral formulation (EP) of the original problem, with two sets of extra variables. The advantage is that an extreme point solution to (EP) is integral. This comes with a price: (EP) grows exponentially with the number of nodes. The authors proceed to project one of the sets of extra variables from the extended formulation. To this end, a result of [\textit{M. Goemans}, Notes, MIT, Cambridge (1992)] is employed. This requires a detailed study of inequalities associated to extreme directions of the projection cone. Using the reduced extended formulation, the authors establish basic properties of the facets of (IP) along the lines introduced by \textit{I. R. de Farias} [Oper. Res. Lett. 28, 161--167 (2001; Zbl 0992.90081)] and \textit{S. de Vries, M. E. Posner} and \textit{R. V. Vohra} [Math. Progr. 110, No. 2 (A), 261--285 (2007; Zbl 1130.90058)]. Inequalities introduced in this paper are facet-defining under weaker conditions than the published ones and compares favorably with their predecessors. The paper also contains a heuristic method that uses the new restrictions to separate a fractional extreme point from the integer hull of the polytope of (IP).
0 references
de Vries facets
0 references
de Faria facets
0 references
polyhedral description
0 references
extreme direction
0 references
projection cone
0 references