最小碰集问题分支定界算法约简与分支策略优化OA

The minimum hitting set problem is an NP-hard problem and has wide applications in fields such as fault diagnosis and drug design.Recently,Bläsius proposed a branch-and-bound algorithm that was the first to outperform mixed-integer linear programming approaches.Through an in-depth analysis,two performance limitations were found in the algorithm.First,the asymmetric reduction efficiency between the left and right branches results in inefficient reduction in the right branch.Second,the degree-based branch vertex selection strategy remains relatively coarse-grained.This paper proposes two optimization strategies:first,an asymmetric reduction strategy based on branch characteristics to reduce inefficient reduction operations in the right branch and improve overall reduction efficiency;second,a bound-based branch vertex set selection strategy based on bound calculation,along with the design of a heuristic scoring mechanism to minimize the branch vertex set.Experimental results on the UCC,CVD,EN1 and EN2 datasets show that the asymmetric reduction strategy significantly improves the reduction efficiency of the algorithm and accelerates the solving speed of the algorithm;the branch vertex selection strategy based on bound calculation can reduce the search tree size by 30%to 80%on most graph instances.The new algorithm combining two optimization strategies greatly improves solving speed and overall solves six more graph instances than the original algorithm.