Aarhus University Seal / Aarhus Universitets segl

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

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Standard

A fast exact method for the capacitated facility location problem with differentiable convex production costs. / Christensen, Tue Rauff Lind ; Klose, Andreas.

I: European Journal of Operational Research, Bind 292, Nr. 3, 08.2021, s. 855-868.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Harvard

APA

CBE

MLA

Vancouver

Author

Christensen, Tue Rauff Lind ; Klose, Andreas. / A fast exact method for the capacitated facility location problem with differentiable convex production costs. I: European Journal of Operational Research. 2021 ; Bind 292, Nr. 3. s. 855-868.

Bibtex

@article{78db9e55ce0e41d0b6758741d6c964cf,
title = "A fast exact method for the capacitated facility location problem with differentiable convex production costs",
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.",
author = "Christensen, {Tue Rauff Lind} and Andreas Klose",
year = "2021",
month = aug,
doi = "10.1016/j.ejor.2020.11.048",
language = "English",
volume = "292",
pages = "855--868",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier BV",
number = "3",

}

RIS

TY - JOUR

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

AU - Christensen, Tue Rauff Lind

AU - Klose, Andreas

PY - 2021/8

Y1 - 2021/8

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

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

U2 - 10.1016/j.ejor.2020.11.048

DO - 10.1016/j.ejor.2020.11.048

M3 - Journal article

VL - 292

SP - 855

EP - 868

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -