Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these pro...Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these problems,almost all state-of-the-art local search algorithms adopt a common general initialization method.This paper develops a general group driven initialization method for clique relaxation problems.The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information.We apply the proposed initialization method to two clique relaxation problems.Experimental results demonstrate that the proposed initialization method clearly improves the performance of stateof-the-art algorithms for the clique relaxation problems.展开更多
In Weighted Model Counting(WMC),we assign weights to literals and compute the sum of the weights of the models of a given propositional formula where the weight of an assignment is the product of the weights of its li...In Weighted Model Counting(WMC),we assign weights to literals and compute the sum of the weights of the models of a given propositional formula where the weight of an assignment is the product of the weights of its literals.The current WMC solvers work on Conjunctive Normal Form(CNF)formulas.However,CNF is not a natural representation for human-being in many applications.Motivated by the stronger expressive power of Pseudo-Boolean(PB)formulas than CNF,we propose to perform WMC on PB formulas.Based on a recent dynamic programming algorithm framework called ADDMC for WMC,we implement a weighted PB counting tool PBCounter.We compare PBCounter with the state-of-the-art weighted model counters SharpSAT-TD,ExactMC,D4,and ADDMC,where the latter tools work on CNF with encoding methods that convert PB constraints into a CNF formula.The experiments on three domains of benchmarks show that PBCounter is superior to the model counters on CNF formulas.展开更多
The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving th...The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.展开更多
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61976050)CCF Huawei Hu Yanglin Foundation Theoretical Computer Science Project(CCFHuaweiLK2023001)+1 种基金the Fundamental Research Funds for the Central Universities(2412022ZD015,2412023YQ003)Jilin Science and Technology Department(YDZJ202201ZYTS412,20240602005RC).
文摘Clique relaxation problems are important extension versions of the maximum clique problem with extensive realworld applications.Although lots of studies focus on designing local search algorithms for solving these problems,almost all state-of-the-art local search algorithms adopt a common general initialization method.This paper develops a general group driven initialization method for clique relaxation problems.The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information.We apply the proposed initialization method to two clique relaxation problems.Experimental results demonstrate that the proposed initialization method clearly improves the performance of stateof-the-art algorithms for the clique relaxation problems.
基金supported by NSFC(Grant Nos.61976050,61972384)the Jilin Province Science and Technology Department project(Nos.20240101378JC,20240602005RC,YDZJ202201ZYTS415)Jilin Education Department Project(No.JJKH20231319KJ)。
文摘In Weighted Model Counting(WMC),we assign weights to literals and compute the sum of the weights of the models of a given propositional formula where the weight of an assignment is the product of the weights of its literals.The current WMC solvers work on Conjunctive Normal Form(CNF)formulas.However,CNF is not a natural representation for human-being in many applications.Motivated by the stronger expressive power of Pseudo-Boolean(PB)formulas than CNF,we propose to perform WMC on PB formulas.Based on a recent dynamic programming algorithm framework called ADDMC for WMC,we implement a weighted PB counting tool PBCounter.We compare PBCounter with the state-of-the-art weighted model counters SharpSAT-TD,ExactMC,D4,and ADDMC,where the latter tools work on CNF with encoding methods that convert PB constraints into a CNF formula.The experiments on three domains of benchmarks show that PBCounter is superior to the model counters on CNF formulas.
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61972063,61976050)the Fundamental Research Funds for the Central Universities(2412020FZ030,2412019ZD013,2412019FZ051)Jilin Science and Technology Association(QT202005).
文摘The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.
