A Decomposition Algorithm for a Discrete Location-Allocation Problem

Hanif D. Sherali and Warren P. Adams
Additional contact information
Hanif D. Sherali: Virginia Polytechnic Institute and State University, Blacksburg, Virginia
Warren P. Adams: Virginia Polytechnic Institute and State University, Blacksburg, Virginia

Operations Research, 1984, vol. 32, issue 4, 878-900

Abstract: This paper considers a discrete location-allocation problem for simultaneously determining the location of a given number of capacitated facilities on certain predesignated sites, and the allocation of their products among a fixed number of customers. The objective is to determine the location and (subsequent) allocation that minimizes the total cost of construction (or location), production, and transportation. The formulation of this model is a specially structured, generally nonconvex problem. However, we specify certain sufficient conditions for the solution to two network-structured linear programs to provide an optimal solution to this problem. For other situations, we present an implicit enumeration algorithm within the framework of Benders' decomposition method, which fully exploits the structure of the problem. This method is an improvement over traditional Lagrangian approaches. Computational experience is provided to demonstrate the practicality of this algorithm for reasonable size problems, as well as its superiority over alternative implicit enumeration schemes. This paper also sheds light on the general implementation of Benders' decomposition technique.

Keywords: 185 location/allocation problem; 625 discrete bilinear program (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.4.878 (application/pdf)

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:inm:oropre:v:32:y:1984:i:4:p:878-900

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().