In　this　paper,　we　consider　the　perfect　demand　matching　problem　(PDM)　which　combines　aspects　of　the　knapsack　problem　along　with　the　b-matching　problem.　It　is　a　generalization　of　the　maximum　weight　matching　problem　which　has　been　fundamental　in　the　development　of　theory　of　computer　science　and　operations　research.　This　problem　is　NP-hard　and　there　exists　a　constant　ϵ＞0　such　that　the　problem　admits　no　1+ϵ-approximation　algorithm,　unless　P=NP.　Here,　we　investigate　the　performance　of　a　distributed　message　passing　algorithm　called　Max-sum　belief　propagation　for　computing　the　problem　of　finding　the　optimal　perfect　demand　matching.　As　the　main　result,　we　demonstrate　the　rigorous　theoretical　analysis　of　the　Max-sum　BP　algorithm　for　PDM,　and　establish　that　within　pseudo-polynomial-time,　our　algorithm　could　converge　to　the　optimal　solution　of　PDM,　provided　that　the　optimal　solution　of　its　LP　relaxation　is　unique　and　integral.　Different　from　the　techniques　used　in　previous　literature,　our　analysis　is　based　on　primal-dual　complementary　slackness　conditions,　and　thus　the　number　of　iterations　of　the　algorithm　is　independent　of　the　structure　of　the　given　graph.　Moreover,　to　the　best　of　our　knowledge,　this　is　one　of　a　very　few　instances　where　BP　algorithm　is　proved　correct　for　NP-hard　problems.　©　2023　Elsevier　Inc.