Journal article
Solving a selected class of location problems by exploiting problem structure: A decomposition approach
Naval research logistics, Vol.45(8), pp.791-815
12/1998
DOI: 10.1002/(SICI)1520-6750(199812)45:8<791::AID-NAV3>3.0.CO;2-H
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.
Details
- Title: Subtitle
- Solving a selected class of location problems by exploiting problem structure: A decomposition approach
- Creators
- Dilip Chhajed - University of Illinois Urbana-ChampaignTimothy J. Lowe - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Naval research logistics, Vol.45(8), pp.791-815
- DOI
- 10.1002/(SICI)1520-6750(199812)45:8<791::AID-NAV3>3.0.CO;2-H
- ISSN
- 0894-069X
- eISSN
- 1520-6750
- Publisher
- Wiley Subscription Services, Inc., A Wiley Company
- Number of pages
- 25
- Language
- English
- Date published
- 12/1998
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963116502771
Metrics
2 Record Views