A nested partitions framework for solving large-scale multicommodity facility location problems

Abstract

Large-scale multicommodity facility location problems are generally intractable with respect to standard mixed-integer programming (MIP) tools such as the direct application of general-purpose Branch & Cut (BC) commercial solvers i.e. CPLEX. In this paper, the authors investigate a nested partitions (NP) framework that combines meta-heuristics with MIP tools (including branch-and-cut). We also consider a variety of alternative formulations and decomposition methods for this problem class. Our results show that our NP framework is capable of efficiently producing very high quality solutions to multicommodity facility location problems. For large-scale problems in this class, this approach is significantly faster and generates better feasible solutions than either CPLEX (applied directly to the given MIP) or the iterative Lagrangian-based methods that have generally been regarded as the most effective structure-based techniques for optimization of these problems. We also briefly discuss some other large-scale MIP problem classes for which this approach is expected to be very effective.

Keywords

Optimization / metaheuristics / mixed integer programming

References

[1] Aardal K.. Capacitated facility location: Separation algorithms and computational experience. Mathematical Programming, 1998, 81: 149-175.

[2] Beasley J.. Lagrangian heuristics for location problems. European Journal of Operational Research, 1993, 65: 383-399.

[3] Bramel, J. and D. Simchi-Levi, The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, Springer Series in Operations Research, 1997.

[4] Crainic T., Toulouse M., Gendreau M.. Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements. Annals of Operations Research, 1996, 63: 277-299.

[5] Delaney R.. 14th Annual State of Logistics Report, June 2, 2003, Washington, D. C.: National Press Club

[6] Delmaire H., Daz J., Fernndez E.. Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem. INFOR, Canadian Journal of Operational Research and Information Processing, 1999, 37(3): 194-225.

[7] D’souza, W., R. Meyer, S. Naqvi, and L. Shi, “Beam orientation optimization in imrt using single beam characteristics and mixed-integer formulations”, AAPM Annual Meeting, San Diego, 2003.

[8] Fisher M.. The Lagrangian relaxation method for solving integer programming problems. Management Sciences, 1981, 27: 1-18.

[9] Geoffrion A., Graves G.. Multicommodity distribution system design by benders decomposition. Management Science, 1974, 20: 822-844.

[10] Hindi K., Basta T.. Computationally efficient solution of a multiproduct, two-stage distribution-location problem. Journal of the Operational Research Society, 1994, 45: 1316-1323.

[11] Hindi K., Basta T., Pienkosz K.. Efficient solution of a multi-commodity, two-stage distribution problem with constraints on assignment of customers to distribution centers. International Transactions in Operations Research, 1998, 5(6): 519-528.

[12] Klincewicz J., Luss H.. A Lagrangian relaxation heuristic for capacitated facility location with single-source constraints. Journal of Operational Research Society, 1986, 37: 495-500.

[13] Klose A.. A Lagrangean relax-and-cut approach for the two-stage capacitated facility location problem. European Journal of Operational Research, 2000, 126: 408-421.

[14] Klose, A. and A. Drexl, “Facility location models for distribution system design”, European Journal of Operational Research, In Press, Corrected Proof, Available online 15 January 2004, 2003.

[15] Lee C.. A cross decomposition algorithm for a multiproduct-multitype facility location problem. Computers and Operations Research, 1993, 20: 527-540.

[16] Lovsz, L., “Randomized algorithms in combinatorial optimization”, Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, pp153–179, 1996.

[17] Mathar R., Niessen T.. Optimum positioning of base stations for cellular radio networks. Wireless Networks, 2000, 6(6): 421-428.

[18] Mazzola J., Neebe A.. Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type. European Journal of Operational Research, 1999, 115: 285-299.

[19] Mirchandani, P. and R. Francis, Discrete Location Theory, John Wiley and Sons, Inc., 1990.

[20] Mitchell, J., “Branch-and-cut algorithms for combinatorial optimization problems”, to appear in the Handbook of Applied Optimization, Oxford University Press, 2000.

[21] Neebe A., Rao M.. An algorithm for the fixed-charge assigning users to sources problem. Journal of Operational Research Society, 1983, 34: 1107-1113.

[22] Pirkul H., Jayaraman V.. Production, transportation, and distribution planning in a multi-commodity tri-echelon system. Transportation Sciences, 1996, 30(4): 291-302.

[23] Santos, C., X. Zhu, and H. Crowder, A mathematical optimization approach for resource allocation in large scale data centers, Technical Report HPL-2002-64 (R.1), Intelligent Enterprise Technologies Laboratory HP Laboratories Palo Alto, http://www.hpl.hp.com/techreports/2002/ HPL-2002-64R1.pdf, 2002.

[24] Shi L., Ólafsson S.. Nested partitions method for global optimization. Operations Research, 2000, 48: 390-407.

[25] Simchi-Levi, D., P. Kaminsky, and E. Simchi-Levi, Designing and Managing the Supply Chain, Irwin McGraw-Hill, 2000.

[26] Wolsey, L., Integer Programming, John Wiley & Sons, Inc., 1998.