Premium
A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint
Author(s) -
Klose A.
Publication year - 1998
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1998.tb00111.x
Subject(s) - subgradient method , facility location problem , branch and bound , mathematical optimization , 1 center problem , backtracking , linear programming relaxation , bounding overwatch , relaxation (psychology) , mathematics , branch and cut , heuristics , computer science , algorithm , integer programming , psychology , social psychology , artificial intelligence
In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p‐median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p ‐median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump‐backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.