(61d) Global Optimization Algorithm for Capacitated Multi-Facility Continuous Location-Allocation Problems
We propose an extension of the original CMWP that considers fixed cost for opening new facilities, fixed transportation costs, and two sets of fixed-location points: suppliers i and customers j . The latter goes back to the original Weber problem, in which the location of the facility had to be determined in relation to 2 suppliers and 1 customer. The model is a nonlinear Generalized Disjunctive Programming (GDP), reformulated as a nonconvex Mixed-Integer Nonlinear Programming (MINLP). This is, to the best of our knowledge, an original problem not reported before that has high practical applicability.
We develop a bilevel decomposition algorithm that consists of decomposing the problem into a master problem and a subproblem. The master problem is based on a relaxation of the nonconvex MINLP, which yields an MILP that predicts the selection of facilities and their links to suppliers and customers, as well as a lower bound on the cost of problem. The subproblem corresponds to a nonconvex NLP of reduced dimensionality that results from fixing the binary variables in the MINLP problem, according to the binary variables predicted in the MILP master problem. Based on the bounding properties of their subproblems, Îµ-convergence is proved for this algorithm.
We apply the proposed method to random instances varying from 2 suppliers and 2 customers to 40 suppliers and 40 customers, from one type of facility to 3 different types, and from 2 to 32 potential facilities. The results show that the algorithm is more effective at finding global optimal solutions than general purpose global optimization solvers tested.
 Brimberg, J., Hansen, P., Mladonovic, N., Salhi, S.: A survey of solution methods for the continuous location allocation problem. International Journal of Operational Research 5(1), 1â12 (2008).
 Cooper, L.: The transportation-location problem. Operations Research 20(1), 94-108 (1972).
 Sherali, A.D., Shetty, C.M.: The rectilinear distance location-allocation problem. A I I E Transactions 9(2), 136-143 (1977).
 Sherali, H.D., Tuncbilek, C.H.: A squared-euclidean distance location-allocation problem. Naval Research Logistics (NRL) 39(4), 447-469 (1992).
 Sherali, H.D., Al-Loughani, I., Subramanian, S.: Global optimization procedures for the capacitated Euclidean and lp distance multifacility location-allocation problems. Operations Research 50(3), 433-448 (2002).