The discrete facility location problem with balanced allocation of customers
We consider a discrete facility location problem where the difference between the maximum and minimum number of customers allocated to every plant has to be balanced. Two different Integer Programming formulations are built, and several families of valid inequalities for these formulations are developed. Preprocessing techniques which allow to reduce the size of the largest formulation, based on the upper bound obtained by means of an ad hoc heuristic solution, are also incorporated. Since the number of available valid inequalities for this formulation is exponential, a branch-and-cut algorithm is designed where the most violated inequalities are separated at every node of the branching tree. Both formulations, with and without the improvements, are tested in a computational framework in order to discriminate the most promising solution methods. Difficult instances with up to 50 potential plants and 100 customers, and largest easy instances, can be solved in one CPU hour.
Year of publication: |
2011
|
---|---|
Authors: | Marín, Alfredo |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 210.2011, 1, p. 27-38
|
Publisher: |
Elsevier |
Keywords: | Allocation Facility location Integer Programming Branch-and-cut |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Extreme points of discrete location polyhedra
Cánovas, Lázaro, (2001)
-
New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem
García, Sergio, (2012)
-
Closest assignment constraints in discrete location problems
Espejo, Inmaculada, (2012)
- More ...