Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fluctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.

Chun-Yan Zhao;Yan-Rong Fu;Jin-Hua Zhao

College of Science,University of Shanghai for Science and Technology,Shanghai 200093,China;Guangdong Provincial Key Laboratory of Nuclear Science,Institute of Quantum Matter,South China Normal University,Guangzhou 510006,China;Guangdong-Hong Kong Joint Laboratory of Quantum Matter,Southern Nuclear Science Computing Center,South China Normal University,Guangzhou 510006,China

理论物理

[1]Chun-Yan Zhao;Yan-Rong Fu;Jin-Hua Zhao-.A residual-based message passing algorithm for constraint satisfaction problems)[J].理论物理,2022(03):77-86

residual,passing,constraint,satisfaction,problems,Message,algorithms,whose,iterative,nature,captures,complicated,interactions,among,interconnected,variables,complex,systems,extracts,information,from,fixed,iterated,messages,provide,powerful,toolkit,tackling,hard,computational,tasks,optimization,inference,learning,In,context,CSPs,when,control,parameter,such,density,tuned,multiple,threshold,phenomena,emerge,signaling,fundamental,structural,transitions,their,space,Finding,solutions,around,these,points,exceedingly,challenging,design,where,suffer,large,fluctuation,far,convergence,Here,introduce,updating,into,which,variation,between,consecutive,steps,are,given,high,priority,process,For,specific,example,model,RB,revised,typical,prototype,random,growing,domains,show,that,our,improves,increases,success,probability,finding,satisfiability,low,cost,Our,approach,should,value,exploring,developing,ground,state,understand,detailed,structure

0.61398