Aarhus University Seal / Aarhus Universitets segl

A branch-and-bound algorithm for the capacitated facility location problem with convex production costs

Publikation: KonferencebidragKonferenceabstrakt til konferenceForskning

We consider the capacitated facility location problem (CFLP) with differentiable convex production cost functions. The problem arises in numerous real-world applications as queues in call-centres, serverqueueing or when production is pushed beyond normal capacity limits. For finding proven optimal solutions, we suggest a branch-and-bound algorithm based on Lagrangian relaxation and subgradient optimization. The algorithm basically extends a similar method for the classical linear cost CFLP to the convex cost case. The method is compared on a large number of test instances to three other exact solution approaches: The use of perspective cuts, a second-order cone (SOC) MIP formulation for the case of quadratic costs, and Benders’ decomposition. Our computational results indicate that in many case the branch-and-bound method is superior to both the perspective cut approach, the SOC MIP, and the application of Benders’ decomposition.
StatusUdgivet - 2017
BegivenhedOperations Research 2017: International Conference on Operations Research - Freie Universität Berlin, Berlin, Tyskland
Varighed: 6 sep. 20178 sep. 2017


KonferenceOperations Research 2017
LokationFreie Universität Berlin

Se relationer på Aarhus Universitet Citationsformater

ID: 119800084