A fast exact method for the capacitated facility location problem with differentiable convex production costs

Tue Rauff Lind Christensen and Andreas Klose

European Journal of Operational Research, 2021, vol. 292, issue 3, 855-868

Abstract: This paper considers the capacitated facility location problem with convex and differentiable production costs functions, an optimization problem that finds numerous real-world applications such as queues in call-centers, server queuing or when production is pushed beyond normal capacity limits leading to over proportional growth in production costs. As opposed to most other solution methods for this and similar problems, we propose an exact method that instead of linearizing the cost functions deals directly with the nonlinear costs. To this end, we use a Lagrangian relaxation of the demand constraints leading to a Lagrangian subproblem with a nonlinear objective function. The Lagrangian dual is (approximately) solved by means of subgradient optimization. Proven optimal solutions to the facility location problem are then found by employing this lower bounding scheme in a branch and bound algorithm. We use this method for solving a large number of test problem instances with production costs that either follow a quadratic or an inverse cost function. Our computational experiments show that the proposed solution method is in most cases superior to other solution methods for this problem.

Keywords: Location; Integer programming; Nonlinear programming; Branch and bound (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720310079
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:292:y:2021:i:3:p:855-868

DOI: 10.1016/j.ejor.2020.11.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().