Solving Combinatorial Optimization Problems using Relaxed Linear Programming: A High Performance Computing Perspective

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 imple-ment it using message passing interface (MPI) to fully utilize the computing power provided by the modern supercomput-ers 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 in-terface 1