Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type

0.00 Avg rating0 Votes
Article ID: iaor20001378
Country: Netherlands
Volume: 115
Issue: 2
Start Page Number: 285
End Page Number: 299
Publication Date: Jun 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer, programming: branch and bound, heuristics
Abstract:

This paper presents exact and heuristic solution procedures for a multiproduct capacitated facility location (MPCFL) problem in which the demand for a number of different product families must be supplied from a set of facility sites, and each site offers a choice of facility types exhibiting different capacities. MPCFL generalizes both the uncapacitated (or simple) facility location (UFL) problem and the pure-integer capacitated facility location problem. We define a branch-and-bound algorithm for MPCFL that utilizes bounds formed by a Lagrangian relaxation of MPCFL which decomposes the problem into UFL subproblems and easily solvable 0–1 knapsack subproblems. The UFL subproblems are solved by the dual-based procedure of Erlenkotter. We also present a subgradient optimization-Lagrangian relaxation-based heuristic for MPCFL. Computational experience with the algorithm and heuristic are reported. The MPCFL heuristic is seen to be extremely effective, generating solutions to the test problems that are on average within 2% of optimality, and the branch-and-bound algorithm is successful in solving all of the test problems to optimality.

Reviews

Required fields are marked *. Your email address will not be published.