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

Andreas Klose

Abstract

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 language	English
Publication date	2017
Publication status	Published - 2017
Event	Operations Research 2017: International Conference on Operations Research - Freie Universität Berlin, Berlin, Germany Duration: 6 Sept 2017 → 8 Sept 2017 http://www.or2017.de/

Conference

Conference	Operations Research 2017
Location	Freie Universität Berlin
Country/Territory	Germany
City	Berlin
Period	06/09/2017 → 08/09/2017
Internet address	http://www.or2017.de/

Cite this

@conference{705cf0b6ed9f4a3a8a5dd56706facd3e,

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

abstract = "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{\textquoteright} 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{\textquoteright} decomposition.",

author = "Andreas Klose",

year = "2017",

language = "English",

note = "Operations Research 2017 : International Conference on Operations Research, OR2017 ; Conference date: 06-09-2017 Through 08-09-2017",

url = "http://www.or2017.de/",

}

TY - ABST

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

AU - Klose, Andreas

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.or2017.de/scientific-program/schedule/20171002_program_guide_book_of_abstracts.pdf

M3 - Conference abstract for conference

T2 - Operations Research 2017

Y2 - 6 September 2017 through 8 September 2017

ER -

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

Abstract

Conference

Other files and links

Fingerprint

Cite this