A tighter formulation of the p-median problem |
| |
Authors: | Sourour Elloumi |
| |
Affiliation: | 1.CEDRIC-CNAM,Paris,France |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|