A Decomposition Algorithm for a Discrete Location-Allocation Problem

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1984-07, Vol.32 (4), p.878-900
Main Authors: Sherali, Hanif D, Adams, Warren P
Format: Article
Language:English
Subjects:
185 location/allocation problem
625 discrete bilinear program
Algorithms
Allocations
Applied sciences
Exact sciences and technology
Incumbents
Integers
Lagrangian function
Linear programming
Location analysis
Management science
Miscellaneous
Operational research and scientific management
Operational research. Management science
Optimal solutions
Supply
Theory
Transportation
Transportation costs
Warehouses
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.32.4.878