A cut and branch approach for the capacitated p-median problem based on Fenchel cutting planes

A cut and branch approach for the capacitated p-median problem based on Fenchel cutting planes

0.00 Avg rating0 Votes
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: , , ,
Keywords: combinatorial optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.