An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge (Q2307752)

The single facility minisum location problem asks for a site minimizing the weighted sum of distances to given customer points. When the distance is expressed by a norm (or gauge) and the site is constrained to lie in a closed convex set, a novel algorithm of alternating direction of multipliers (ADMM) type is proposed involving at each iteration some Euclidean projection on the constraint set and another on the gauge's unit ball. This is well defined at any starting point, contrary to other methods such as Weiszfeld's or Newton-bracketing, that are often advocated for unconstrained problems with Euclidean distance. Convergence to optimality is proven under the unstated assumption that the optimal solution is unique. Some computational evidence is offered that it firstly outperforms these two classical methods when they apply, and secondly that it converges rather quickly when constrained within a circular region and for a distance defined by \(l_1\), \(l_2\), \(l_\infty\) or an asymmetric elliptic gauge. (That uniqueness at optimality is not guaranteed in the first and third case is ignored.) For the multifacility location-allocation (or multi-source Weber) problem, possibly with different convex constraints on each facility site, it is then proposed to apply the well-known method of Cooper which alternates between an allocation to the nearest facility phase and a location phase that decomposes into one single facility location problem for each facility, solved by way of previous ADMM method. Similar computational results are exhibited.