A Cut and Branch Approach for the Capacitated p-Median Problem Based on Fenchel Cutting Planes |
| |
| Authors: | Maurizio Boccia Antonio Sforza Claudio Sterle Igor Vasilyev |
| |
| Affiliation: | (1) RCOST – Research Center on Software Technology, Università del Sannio, C.so Garibaldi 107, 82100 Benevento, Italy;(2) Dipartimento di Informatica e Sistemistica, Università degli Studi di Napoli “Federico II”, Via Claudio 21, 80125 Napoli, Italy;(3) Institute of System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences, Lermontov Srt., 134, 664033 Irkutsk, Russia |
| |
| Abstract: | 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. |
| |
| Keywords: | p-Median problem Cutting planes Fenchel cuts |
| 本文献已被 SpringerLink 等数据库收录！ |
|
