The uncapacitated facility location problem with client matching

The Uncapacitated Facility Location Problem,vith Client Matching (LCM) is a n extension of the Uncapacitated Facility Location Problem (UFLP), where tw o clients allocated to a facility can be matched. As in the UFLP, facilitie s can be opened at any of m predefined locations with given fixed costs, an d n clients have to be allocated to the open facilities. In classical locat ion models, the allocation cost is the distance between a client and an ope n facility. In the LCM, the allocation cost is either the cost of a return trip between the facility and the client, or the length of a tour containin g the facility and two clients. The similarities of the LCM with the classi cal UFLP and the matching problem are exploited to derive valid inequalitie s, optimality cuts, and polyhedral results. A greedy heuristic and a branch -and-cut algorithm are developed, and several separation procedures are des cribed. Computational experiments confirm the efficiency of the proposed ap proach.