Solving a selected class of location problems by exploiting problem structure: A decomposition approach

Dilip Chhajed and Timothy J. Lowe

Naval Research Logistics (NRL), 1998, vol. 45, issue 8, 791-815

Abstract: For many combinatorial optimization problems that are NP‐hard, a number of special cases exist that can be solved in polynomial time. This paper addresses the issue of solving one such problem, the well‐known m‐median problem with mutual communication (MMMC), by exploiting polynomially solvable special cases of the problem. For MMMC, a dependency graph is defined that characterizes the structure of the interactions between decision variables. A Lagrangian decomposition scheme is proposed that partitions the problem into two or more subproblems, each having the same structure as the original problem, but with simpler dependency graphs. The dual problems are solved using subgradient or multiplier adjustment methods. An efficient method of adjusting the multiplier values is given. Computational results are reported that show the method to be quite effective. In addition, applications of the approach to other difficult location problems is discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 791–815, 1998

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199812)45:83.0.CO;2-H

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:wly:navres:v:45:y:1998:i:8:p:791-815

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().