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.