A branch-and-bound algorithm for the multi-level uncapacitated facility location problem (Q795714)

Consider a distribution system with origin-level facilities, sets \(I_ k (k=1,...,K)\) of intermediate level facilities and a set J of destinations. The problem of determining an optimal set I of intermediate level facilities to open which minimizes the total distribution costs including the fixed costs associated with opening them is discussed. If P is the set of all facility paths \(p=(i_ 1,...,i_ k) (i_ k\in I_ k)\), c(p,j) is the cost of shipping one unit to destination j via path p, and f(i) is the fixed cost for establishing facility i, then the problem may be formulated as follows: \[ \min imize\quad \sum_{j\in J}\sum_{p\in P}c(p,j)x(p,j)+\sum^{K}_{k=1}\sum_{i\in I_ k}f(i)y(i) \] subject to \(\sum_{p\in P}x(p,j)=1\) (\(j\in J)\), \(0\leq x(p,j)\leq y(i)\) (\(i\in p\), \(p\in P\), \(j\in J)\), \(y(i)\in \{0,1\}\) (\(i\in p\in P)\). In this formulation x(p,j) is the fraction of the demand in destination j shipped to j via path p and \(y(i)=1\) if and only if facility i is opened. A branch-and-bound procedure is given which uses a dual ascent procedure and a primal descent procedure for generating lower and upper bounds, as well as a node simplification procedure. Computational results are reported for \(K=2\) and \(K=3\).