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

Research output: Contribution to conferenceConference abstract for conferenceResearch

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.
Original languageEnglish
Publication year2017
Publication statusPublished - 2017
EventOperations Research 2017: International Conference on Operations Research - Freie Universität Berlin, Berlin, Germany
Duration: 6 Sep 20178 Sep 2017


ConferenceOperations Research 2017
LocationFreie Universität Berlin
Internet address

See relations at Aarhus University Citationformats

ID: 119800084