Discretized Formulations for capacitated location models with variable distribution costs
by
Isabel Correia, Luís Gouveia & Francisco Saldanha-da-Gama
Department of Mathematics/Applied Mathematics Center, Faculty of Science and Technology, New University of Lisbon; Department of Statistics and Operational Research/Operational Research Center, Faculty of Science, University of Lisbon

In this paper we consider a discrete capacitated location problem in which there is a maximum amount that can be shipped from each location to each demand point. We consider modular distribution costs depending on the amount shipped.

In ‘classical’ location models a set of variables x_ij is usually considered indicating the amount shipped from location i to demand point j. In this talk we propose and discuss a model using discretized binary variables z^q_ij indicating whether or not facility i sends exactly q units to demand point j. We show that in the case of modular costs, the reformulated model may provide better linear programming bounds than the classical model. Using the ‘new’ allocation variables we propose new valid inequalities for improving the linear programming relaxation bound. We present the computational tests showing that the valid inequalities proposed enhance the linear programming relaxation bound and may be extremely helpful when using a commercial package for solving the problem optimality.

Keywords: Discrete location, Extended formulations

Date received: May 12, 2006