'Multidimensional' extensions and a nested dual approach for the m-median problem (Q1072925)

A generalization to ''multiple dimensions'' is introduced for the median- type location problem. This covers the following situations: (i) the travel costs and demands are stochastic, (ii) one considers multiple commodities or services, or (iii) multiple ''minisum-type'' objectives are present. The underlying network is referred to as the ''multidimensional network'' or, if the vectors are not deterministic, ''stochastic multidimensional network''. The 0-1 decision variables are the usual \(y_ i\) (equal to 1 iff a facility is established at site \(v_ i)\) and the more general \(x_{ijk}\) (equal 1 iff the demands at \(v_ j\) are serviced by a facility at \(v_ i\), when the network is in dimension k). Index k denotes a ''dimension'' of the network, which refers to a probabilistic state for stochastic networks, or a commodity for multicommodity networks. The authors first present a transformation of variables which maps any multidimensional m-median problem into a classical m-median problem with a larger node set. They then dualize the problem with respect to the m- median constraint using a dual multiplier f, and solve the Lagrangean dual by a dual simplex procedure (to determine the optimal value of f). The Lagrangean subproblems are solved by Erlenkotter's dual-based method. This nested procedure gives its name to the authors' approach. Computational experience with several examples is summarized and computational results for large scale problems are reported. Another possible application is to perform sensitivity analysis on m-median problems when travel costs are only estimated.