A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints (Q761340)

The problem of locating plants and warehouses is considered, in which commodities are delivered to customers either directly from the plants or from intermediate warehouses. For each plant a set of adjunct warehouses is specified that must be open whenever the plant is open. No capacity constraints on the plants or warehouses are imposed. The objective is to minimize total cost which consists of fixed costs for opening plants and warehouses and shipment costs. A branch and bound algorithm is proposed the special features of which are the lower bounds and dominance rules obtained by exploiting the submodularity of the objective function and the relationship of plants to their adjunct warehouses. Computational results are reported for problems with 50 customers, with up to 10 possible plant locations and with up to 25 possible warehouse locations.