Data-driven approximations to NP-hard problems

Anton Milan, S. Hamid Rezatofighi, Ravi Garg, Anthony Dick, Ian Reid

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

23 Citations (Scopus)


There exist a number of problem classes for which obtaining the exact solution becomes exponentially expensive with increasing problem size. The quadratic assignment problem (QAP) or the travelling salesman problem (TSP) are just two examples of such NP-hard problems. In practice, approximate algorithms are employed to obtain a suboptimal solution, where one must face a trade-off between computational complexity and solution quality. In this paper, we propose to learn to solve these problem from approximate examples, using recurrent neural networks (RNNs). Surprisingly, such architectures are capable of producing highly accurate solutions at minimal computational cost. Moreover, we introduce a simple, yet effective technique for improving the initial (weak) training set by incorporating the objective cost into the training procedure. We demonstrate the functionality of our approach on three exemplar applications: marginal distributions of a joint matching space, feature point matching and the travelling salesman problem. We show encouraging results on synthetic and real data in all three cases.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Subtitle of host publicationSan Francisco, California, USA — February 04 - 09, 2017
EditorsSatinder Singh, Shaul Markovitch
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages7
ISBN (Electronic)9781577357810
Publication statusPublished - 2017
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2017 - Hilton San Francisco Union Square, San Francisco, United States of America
Duration: 4 Feb 201710 Feb 2017
Conference number: 31st


ConferenceAAAI Conference on Artificial Intelligence 2017
Abbreviated titleAAAI 2017
CountryUnited States of America
CitySan Francisco
Internet address


  • Long short-term memory
  • data association
  • matching

Cite this