Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective

Chen Jin, Qiang Fu, Huahua Wang, Ankit Agrawal, William Hendrix, Wei Keng Liao, Md Mostofa Ali Patwary, Arindam Banerjee, Alok Choudhary

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Several important combinatorial optimization problems can be formulated as maximum a posteriori (MAP) inference in discrete graphical models. We adopt the recently proposed parallel MAP inference algorithm Bethe-ADMM and implement it using message passing interface (MPI) to fully utilize the computing power provided by the modern supercomputers with thousands of cores. The empirical results show that our parallel implementation scales almost linearly even with thousands of cores.

Original languageEnglish (US)
Title of host publicationProc. of 2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining
Subtitle of host publicationAlgorithms, Systems, Programming Models and Applications, BigMine 2013 - Held in Conj. with SIGKDD 2013 Conf.
PublisherAssociation for Computing Machinery
Pages39-46
Number of pages8
ISBN (Print)9781450323246
DOIs
StatePublished - Jan 1 2013
Event2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, BigMine 2013 - Held in Conj. with SIGKDD 2013 Conf. - Chicago, IL, United States
Duration: Aug 11 2013Aug 11 2013

Publication series

NameProc. of 2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, BigMine 2013 - Held in Conj. with SIGKDD 2013 Conf.

Other

Other2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, BigMine 2013 - Held in Conj. with SIGKDD 2013 Conf.
CountryUnited States
CityChicago, IL
Period8/11/138/11/13

Keywords

  • Alternating direction method of multipliers
  • Markov random field
  • Maximum a posteriori inference
  • Message passing interface

Fingerprint Dive into the research topics of 'Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective'. Together they form a unique fingerprint.

Cite this