An Improved Algorithm for the Capacitated Facility Location Problem

Journal of the Operational Research SocietyPublished 1 December 1978

Robert M. Nauss

DOI10.1057/jors.1978.263

Source URL

Citations122

SJR quartileQ1

SJR score0.92

SNIP1.26

TL;DR

A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala and results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required.

Abstract

In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.

Keywords

MathematicsBusiness, Management and AccountingEngineering

Mathematical ProgrammingValidation of subgradient optimization

1,366 Citations1974Michael Held, Philip Wolfe +1 more

It is concluded that the “relaxation” procedure for approximately solving a large linear programming problem related to the traveling-salesman problem shows promise for large-scale linear programming.

International series in management science/operations research/International series in operations research & management scienceMulticommodity Distribution System Design by Benders Decomposition * † ‡

983 Citations2010Arthur M. Geoffrion, G. W. Graves§

Lagrangian Relaxation for Integer Programming

978 Citations2009Arthur M. Geoffrion

It is a pleasure to write this commentary because it offers an opportunity to express my gratitude to several people who helped me in ways that turned out to be essential to the birth of [8].

Lecture notes in economics and mathematical systemsA Heuristic Program for Locating Warehouses

731 Citations1976Alfred A. Kuehn, Michael J. Hamburger

Management ScienceInteger Programming Algorithms: A Framework and State-of-the-Art Survey

353 Citations1972Arthur M. Geoffrion, Roy E. Marsten

A unifying framework is developed to facilitate the understanding of most known computational approaches to integer programming, and a number of currently operational algorithms are related to this framework.

Management ScienceAn Efficient Branch and Bound Algorithm for the Capacitated Warehouse Location Problem

244 Citations1977Umit Akinc, Basheer M. Khumawala

Management ScienceAn Efficient Algorithm for the 0-1 Knapsack Problem

124 Citations1976Robert M. Nauss

An efficient algorithm is presented for the 0-1 knapsack problem and the availability of a callable FORTRAN subroutine which solves this problem is announced.

Operations ResearchBranch-and-Bound and Approximate Solutions to the Capacitated Plant-Location Problem

109 Citations1969Graciano Sá

Empirical evidence is provided suggesting that the branch-and-bound method may be useful in problems of around 25 integer variables, perhaps more, depending on how tightly row-constrained the problem at hand is.