This page lists papers using the Configuration Checking (CC) idea. If you know some other papers should be included, it is appreciated that you drop me an email to let me know.
Vertex Cover Problems
Shaowei Cai, Kaile Su, Abdul Sattar, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artificial Intelligence (AIJ) 175(9-10), 1672-1696 (2011). [Propose the CC strategy for the first time.]
Shaowei Cai, Kaile Su, Chuan Luo, Abdul Sattar, NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover, Journal of Artificial Intelligence Research (JAIR) 46, pp. 687-716 (2013)
Zhou Y, Zhang H, Li R, et al. Two Local Search Algorithms for Partition Vertex Cover Problem, J. Comput. Theor. Nanosci. 13, 743-751 (2016)
Zhiwen Fang, Yang Chu, Kan Qiao, Xu Feng, Ke Xu: Combining Edge Weight and Vertex Weight for Minimum Vertex Cover Problem. Proc. of FAW (Frontiers in Algorithmics) 2014: 71-81
Boolean Satisfiability
Shaowei Cai, Kaile Su, Local search for Boolean Satisfiability with configuration checking and subscore, Artificial Intelligence (AIJ) 204, pp. 75-98 (2013). [Typical CC for SAT with analysis]
Shaowei Cai, Chuan Luo, Kaile Su: CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability. Proc. of SAT 2015: 1-8
Chuan Luo, Shaowei Cai, Kaile Su, Wei Wu: Clause States Based Configuration Checking in Local Search for Satisfiability. IEEE Trans. Cybernetics 45(5): 1014-1027 (2015)[Clause states based CC]
Chuan Luo, Shaowei Cai, W. Wu, Kaile Su, Double Configuration Checking in Stochastic Local Search for Satisfiability, Proc. of AAAI-2014, pp. 2703-2709.[Double CC]
André Abramé, Djamal Habet, Donia Toumi:Improving configuration checking for satisfiable random k-SAT instances. Ann. Math. Artif. Intell. 79(1-3): 5-24 (2017)
Andre Abrame, Djamal Habet, Donia Toumi: A Two-Levels Local Search Algorithm for Random SAT Instances with Long Clauses. Proc. of STAIRS 2014: 11-20
Chu Min Li, Chong Huang, and Ruchu Xu, Balance between intensification and diversification: two sides of the same coin, Proc. of SAT Competition 2013, pp.10-11
C. Li, Y. Fan, CCA2013, Proc. of SAT Competition 2013, p.14
Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, and Meinolf Sellmann, Parallel Lingeling, CCASat, and CSCH-based Portfolios, Proc. of SAT Competition 2013, pp.26-27
Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, and Meinolf Sellmann, CSCH-based Portfolio using CCSat and March, Proc. of SAT Competition 2013, pp.28-29
Jingchao Chen, Solvers Combining Complete and Incomplete Solving Engines, Proc. of SAT Competition 2013, pp.54-55
Djamal Habet, Donia Toumi, and Andre Abrame, Ncca+: Configuration Checking and Novelty+ like heuristic, Proc. of SAT Competition 2013, p.61
Jingchao Chen and Yuyang Huang, vflipnum: A Local Search with Variable Flipping Frequency Heuristics for SAT, Proc. of SAT Competition 2013, pp.91-92
MaxSAT Problems
Chuan Luo, Shaowei Cai, Wei Wu, Zhong Jie, Kaile Su: CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability. IEEE Trans. Computers 64(7): 1830-1843 (2015)
Shaowei Cai, Zhong Jie, Kaile Su: An effective variable selection heuristic in SLS for weighted Max-2-SAT. J. Heuristics 21(3): 433-456 (2015)
Chuan Luo, Shaowei Cai, Kaile Su, Wenxuan Huang: CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability. Artif. Intell. 243: 26-44 (2017)
Maximum Clique Problems
Yiyuan Wang, Shaowei Cai, Minghao Yin, Two Efficient Local Search Algorithms for Maximum Weight Clique Problem, Proc. AAAI 2016, pp.805-811
Yi Fan, Chengqian Li, Zongjie Ma, Lian Wen, Abdul Sattar, Kaile Su: Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures. Australasian Conference on Artificial Intelligence 2016: 255-267
Set Cover Problems
Yiyuan Wang, Dantong Ouyang, Zhang L, Minghao Yin, A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. SCIENCE CHINA Info Sci. 2015 doi:10.1007/s11432-015-5377-8
Chao Gao, Xin Yao, Thomas Weise, Jinlong Li: An efficient local search heuristic with row weighting for the unicost set covering problem. European Journal of Operational Research 246(3): 750-761 (2015)
Yiyuan Wang, Minghao Yin, Dantong Ouyang, Liming Zhang: A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem. International Transactions in Operational Research 24(6): 1463-1485 (2017)
Dominating Set Problems
Yiyuan Wang, Shaowei Cai and Minghao Yin: Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function, Journal of Artificial Intelligence Research (JAIR) 58, pp. 267-295 (2017) [CC with two level neighborhoods]
Combinatorial Auction
Haochen Zhang, Shaowei Cai, Chuan Luo, Minghao Yin: An efficient local search algorithm for the winner determination problem. J. Heuristics 23(5): 367-396 (2017)
Golomb Ruler Problem
M. M. Alam Polash, M. A. Hakim Newton, Abdul Sattar: Constraint-Based Local Search for Golomb Rulers. CPAIOR 2015: 322-331
The Black and White problem (chemical problem)
The Black and White problem (BWC) was modelled from the the problem of storing chemical products where certain pairs of places cannot contain different products.
Dongming Zhao: Simulated Annealing with Configuration Checking for the BWC Problem. Journal of Computational and Theoretical Nanoscience, Volume 12, Number 12, December 2015, pp. 5725-5727(3)
Our CC-based algorithms have been used or tested in real-world applications.
Wenxuan Huang, Daniil A Kitchaev, Stephen T Dacek, Ziqin Rong, Alexander Urban, Shan Cao, Chuan Luo, Gerbrand Ceder: Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT, Physical Review B 94 (13), 134424
Chuan Luo, Shaowei Cai, Kaile Su, Wenxuan Huang: CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability. Artif. Intell. 243: 26-44 (2017)
Andreas Fröhlich, Armin Biere, Christoph M. Wintersteiger, Youssef Hamadi: Stochastic Local Search for Satisfiability Modulo Theories. AAAI 2015: 1136-1143
Alexandre Fréchette, Neil Newman, Kevin Leyton-Brown: Solving the Station Repacking Problem. AAAI 2016: 702-709
M. M. Alam Polash, M. A. Hakim Newton, Abdul Sattar: Constraint-Based Local Search for Golomb Rulers. CPAIOR 2015: 322-331