Two algorithms for the multi-Weber problem (Q1417702)

The paper discusses a subproblem occuring in the first stage of an algorithm of \textit{K. E. Rosing} [Eur. J. Oper. Res. 58, 414--426 (1992; Zbl 0760.90064)] for the exact solution of the multi-Weber problem (location-allocation problem): Find all ``valid'' subsets of a finite set of existing facilities in the plane such that no other existing facility is contained in the convex hull of that subset. Two basic strategies for the complete enumeration of all valid subsets are presented. The first method is based on the repeated addition of one existing facility at a time to a pre-existing valid subset, using backtracking to ensure complete enumeration. The second method enumerates all convex polygons and their convex hulls which can be formed out of the existing facilities.