deep learning for bipartite assignment problems

Deep Learning for Bipartite Assignment Problems*

Preserved fulltext.

• Adelaide Research & Scholarship

• Research Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Deep Learning for Bipartite Assignment Problems

2019, 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC)

Related Papers

Mohammed El-Beltagy

2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

Dhouha Bennoureddine

The task allocation problem in a distributed environment is one of the most challenging problems in a multiagent system. We propose a new task allocation process using deep reinforcement learning that allows cooperating agents to act automatically and learn how to communicate with other neighboring agents to allocate tasks and share resources. Through learning capabilities, agents will be able to reason conveniently, generate an appropriate policy and make a good decision. Our experiments show that it is possible to allocate tasks using deep Q-learning and more importantly show the performance of our distributed task allocation approach.

Mathematical Methods of Operations Research

Frits Spieksma , Sergey Polyakovskiy , Dries Goossens

2021 IEEE International Conference on Communications Workshops (ICC Workshops)

mehrazin alizadeh

James Orlin

Computers & Industrial Engineering

Silvio Eberhardt

Igor Litvinchev , Miguel Mata Perez

Erol Gelenbe

We investigate the assignment of assets to tasks where each asset can potentially execute any of the tasks, but assets execute tasks with a probabilistic outcome of success. There is a cost associated with each possible assignment of an asset to a task, and if a task is not executed there is also a cost associated with the non-execution of the task. Thus any assignment of assets to tasks will result in an expected overall cost which we wish to minimise. We formulate the allocation of assets to tasks in order to minimise this expected cost, as a nonlinear combinatorial optimisation problem. A neural network approach for its approximate solution is proposed based on selecting parameters of a Random Neural Network (RNN), solving the network in equilibrium, and then identifying the assignment by selecting the neurons whose probability of being active is highest. Evaluations of the proposed approach are conducted by comparison with the optimum (enumerative) solution as well as with a greedy approach over a large number of randomly generated test cases. The evaluation indicates that the proposed RNN based algorithm is better in terms of performance than the greedy heuristic, consistently achieving on average results within 5% of the cost obtained by the optimal solution for all problem cases considered. The RNN based approach is fast and is of low polynomial complexity in the size of the problem, while it can be used for decentralised decision making.

RELATED PAPERS

Diabetes care

Deborah Greenwood

Agung Nugraha

Tharun Shastry

Atención Primaria

Gabriel Sanfélix-Gimeno

Building and Environment

Angela Calia

DR. SHIBNATH BANERJEE

Charles KRAEMER

Jonas Kilpp

Journal of emerging technologies and innovative research

Dr. Sreenivasulu Gopu

Tareq Hossain

Cognition and Instruction

Thomas Philip

Emerging Mobile and Web 2.0 Technologies for Connected E-Government

Konstantin Simić

Journal of South American Earth Sciences

Diego Gallardo

Education Sciences

Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems Volume 2

Teologia Polityczna co tydzień 182

Andrzej Serafin

Bioremediation Science and Technology Research

Ismail Gambo Hassan

Research Square (Research Square)

Fernando Salvagiotti

Arun HS Kumar

arXiv (Cornell University)

Actes du VIe Colloque des étudiants de Master en Sciences Historiques et Artistiques tenu les 25-26 mai 2020

Morgane Pique

Peter Bediako

Journal of Marine Science and Engineering

Hakima Bahri

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

International Conference on Applied Intelligence and Informatics

AII 2022: Applied Intelligence and Informatics pp 90–101 Cite as

Tackling the Linear Sum Assignment Problem with Graph Neural Networks

• Carlo Aironi 10 ,
• Samuele Cornell 10 &
• Stefano Squartini 10  
• Conference paper

490 Accesses

2 Citations

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1724))

Linear Assignment Problems are fundamental combinatorial optimization problems that appear throughout domains such as logistics, robotics and telecommunications. In general, solving assignment problems to optimality is computationally infeasible even for contexts of small dimensionality, and so heuristic algorithms are often employed to find near-optimal solutions. The handcrafting of a heuristic usually requires expert-knowledge to exploit the problem structure to be addressed, however if the problem description changes slightly, a previously derived heuristic may no longer be appropriate.

This work explores a more general-purpose learning approach, based on the description of the problem through a bipartite graph, and the use of a Message Passing Graph Neural Network model, to attain the correct assignment permutation.

The simulation results indicate that the proposed structure allows for a significant increase in classification accuracy if compared with two different DNN approaches based on Dense Networks and Convolutional Neural Networks, furthermore, the GNN has proved to be very efficient with regard to the processing time and memory requirements, thanks to intrinsic parameter-sharing capability.

This is a preview of subscription content, log in via an institution .

Buying options

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Ann. Oper. Res. 14 (1), 105–123 (1988)

Article   MathSciNet   MATH   Google Scholar  

Burkard, R., Dragoti-Cela, E.: Linear assignment problems and extensions. Supplement Volume A, 1 edn., pp. 75–149. Kluwer Academic Publishers, Netherlands (1999)

Google Scholar  

Clapper, B.M.: Munkres implementation for python. https://github.com/bmc/munkres . Accessed 10 May 2022

Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch geometric. In: ICLR Workshop on Representation Learning on Graphs and Manifolds (2019)

Fujita, Y., Kanda, N., Horiguchi, S., Xue, Y., Nagamatsu, K., Watanabe, S.: End-to-end neural speaker diarization with self-attention. In: 2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pp. 296–303. IEEE (2019)

Gori, M., Monfardini, G., Scarselli, F.: A new model for learning in graph domains. In: International Joint Conference on Neural Networks, vol. 2, pp. 729–734. IEEE (2005)

Haralick, R.M., Shapiro, L.G.: Image segmentation techniques. Comput. Vision Graph. Image Process. 29 (1), 100–132 (1985)

Article   Google Scholar  

Hirata, N.S., Julca-Aguilar, F.D.: Matching based ground-truth annotation for online handwritten mathematical expressions. Pattern Recogn. 48 (3), 837–848 (2015)

Article   MATH   Google Scholar  

Karmarkar, N., Ramakrishnan, K.: Computational results of an interior point algorithm for large scale linear programming. Math. Program. 52 (1), 555–586 (1991)

de Kerret, P., Gesbert, D., Filippone, M.: Decentralized deep scheduling for interference channels. arXiv preprint arXiv:1711.00625 (2017)

Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2 (1–2), 83–97 (1955)

Lee, M., Xiong, Y., Yu, G., Li, G.Y.: Deep neural networks for linear sum assignment problems. IEEE Wirel. Commun. Lett. 7 (6), 962–965 (2018)

Lian, W., Zhang, L.: A concave optimization algorithm for matching partially overlapping point sets. Pattern Recogn. 103 , 107322 (2020)

Lu, X., Ni, Q., Li, W., Zhang, H.: Dynamic user grouping and joint resource allocation with multi-cell cooperation for uplink virtual MIMO systems. IEEE Trans. Wireless Commun. 16 (6), 3854–3869 (2017)

Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5 (1), 32–38 (1957)

Naiem, A., El-Beltagy, M., Ab, P.: Deep greedy switching: a fast and simple approach for linear assignment problems. In: 7th International Conference of Numerical Analysis and Applied Mathematics, p. 9999 (2009)

Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Trans. Neural Netw. 20 (1), 61–80 (2008)

Smith, K., Gatica-Perez, D., Odobez, J.M., Ba, S.: Evaluating multi-object tracking. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005)-Workshops, p. 36. IEEE (2005)

Song, H., Fang, X., Fang, Y.: Unlicensed spectra fusion and interference coordination for LTE systems. IEEE Trans. Mob. Comput. 15 (12), 3171–3184 (2016)

Sun, H., Chen, X., Shi, Q., Hong, M., Fu, X., Sidiropoulos, N.D.: Learning to optimize: training deep neural networks for interference management. IEEE Trans. Signal Process. 66 (20), 5438–5453 (2018)

Sun, H., Chen, X., Shi, Q., Hong, M., Fu, X., Sidiropoulos, N.D.: Learning to optimize: training deep neural networks for wireless resource management. In: 2017 IEEE 18th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 1–6. IEEE (2017)

Yu, D., Kolbæk, M., Tan, Z.H., Jensen, J.: Permutation invariant training of deep models for speaker-independent multi-talker speech separation. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 241–245. IEEE (2017)

Yu, G., Xu, L., Feng, D., Yin, R., Li, G.Y., Jiang, Y.: Joint mode selection and resource allocation for device-to-device communications. IEEE Trans. Commun. 62 (11), 3814–3824 (2014)

Zhou, J., et al.: Graph neural networks: a review of methods and applications. AI Open 1 , 57–81 (2020)

Download references

Author information

Authors and affiliations.

Department of Information Engineering, Universitá Politecnica delle Marche, Ancona, Italy

Carlo Aironi, Samuele Cornell & Stefano Squartini

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carlo Aironi .

Editor information

Editors and affiliations.

Nottingham Trent University, Nottingham, UK

Mufti Mahmud

University Mediterranea of Reggio Calabria, Reggio Calabria, Italy

Cosimo Ieracitano

Jahangirnagar University, Dhaka, Bangladesh

M. Shamim Kaiser

Nadia Mammone

Francesco Carlo Morabito

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Cite this paper.

Aironi, C., Cornell, S., Squartini, S. (2022). Tackling the Linear Sum Assignment Problem with Graph Neural Networks. In: Mahmud, M., Ieracitano, C., Kaiser, M.S., Mammone, N., Morabito, F.C. (eds) Applied Intelligence and Informatics. AII 2022. Communications in Computer and Information Science, vol 1724. Springer, Cham. https://doi.org/10.1007/978-3-031-24801-6_7

Download citation

DOI : https://doi.org/10.1007/978-3-031-24801-6_7

Publisher Name : Springer, Cham

Online ISBN : 978-3-031-24801-6

eBook Packages : Computer Science Computer Science (R0)

Share this paper

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Library staff login
• Subject/college/research area
• Latest Additions
• Special collections & archives
• Submit a paper

VU Research Repository

Find repository resources, search the vu research repository, deep learning for bipartite assignment problems.

Dimensions Badge

Altmetric badge.

Search Google Scholar

Repository staff login

Combinatorial Reinforcement Learning of Linear Assignment Problems

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Help | Advanced Search

Computer Science > Discrete Mathematics

Title: multidimensional assignment problem for multipartite entity resolution.

Abstract: Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We derive a mathematical formulation for a general class of record linkage problems in multipartite entity resolution across many datasets as a combinatorial optimization problem known as the multidimensional assignment problem. As a motivation for our approach, we illustrate the advantage of multipartite entity resolution over sequential bipartite matching. Because the optimization problem is NP-hard, we apply two heuristic procedures, a Greedy algorithm and very large scale neighborhood search, to solve the assignment problem and find the most likely matching of records from multiple datasets into a single entity. We evaluate and compare the performance of these algorithms and their modifications on synthetically generated data. We perform computational experiments to compare performance of recent heuristic, the very large-scale neighborhood search, with a Greedy algorithm, another heuristic for the MAP, as well as with two versions of genetic algorithm, a general metaheuristic. Importantly, we perform experiments to compare two alternative methods of re-starting the search for the former heuristic, specifically a random-sampling multi-start and a deterministic design-based multi-start. We find evidence that design-based multi-start can be more efficient as the size of databases grow large. In addition, we show that very large scale search, especially its multi-start version, outperforms simple Greedy heuristic. Hybridization of Greedy search with very large scale neighborhood search improves the performance. Using multi-start with as few as three additional runs of very large scale search offers some improvement in the performance of the very large scale search procedure. Last, we propose an approach to evaluating complexity of the very large-scale neighborhood search.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

DBLP - CS Bibliography

Bibtex formatted citation.

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .