Solution approaches to the Three-Index Assignment Problem

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 2, March-April 2025


Page(s)		1035 - 1065
DOI		https://doi.org/10.1051/ro/2024140
Published online		09 April 2025

L.G. Afraimovich and M.D. Emelin, Combining solutions of the axial assignment problem. Autom. Remote Control 82 (2021) 1418–1425. [CrossRef] [MathSciNet] [Google Scholar]
L.G. Afraimovich and M.D. Emelin, Complexity of solutions combination for the three-index axial assignment problem. Mathematics 10 (2022) 1062. [CrossRef] [Google Scholar]
G. Appa, D. Magos and I. Mourtos, On multi-index assignment polytopes. Linear Algebra Appl. 416 (2006) 224–241. [CrossRef] [MathSciNet] [Google Scholar]
A. Arora, Multiple alignment of protein interaction networks by three-index assignment algorithm, MSc. thesis in Computer Science, University of Windsor, Ontario, Canada (2013). [Google Scholar]
E. Balas and L. Qi, Linear-time separation algorithms for the three-index assignment polytope. Discrete Appl. Math. 43 (1993) 1–12. [CrossRef] [MathSciNet] [Google Scholar]
E. Balas and P.R. Landweer, Traffic assignment in communication satellites. Oper. Res. Lett. 2 (1983) 141–147. [CrossRef] [Google Scholar]
E. Balas and M.J. Saltzman, Facets of the three-index assignment polytope. Discrete Appl. Math. 23 (1989) 201–229. [CrossRef] [MathSciNet] [Google Scholar]
E. Balas and M.J. Saltzman, An algorithm for the three-index assignment problem. Oper. Res. 39 (1991) 150–161. [CrossRef] [MathSciNet] [Google Scholar]
R.E. Burkard, R. Rudolf and G.J. Woeginger, Three-dimensional axial assignment problems with decomposable cost coefficients. Discrete Appl. Math. 65 (1996) 123–139. [CrossRef] [MathSciNet] [Google Scholar]
Y. Crama and F.C.R. Spieksma, Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur. J. Oper. Res. 60 (1992) 273–279. [CrossRef] [Google Scholar]
T. Dokka, A.N. Letchford and M.H. Mansoor, Using surrogate relaxation as a matheuristic. Internal report, Department of Management Science, Lancaster University, Lancaster, UK (2021). [Google Scholar]
T. Dokka and F.C.R. Spieksma, Facets of the axial three-index assignment polytope. Discrete Appl. Math. 201 (2016) 86–104. [CrossRef] [MathSciNet] [Google Scholar]
T. Dokka, Y. Crama and F.C.R. Spieksma, Multi-dimensional vector assignment problems. Discrete Optim. 14 (2014) 111–125. [CrossRef] [MathSciNet] [Google Scholar]
R. Euler, Odd cycles and a class of facets of the axial 3-index assignment polytope. Appl. Math. 19 (1987) 375–386. [Google Scholar]
S. Faudzi, S. Abdul-Rahman and R. Abd Rahman, An assignment problem and its application in education domain: a review and potential path, Hindawi (2018). DOI: 10.1155/2018/8958393. [Google Scholar]
A.M. Frieze and J. Yadegar, An algorithm for solving 3-dimensional assignment problems with application to scheduling a teaching practice. J. Oper. Res. Soc. 32 (1981) 989–995. [CrossRef] [Google Scholar]
B. Gabrovšek, T. Novak, J. Povh, D.R. Poklukar and J. Žerovnik, Multiple Hungarian method for k-assignment problem. Mathematics 8 (2020) 2050. [CrossRef] [Google Scholar]
M.R. Garey and D.S. Johnson, Computers and Intractability. Freeman, San Francisco (1979). [Google Scholar]
H. Gauvrit, J. Le Cadre and C. Jauffret, formulation of multitarget tracking as an incomplete data problem. IEEE Trans. Aerosp. Electron. Syst. 33 (1997) 1242–1257. [CrossRef] [Google Scholar]
D. Grundel, R. Murphey, P.M. and Pardalos, Theory and Algorithms for Cooperative Systems. World Scientific, River Edge (2004). [CrossRef] [Google Scholar]
Gurobi (2024). https://www.gurobi.com/. [Google Scholar]
J. He, S. Zhang, Z. Ren, X. Lai and Y. Piao, Approximate muscle guided beam search for three-index assignment problem. In: Proceedings of the 5th International Conference on Swarm Intelligence (2014). https://doi.org/10.48550/arXiv.1703.01893. [Google Scholar]
G. Huang and A. Lim, A hybrid genetic algorithm for three-index assignment problem. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation, CEC 2003 (2003) 2762–2768. [Google Scholar]
M. Johnsson, G. Magyar and O. Nevalainen, On the Euclidean 3-matching problem. Nordic J. Comput. 5 (1998) 143–171. [MathSciNet] [Google Scholar]
D. Kadhem, Heuristic solution approaches to the solid assignment problem, Ph.D. thesis, University of Essex, UK (2017). [Google Scholar]
A.R. Kammerdiner and C.F. Vaughan, Very large-scale neighborhood search for the multidimensional assignment problem, in Optimization Methods and Applications. Springer, Cham (2017) 251–262. [Google Scholar]
A.R. Kammerdiner, A. Semenov and E. Pasiliao, Landscape properties of the very large-scale and the variable neighborhood search metaheuristics for the multidimensional assignment problem (2021). Preprint arXiv:2112.11849. [Google Scholar]
A.R. Kammerdiner, A. Semenov and E.L. Pasiliao, Multidimensional assignment problem for multipartite entity resolution. J. Glob. Optim. (2022) 1–33. [Google Scholar]
D. Karapetyan and G. Gutin, Local search heuristics for the multidimensional assignment problem. J. Heuristics 17 (2011) 201–249. [CrossRef] [Google Scholar]
D. Karapetyan and G. Gutin, A new approach to population sizing for memetic algorithms: a case study for the multidimensional assignment problem. Evol. Comput. 19 (2011) 345–371. [CrossRef] [PubMed] [Google Scholar]
R.M. Karp, Reducibility among combinatorial problems. In: Complexity of Computer Computations. The IBM Research Symposia Series, Springer, Boston (1972) 85–103. [Google Scholar]
V.M. Kravtsov, Description of the types of maximum non-integer vertices of the polyhedron in the three-index axial assignment problem. Comput. Math. Math. Phys. 46 (2006) 1821–1825. [Google Scholar]
V.M. Kravtsov, Combinatorial properties of non-integer vertices of a polytope in a three-index axial assignment problem. Cybern. Syst. Anal. 43 (2007) 25–33. [CrossRef] [Google Scholar]
H.W. Kuhn, The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2 (1955) 83–97. [CrossRef] [Google Scholar]
Y. Kuroki and T. Matsui, An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors. Discrete Appl. Math. 157 (2009) 2124–2135. [CrossRef] [MathSciNet] [Google Scholar]
J. Li, R. Tharmarasa, D. Brown, T. Kirubarajan and K.R. Pattipati, A novel convex dual approach to three-dimensional assignment problem: theoretical analysis. Comput. Optim. Appl. 74 (2019) 481–516. [Google Scholar]
G. Magyar, M. Johnsson and O. Nevalainen, An adaptive hybrid genetic algorithm for the three-matching problem. IEEE Trans. Evol. Comput. 4 (2000) 135–146. [CrossRef] [Google Scholar]
A.R. Mahjoub, Two-edge connected spanning subgraphs polyhedra. Math. Program. 64 (1994) 199–208. [CrossRef] [Google Scholar]
A.R. Mahjoub, Polyhedral approaches, in Concepts of Combinatorial Optimization. John Wiley & Sons, Inc. (2014) 261–324. [CrossRef] [Google Scholar]
S.N. Medvedev and O.A. Medvedeva, An adaptive algorithm for solving the axial three-index assignment problem. Autom. Remote Control 80 (2019) 718–732. [CrossRef] [MathSciNet] [Google Scholar]
M. Mehbali (2025). https://github.com/mmehbali/Three-IAP. [Google Scholar]
J. Munkres, Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5 (1957) 32–38. [CrossRef] [Google Scholar]
S. Pal, I. Khan and M.K. Maiti, A heuristic approach to solve multidimensional assignment problem, in Proceedings of the 2018 4th International Conference on Recent Advances in Information Technology (RAIT). IEEE (2018) 1–7. [Google Scholar]
E.L. Pasiliao, P.M. Pardalos and L.S. Pitsoulis, Branch and bound algorithms for the multidimensional assignment problem. Optim. Methods Softw. 20 (2005) 127–143. [CrossRef] [MathSciNet] [Google Scholar]
S.L.P. Perez, Personnel assignment problems through the multidimensional assignment problem. Ph.D. thesis on Optimization Universidad Autónoma Metropolitana, Mexico City, Mexico (2017). [Google Scholar]
W.P. Pierskalla, The tri-substitution method for the multidimensional assignment problem. Can. Oper. Res. Soc. 5 (1967) 71–81. [Google Scholar]
W.P. Pierskalla, Letters to the editor - the multidimensional assignment problem. Oper. Res. 16 (1968) 422–454. [CrossRef] [Google Scholar]
A.B. Poore, Multidimensional assignment problems arising in multitarget and multisensor tracking. In: Nonlinear Assignment Problems. Springer, Boston (2000) 13–38. [CrossRef] [Google Scholar]
A.B. Poore and A.J. Robertson, A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problem. Comput. Optim. Appl. 8 (1997) 129–150. [Google Scholar]
A.B. Poore and S. Gadaleta, Some assignment problems arising from multiple target tracking. Math. Computer Model. 43 (2006) 1074–1091. [CrossRef] [Google Scholar]
A.B. Poore, S. Lu and B.J. Suchomel, Data association using multiple-frame assignments. In: Handbook of Multi-sensor Data Fusion. CRC Press, Boca Raton (2017) 319–338. [Google Scholar]
L. Qi, L. and D. Sun, Polyhedral methods for solving three index assignment problems. In: Nonlinear Assignment Problems. Springer, Boston (2000) 91–107. [CrossRef] [Google Scholar]
L.E.U. Rivero, M.R.B. Escarcega and J. Velasco, An integer linear programming model for a case study in classroom assignment problem. Comput. Sist. 24 (2020) 97–104. [Google Scholar]
F.C.R. Spieksma, Multi-index assignment problems: complexity, approximation, applications. In: Nonlinear Assignment Problems. Springer, Boston (2000) 1–12. [Google Scholar]
F.C.R. Spieksma and G.J. Woeginger, Geometric three-dimensional assignment problems. Eur. J. Oper. Res. 91 (1996) 611–618. [CrossRef] [Google Scholar]
T.A.M. Toffolo and H.G. Santos, Introduction - Python-MIP documentation (2019). https://docs.python-mip.com/en/latest/intro.html. [Google Scholar]
S. Vadrevu and R. Nagi, A dual-ascent algorithm for the multi-dimensional assignment problem: application to multi-Target tracking. In: Proceedings of the 2020 IEEE 23rd International Conference on Information Fusion (FUSION)., IEEE (2020) 1–8. [Google Scholar]
C.E. Valencia, F.J.Z. Martinez, S.L.P. and Perez, A simple but effective memetic algorithm for the multidimensional assignment problem. In: Proceedings of the 2017 14th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE). IEEE (2017). [Google Scholar]
C.E. Valencia, C.A. Alfaro, F.J.Z. Martinez, M.C.V Magana and S.L.P. Perez, Outperforming several heuristics for the multidimensional assignment problem. In: Proceedings of the 2018 15th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE). IEEE (2018). [Google Scholar]
C.J. Veenman, M.J.T. Reinders and E. Backer, Establishing motion correspondence using extended temporal scope. Artif. Intell. 145 (2003) 227–243. [CrossRef] [Google Scholar]
E.R. Wulan, D. Jamaluddin and W.N. Ramadhan, Determining optimal solutions in learning outcome using one to one fixed method. In: Proceedings of the International Conference on Science and Engineering (ICSE-UIN-SUKA 2021). Atlantis Press (2021) 7–11. [Google Scholar]
L. Zhang, D. Sidoti, S. Vallabhaneni, K.R. Pattipati and D.A. Castnon, Approaches to obtain a large number of ranked solutions to 3-dimensional assignment problems. J. Adv. Inf. Fusion 13 (2017) 50–65. [Google Scholar]
Y. Zhang, Y. Li, S. Li, J. Zeng, Y. Wang and S. Yan, Multi-target tracking in multi-static networks with autonomous underwater vehicles using a robust multi-sensor labeled Bernoulli filter. J. Mar. Sci. Eng. 11 (2023) 875. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.