A tighter formulation of the p-median problem

A tighter formulation of the p-median problem

0.00 Avg rating0 Votes
Article ID: iaor2010175
Volume: 19
Issue: 1
Start Page Number: 69
End Page Number: 83
Publication Date: Jan 2010
Journal: Journal of Combinatorial Optimization
Authors:
Keywords: programming: integer
Abstract:

Given a set of clients and a set of potential sites for facilities, the p-median problem consists of opening a set of p sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem by a mixed integer linear problem. We show that this formulation, while it has the same value by LP-relaxation, can be much more efficient than two previous formulations. The computational experiment performed on two sets of benchmark instances has showed that the efficiency of the standard branch-and-cut algorithm has been significantly improved. Finally, we explore the structure of the new formulation in order to derive reduction rules and to accelerate the LP-relaxation resolution.

Reviews

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