Article ID: | iaor20091373 |
Country: | United Kingdom |
Volume: | 7 |
Issue: | 1 |
Start Page Number: | 43 |
End Page Number: | 58 |
Publication Date: | Mar 2008 |
Journal: | Journal of Mathematical Modelling and Algorithms |
Authors: | Sforza Antonio, Boccia Maurizio, Sterle Claudio, Vasilyev Igor |
Keywords: | combinatorial optimization |
The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.