Abstract
The problem of characterizing extreme points of a family of polyhedra is considered. This family embraces a variety of linear relaxations of feasible regions of discrete location problems. After characterizing the extreme points by means of a homogeneous system of linear equations, we obtain, as particular cases, four problems which have already been treated from a polyhedral point of view in the literature. Finally, we show that our characterization improves the one known for the Simple Plant Location Problem and corrects the one established for the Two-Level Uncapacitated Facility Location Problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal K., Labbé M., Leung J. and Queyranne M. (1996). On the Two-Level Uncapacitated Facility Location Problem.INFORMS Journal on Computing 8, 289–301.
Caprara A. and Salazar J.J. (1996). A Branch-and-Cut Algorithm for a Generalization of the Uncapacitated Facility Location Problem.Top 4, 135–163.
Cho D.C., Johnson E.L., Padberg M.W. and Rao M.R. (1983a). On the Uncapacitated Plant Location Problem I: Valid Inequalities and Facets.Mathematical Methods of Operational Research 8, 579–589.
Cho D.C., Padberg M.W. and Rao M.R. (1983b). On the Uncapacitated Plant Location Problem II: Facets and Lifting Theorems.Mathematical Methods of Operational Research 8, 590–612.
Cornuéjols G., Fisher M. and Nemhauser G.L. (1977). On the Uncapacitated Location Problem.Annals of Discrete Mathematics 1, 163–177.
Cornuéjols G. and Thizy J.M. (1982). Some facets of the Simple Plant Location Polytope.Mathematical Programming 23, 50–74.
Guignard M. (1980). Fractional Vertices, Cuts and Facets of the Simple Plant Location Problem.Mathematical Programming 12, 150–162.
Krarup J. and Pruzan P.M. (1983). The Simple Plant Location Problem: Survey and Synthesis.European Journal of Operational Research 12, 36–81.
Leung J. and Magnanti T.L. (1989). Valid Inequalities and Facets of the Capacitated Plant Location Problem.Mathematical Programming 44, 271–291.
Nemhauser G.L. and Trotter L.E. (1974). Properties of Vertex Packing and Independence System PolyhedraMathematical Programming 6, 48–61.
Author information
Authors and Affiliations
Additional information
The first and third authors were supported by Fundación Séneca, project PB/11/FS/97
Rights and permissions
About this article
Cite this article
Cánovas, L., Marín, A. & Landete, M. Extreme points of discrete location polyhedra. Top 9, 115–138 (2001). https://doi.org/10.1007/BF02579074
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02579074