Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort

In literature, single/multistage warehouse location problems have been attempted by Geoffrion and Graves [A.M. Geoffrion, G.W. Graves, Multicommodity distribution system design by Benders decomposition, Management Science 2 (1974) 82-114] and Sharma [R.R.K. Sharma, Modeling a fertilizer distribution system, European Journal of Operational Research 51 (1991) 24-34] among others and they have given completely different formulations. We use the formulation style given by Sharma and Sharma [R.R.K. Sharma, K.D. Sharma, A new dual based procedure for the transportation problem, European Journal of Operational Research 122 (3) (2000) 96-109] to develop variety of constraints that link real and 0-1 integer variables; thus developing many formulations of single stage capacitated warehouse location problem (SSCWLP). We relax the integer constraints on 0-1 variables to obtain their relaxations. Later we conduct an empirical investigation to find that there exist relaxations which give better bounds than the `strong' relaxation of SSCWLP. We also find that SSCWLP when formulated using the style due to Sharma [R.R.K. Sharma, Modeling a fertilizer distribution system, European Journal of Operational Research 51 (1991) 24-34] takes significantly less computational time for optimal solution compared to the time taken to reach optimality for the SSCWLP problems when formulated using the style due to Geoffrion and Graves [A.M. Geoffrion, G.W. Graves, Multicommodity distribution system design by Benders decomposition, Management Science 2 (1974) 82-114]. Finally we conducted an experimental investigation on 100 problems of SSCWLP problems each of sizes 25 x 25 x 25, 50 x 50 x 50 and 100 x 100 x 100 and this establishes that the effectiveness of 'capacity' constraints proposed in this paper is particularly strong. (c) 2006 Elsevier B.V. All rights reserved.