Francisco Barahona, Ali Ridha Mahjoub
Discrete Mathematics
We study a prize-collecting version of the uncapacitated facility location problem and of the p-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the p-median and facility location problems studied in this paper. © 2011 Society for Industrial and Applied Mathematics.
Francisco Barahona, Ali Ridha Mahjoub
Discrete Mathematics
Mourad Baïou, Francisco Barahona, et al.
Mathematics of Operations Research
Mourad Baiou, Francisco Barahona
Networks
Francisco Barahona
SIAM Journal on Discrete Mathematics