Test problem generator for the multidimensional assignment problem. (English) Zbl 1066.90061
Summary: The multidimensional assignment problem (MAPs) is a higher dimensional version of the standard linear assignment problem. Test problems of known solution are useful in exercising solution methods. A method of generating an axial MAP of controllable size with a known unique solution is presented. Certain characteristics of the generated MAPs that determine realism and difficulty are investigated.
MSC:
| 90B80 | Discrete location and assignment |
References:
| [1] | R.M. Aiex, M.G.C. Resende, P.M. Pardalos, and G. Toraldo, ”GRASP with path relinking for the three-index assignment problem” Technical Report, AT&T Labs Research, Florham Park, NJ 07733, 2001. · Zbl 1239.90087 |
| [2] | E. Balas and M.J. Saltzman, ”An algorithm for the three-index assignment problem” Operations Research, vol. 39, pp. 150–161, 1991. · Zbl 0743.90079 · doi:10.1287/opre.39.1.150 |
| [3] | J.E. Beasley, ”OR-Library: Distributing test problems by electronic mail” Journal of the Operational Research Society, vol. 41, no. 11, pp. 1069–1072, 1990. |
| [4] | J.E. Beasley, OR-Library, http://www.ms.ic.ac.uk/info.html. |
| [5] | R.E. Burkard, ”Selected topics on assignment problems” Discrete Applied Mathematics, vol. 123, pp. 257–302, 2002. · Zbl 1036.90056 · doi:10.1016/S0166-218X(01)00343-2 |
| [6] | R.E. Burkard, E. Çela, S.E. Karisch, and F. Rendlqaplib, A Quadratic Assignment Problem Library, http://www.opt.math.tu-graz.ac.at/qaplib/. |
| [7] | R.E. Burkard, R. Rudolf, and G.J. Woeginger, ”Three-dimensional axial assignment problems with decomposible cost coefficients” Discrete Applied Mathematics, vol. 65, pp. 123–139, 1996. · Zbl 0846.90090 · doi:10.1016/0166-218X(95)00031-L |
| [8] | Y. Crama and F.C.R. Spieksma, ”Approximation algorithms for three-dimensional assignment problems with triangle inequalities” European Journal of Operational Research, vol. 60, pp. 273–279, 1992. · Zbl 0761.90071 · doi:10.1016/0377-2217(92)90078-N |
| [9] | C.A. Floudas, P.M. Pardalos, C.S. Adjiman, W.R. Esposito, Z.H. Gms, S.T. Harding, J.L. Klepeis, C.A. Meyer, and C.A. Schweiger, Handbook of Test Problems in Local and Global Optimization, Kluwer, Dordrecht, Netherlands, 1999. · Zbl 0943.90001 |
| [10] | A.M. Frieze and J. Yadegar, ”An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice” Journal of Operational Research Society, vol. 32, pp. 989–995, 1981. · Zbl 0464.90055 |
| [11] | M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman: New York, 1979. · Zbl 0411.68039 |
| [12] | E.E. Lewis, Introduction to Reliability Engineering, 2nd ediition, John Wiley and Sons: New York, 1996, pp. 25–30. |
| [13] | D. Magos and P. Miliotis, ”An algorithm for the planar three-index assignment problem” European Journal of Operational Research, vol. 77, pp. 141–153, 1994. · Zbl 0810.90093 · doi:10.1016/0377-2217(94)90034-5 |
| [14] | R. Murphey, P. Pardalos, and L. Pitsoulis, ”A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem” in DIMACS Series, vol. 40, American Mathematical Society, 1998, pp. 277–302. · Zbl 0903.90178 |
| [15] | P. Pardalos and L. Pitsoulis (Eds.), Nonlinear Assignment Problems, Algorithms and Applications, Kluwer: Dordrecht, 2000, pp. 1–12. · Zbl 1029.90036 |
| [16] | W. Pierskalla, ”The multidimensional assignment problem” Operations Research, vol. 16, pp. 422–431, 1968. · Zbl 0164.50003 · doi:10.1287/opre.16.2.422 |
| [17] | A. Poore and N. Rijavec, ”A lagrangian relaxation algorithm for multidimensional assignment problems arising from multitarget tracking” Society of Industrial and Applied Mathmatics Journal on Optimization, vol. 3, pp. 544–563, 1993. · Zbl 0799.90092 |
| [18] | J. Pusztaszeri, P.E. Rensing, and T.M. Liebling, ”Tracking elementary particles near their primary vertex: A combinatorial approach.” Journal of Global Optimization, vol. 16, pp. 422–431, 1995. · Zbl 0860.90130 |
| [19] | L. Yong and P.M. Pardalos, ”Generating quadratic assignment test problems with know optimal permutations” Computational Optimization and Applications, vol. 1, no. 2, pp. 163–184, 1992. · Zbl 0773.90083 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
