Discretized formulations for capacitated location problems with modular distribution costs

Isabel Correia, Luís Gouveia, Francisco Saldanha-da-Gama

Research output: Contribution to journalArticle

21 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)237-244
Number of pages8
JournalEuropean Journal of Operational Research
Volume204
Issue number2
DOIs
Publication statusPublished - 16 Jul 2010

Keywords

  • Capacitated facility location
  • Extended reformulations
  • Modular link costs

Fingerprint Dive into the research topics of 'Discretized formulations for capacitated location problems with modular distribution costs'. Together they form a unique fingerprint.

  • Cite this