Discretized formulations for capacitated location problems with modular distribution costs
In this paper we study a discretization reformulation technique in the context of a facility location problem with modular link costs. We present a so-called 'traditional' model and a straightforward discretized model with a general objective function whose variable coefficients are computed by solving a simple knapsack problem. We show that the linear programming relaxation of the discretized model dominates the linear programming relaxation of the original model. The discretized model suggests quite intuitive valid inequalities that considerably improve the linear programming relaxation of the original model. Computational results based on randomly generated data show that in the context of problems with modular costs, the proposed discretized models perform significantly better than the 'traditional' models. An important outcome of our research is the result, whose proof is also presented in this paper, that a restricted version of the discretized model gives an extended description of the convex hull of the integer solutions of a subproblem that usually arises in network design problems with modular costs.
Year of publication: |
2010
|
---|---|
Authors: | Correia, Isabel ; Gouveia, Luís ; Saldanha-da-Gama, Francisco |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 204.2010, 2, p. 237-244
|
Publisher: |
Elsevier |
Keywords: | Capacitated facility location Modular link costs Extended reformulations |
Saved in:
Saved in favorites
Similar items by person
-
Correia, Isabel, (2010)
-
Solving the variable size bin packing problem with discretized formulations
Correia, Isabel, (2008)
-
Discretized formulations for capacitated location problems with modular distribution costs
Correia, Isabel, (2010)
- More ...