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

doi:10.1145/2501221.2501227

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

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	English
Title of host publication	Proc. of 2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining
Subtitle of host publication	Algorithms, Systems, Programming Models and Applications, BigMine 2013 - Held in Conj. with SIGKDD 2013 Conf.
Pages	39-46
Number of pages	8
DOIs	https://doi.org/10.1145/2501221.2501227
State	Published - 2013
Event	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. - Chicago, IL, United States Duration: 11 Aug 2013 → 11 Aug 2013

Publication series

Name	Proc. 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.

Conference

Conference	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.
Country/Territory	United States
City	Chicago, IL
Period	11/08/13 → 11/08/13

Keywords

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

Access to Document

10.1145/2501221.2501227

Cite this

Jin, C., Fu, Q., Wang, H., Agrawal, A., Hendrix, W., Liao, W. K., Patwary, M. M. A., Banerjee, A., & Choudhary, A. (2013). Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective. In Proc. 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. (pp. 39-46). (Proc. 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.). https://doi.org/10.1145/2501221.2501227

Jin, Chen ; Fu, Qiang ; Wang, Huahua et al. / Solving combinatorial optimization problems using relaxed linear programming : A high performance computing perspective. Proc. 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.. 2013. pp. 39-46 (Proc. 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.).

@inproceedings{35e5b82bba4d427b8d7a157decb1bafd,

title = "Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective",

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.",

keywords = "Alternating direction method of multipliers, Markov random field, Maximum a posteriori inference, Message passing interface",

author = "Chen Jin and Qiang Fu and Huahua Wang and Ankit Agrawal and William Hendrix and Liao, {Wei Keng} and Patwary, {Md Mostofa Ali} and Arindam Banerjee and Alok Choudhary",

year = "2013",

doi = "10.1145/2501221.2501227",

language = "English",

isbn = "9781450323246",

series = "Proc. 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.",

pages = "39--46",

booktitle = "Proc. of 2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining",

note = "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. ; Conference date: 11-08-2013 Through 11-08-2013",

}

Jin, C, Fu, Q, Wang, H, Agrawal, A, Hendrix, W, Liao, WK, Patwary, MMA, Banerjee, A & Choudhary, A 2013, Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective. in Proc. 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.. Proc. 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., pp. 39-46, 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., Chicago, IL, United States, 11/08/13. https://doi.org/10.1145/2501221.2501227

Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective. / Jin, Chen; Fu, Qiang; Wang, Huahua et al.
Proc. 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.. 2013. p. 39-46 (Proc. 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.).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving combinatorial optimization problems using relaxed linear programming

T2 - 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.

AU - Jin, Chen

AU - Fu, Qiang

AU - Wang, Huahua

AU - Agrawal, Ankit

AU - Hendrix, William

AU - Liao, Wei Keng

AU - Patwary, Md Mostofa Ali

AU - Banerjee, Arindam

AU - Choudhary, Alok

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Alternating direction method of multipliers

KW - Markov random field

KW - Maximum a posteriori inference

KW - Message passing interface

UR - http://www.scopus.com/inward/record.url?scp=84890702859&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84890702859&partnerID=8YFLogxK

U2 - 10.1145/2501221.2501227

DO - 10.1145/2501221.2501227

M3 - Conference contribution

AN - SCOPUS:84890702859

SN - 9781450323246

T3 - Proc. 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.

SP - 39

EP - 46

BT - Proc. of 2nd Int. Workshop on Big Data, Streams and Heterogeneous Source Mining

Y2 - 11 August 2013 through 11 August 2013

ER -

Jin C, Fu Q, Wang H, Agrawal A, Hendrix W, Liao WK et al. Solving combinatorial optimization problems using relaxed linear programming: A high performance computing perspective. In Proc. 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.. 2013. p. 39-46. (Proc. 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.). doi: 10.1145/2501221.2501227

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this