Solving combinatorial optimization problems using relaxed linear programming
Chen Jin, Qiang Fu, Huahua Wang, Ankit Agrawal, William Hendrix, Wei‐keng Liao, Md. Mostofa Ali Patwary, Arindam Banerjee, Alok N. Choudhary · 2013
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.