基本信息

蔡少伟 

中国科学院软件研究所  研究员 博导

中国科学院大学 教授
电子邮件: caisw@ios.ac.cn
通信地址: 北京市海淀区中关村南四街4号中国科学院软件园区5号楼210
邮政编码: 100190

研究方向 和 招生信息

本人主要研究方向为约束求解、组合优化以及EDA(电子设计自动化)验证工具。主要研究成果包括:(1)提出了格局检测策略,有效解决局部搜索的重要缺陷—循环现象,被广泛用于NP难组合优化问题。(2)设计了高效的约束求解算法,在命题逻辑可满足性问题(SAT)、可满足性模理论(SMT)问题、最大可满足性问题(MaxSAT)等国际比赛多次获得冠军,在国际EDA比赛获得亚军;提出可满足性问题的混合搜索方法,解决了命题逻辑推理与搜索方向十大挑战的第7个挑战,获得SAT会议最佳论文奖。(3)设计了搜索+推理的新型方法求解大规模组合优化问题,在多个著名组合优化问题如最大团,图着色,顶点覆盖,集合覆盖等NP难优化问题保持着前沿水平,在稀疏实例上可以秒级求解千万顶点规模的图优化问题。

本人也致力于研究成果产业化,在EDA、软件验证、云计算、排班、智慧园区等领域展开了系列项目,研究成果被用于国内龙头企业芯片验证、美联邦通讯委员会频谱分配、意大利银行系统优化、建设银行智慧园区、腾讯地图优化、微软云计算服务平台优化和故障检测、MIT新型材料研究等实际场景。


招收研究生和实习生,希望学生有优秀的算法基础和编程能力, 较好的数学基础(尤其是离散数学)和英语能力。如有意愿保送研究生,请尽早联系。

教育背景

2012-07--2014-07   Griffith University (jointly with National ICT Australia)   应用数学 博士
2008-09--2012-07   北京大学   计算机软件与理论 博士
2004-09--2008-07   华南理工大学   计算机科学与技术 学士

工作经历

工作简历
2017-09~现在, 中国科学院软件研究所, 研究员
2014-07~2017-09,中国科学院软件研究所, 副研究员


社会兼职

  • 中科院青年创新促进会 信息与管理分会 会长, 2019.10.16至今
  • 会议主席,中科院青促会信管分会年会暨第一届青年信息学论坛,北京, 2020.12.12
  • 程序委员会主席,the first international workshop of Heuristic Search in Industry (HSI 2020), conjunction with the 29th IJCAI Conference on Artificial Intelligence (IJCAI 2020);
  • 程序委员会主席, Constraints and Satisfiability Track, KESM 2018
  • 组织委员会委员(发起人), Workshop on Hard Computational Problems: Representations, Algorithms and Applications 2017-2019
    程序委员会(高级)委员, IJCAI 2016-2021, AAAI 2015-2021
    Yong Associate Editor,Frontinese of Computer Sciences, 2014.12至今
  • 客座编辑,"Constraints and Optimizations" special issue, Science China:Information Sciences, 2020.



教授课程

离散数学
高级算法设计与分析

荣誉与奖励

荣誉与奖励

  • 中科院优秀导师,2021
  • 智源青年科学家,2020
  • 中科院软件所 杰出青年,2018
  • 中科院青促会会员,2017
  • 北京市优秀毕业生, 2012
  • 北京大学优秀博士论文奖,2012
  • 北京大学学术创新奖, 2011

国际比赛获奖

  • 2021年国际SMT-COMP比赛QF_IDL theory冠军(中国首次在SMT-COMP获冠军),2021
  • 2021年国际EDA Challenge比赛亚军,2021
  • 2021年国际SAT比赛Main track SAT,UNSAT 亚军,2021
  • 2021年国际MaxSAT比赛完备组(加权)冠军, 非完备组(不加权和加权)冠军,2018
  • 2020年国际SAT比赛Main track SAT 冠军,2020
  • 2020年国际SAT比赛Planning track 亚军,2020
  • 全球运筹优化挑战赛-城市物流运输车辆智能调度 Excellence Award, 2018
  • 2018年Sparkle SAT Challenge, 亚军,  2018
  • 2018年国际SAT比赛No-Limits track 冠军, 2018
  • 2018年联合逻辑大会奥林匹克 金牌, 2018
  • 2016年国际SAT比赛Random track 亚军, 2016
  • 2014国际SAT比赛Hard-combinatorial组 亚军, 2014
  • 2012国际SAT比赛,Best Solver Award (中国首次在SAT-COMP获冠军), 2012
  • 中国机器人暨RoboCup公开赛:足球机器人比赛中型组,一等奖,2007


出版信息

发表论文


  1. Shaowei Cai, Jinkun Lin, Yiyuan Wang: A Semi-Exact lgorithm for Quickly Computing a Maximum Weight Clique in Large Sparse Graphs, J. Artif. Intell. Res. 72: 39-67 (2021)
  2. Shaowei Cai*, Xindi Zhang: Deep Cooperation of CDCL and Local Search for SAT, SAT 2021 [最佳论文奖]
  3. Zhendong Lei, Shaowei Cai*, Chuan Luo, Holger H. Hoos: Efficient Local Search for Pseudo Boolean Optimization. SAT 2021
  4. Jinkun Lin, Shaowei Cai*, Bing He, Yingjie Fu, Chuan Luo, Qingwei Lin: FastCA: An Effective and Efficient Tool for Combinatorial Covering Array Generation. ICSE 2021
  5. Shaowei Cai*, Xindi Zhang: Pure MaxSAT and Its Applications to Combinatorial Optimization via Linear Local Search, 26th International Conference on Principles and Practice of Constraint Programming (CP 2020).

  6. Shaowei Cai*, Zhendong Lei: Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability, Artificial Intelligence (AIJ), 287(2020)103354

  7.  Chuan Luo, Holger Hoos, Shaowei Cai: PbO-CCSAT: Boosting Local Search for Satisfiability using Programming by Optimisation, 16th International Conference on Parallel Problem Solving from Nature (PPSN 2020), Leiden, The Netherlands, September 5-9, 2020

  8. Shaowei Cai*, Wenying Hou, Yiyuan Wang, Chuan Luo, Qingwei Lin: Two-goal Local Search and Inference Rules for Minimum Dominating Set, 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Kyoto, January 5-10, 2021

  9. Zhendong Lei, Shaowei Cai*, Chuan Luo: Extended Conjunctive Normal Form and An Efficient Algorithm for Cardinality Constraints, 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Kyoto, January 5-10, 2021

  10. Bohan Li, Xindi Zhang, Shaowei Cai*, Jinkun Lin, YiyuanWang, Christian Blum: NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set, 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Kyoto, January 5-10, 2021

  11. Wenjie Zhang, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, Lu Zhang: NLocalSAT: Boosting Local Search with Solution Prediction, 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), Kyoto, January 5-10, 2021

  12. Zhendong Lei, Shaowei Cai*: Solving Set Cover and Dominating Set via Maximum Satisfiability, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), New York, USA, February 7-12, 2020.

  13. Yiyuan Wang, Shaowei Cai*, Shiwei Pan, Ximing Li, Minghao Yin*: Reduction and Local Search for Weighted Graph Coloring Problem, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), New York, USA, February 7-12, 2020.

  14. Peilin Chen#, Hai Wan#, Shaowei Cai#*, Jia Li, Haicheng Chen: Local Search with Dynamic-threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem, Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), New York, USA, February 7-12, 2020.

  15. Yiyuan Wang#, Shaowei Cai#*, Jiejiang Chen, Minghao Yin: SCCWalk: An Efficient Local Search Algorithm and Its Improvements for Maximum Weight Clique Problem, Artificial Intelligence (AIJ), 280: 103230 (2020). Co-first author

  16. Yingjie Fu, Zhendong Lei, Shaowei Cai*, Jinkun Lin, Haoran Wang: WCA: A weighting local search for constrained combinatorial test optimization, Information & Software Technology 122: 106288 (2020)

  17. Yi Chu, Boxiao Liu, Shaowei Cai, Chuan Luo, Haihang You: An efficient local search algorithm for solving maximum edge weight clique problem in large graphs, Journal of Combinatorial Optimization 39(4): 933-954 (2020)

  18. Yuren Zhou, Xiaoyu He, Yi Xiang, Shaowei Cai: A set of new multi- and many-objective test problems for continuous optimization and a comprehensive experimental evaluation, Artificial Intelligence (AIJ) 276: 105-129 (2019).

  19. Shaowei Cai*, Yuanjie Li, Wenying Hou, Haoran Wang: Towards faster local search for minimum weight vertex cover on massive graphs, Information Sciences 471 (2019) 6479.

  20. Zhendong Lei, Shaowei Cai*: NuDist: An Efficient Local Search Algorithm for Weighted Partial MaxSAT, The Computer Journal (2019), doi: 10.1093/comjnl/bxz063

  21. Yi Chu, Chuan Luo, Shaowei Cai, Haihang You: Empirical investigation of stochastic local search for maximum satisfiability. Frontiers of Computer Science 13(1): 86-98 (2019)

  22. Chuan Luo, Holger H. Hoos, Shaowei Cai, Qingwei Lin, Hongyu Zhang, Dongmei Zhang: Local Search with Efficient Automatic Configuration for Minimum Vertex Cover, 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), Macao, China, August 10-16, 2019. 

  23. Jinkun Lin, Shaowei Cai*, Chuan Luo, Qingwei Lin, and Hongyu Zhang: Towards more efficient meta-heuristic algorithms for combinatorial test generation, 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (FSE 2019), Tallinn, Estonia, August 26-30, 2019. 

  24. Yongjian Li, Kaiqiang Duan, David N. Jansen, Jun Pang, Lijun Zhang, Yi Lv, Shaowei Cai: An Automatic Proving Approach to Parameterized Verification, ACM Transactions on Computational Logic (TOCL) 19(4): 27:1-27:25 (2018).

  25. Yiyuan Wang, Shaowei Cai*, Minghao Yin: New heuristic approaches for maximum balanced biclique problem, Information Science 432: 362-375(2018).

  26. Kenji Kanazawa, Shaowei Cai: FPGA Acceleration to Solve Maximum Clique Problems Encoded into Partial MaxSAT, 12th IEEE International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC 2018), Hanoi, Vietnam, September 12-14, 2018

  27. Shaowei Cai*, Wenying Hou, Jinkun Lin, Yuanjie Li: Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies, 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Sweden, July 13-19, 2018.

  28. Zhendong Lei, Shaowei Cai*: Solving (Weighted) Partial MaxSAT by Dynamic Local Search for SAT, 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Sweden, July 13-19, 2018.

  29. Yiyuan Wang, Shaowei Cai*, Jiejiang Chen, Minghao Yin*: A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs, 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Sweden, July 13-19, 2018.

  30. Ruizhi Li, Shaowei Cai, Shuli Hu, Minghao Yin, Jian Gao: NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem, Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018), Hilton New Orleans Riverside, New Orleans, Louisiana, USA, February 2–7, 2018

  31. Chuan Luo, Shaowei Cai*, Kaile Su, Wenxuan Huang: CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability, Artificial Intelligence (AIJ) 243: 26-44 (2017)

  32. Shaowei Cai*, Jinkun Lin, Chuan Luo: Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess, Journal of Artificial Intelligence Research (JAIR) 59: 463-494 (2017).

  33. Yiyuan Wang, Shaowei Cai, 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: 267-295 (2017).

  34. Haochen Zhang, Shaowei Cai, Chuan Luo, Minghao Yin: An efficient local search algorithm for the winner determination problem. Journal of Heuristics 23(5): 367-396 (2017)

  35. Shaowei Cai*, Chuan Luo, Haochen Zhang: From Decimation to Local Search and Back: A New Approach to MaxSAT, 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, August 19-25, 2017.

  36. Jinkun Lin, Shaowei Cai*, Chuan Luo, Kaile Su: A Reduction based Method for Coloring Very Large Graphs, 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, August 19-25, 2017.

  37. Chuan Luo, Shaowei Cai*, Kaile Su, Wenxuan Huang: CCEHC: An Efficient Local Search Algorithm for Weighted Partial Maximum Satisfiability, 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, August 19-25, 2017.

  38. Yiyuan Wang, Shaowei Cai, Minghao Yin: Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function, 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), Melbourne, Australia, August 19-25, 2017.

  39. Faisal N. Abu-Khzam, Shaowei Cai, Judith Egan, Peter Shaw, Kai Wang: Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis,14th Annual Conference of Theory and Applications of Models of Computation (TAMC 2017), Bern, Switzerland, April 20-22, 2017

  40. Shaowei Cai*, Chuan Luo, Jinkun Lin, Kaile Su: New local search methods for partial MaxSAT, Artificial Intelligence (AIJ) 240: 1-18 (2016).

  41. Shaowei Cai*, Jinkun Lin: Fast Solving Maximum Weight Clique Problem in Massive Graphs, 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), New York, USA, July 9-15, 2016.

  42. Yiyuan Wang, Shaowei Cai, Minghao Yin: Two Efficient Local Search Algorithms for Maximum Weight Clique Problem, Thirtieth AAAI Conference on Artificial Intelligence (AAAI 2016), Phoenix, Arizona USA, February 12–17, 2016.

  43. Yongjian Li, Kaiqiang Duan, Yi Lv, Jun Pang, Shaowei Cai: A novel approach to parameterized verification of cache coherence protocols, 34th IEEE International Conference on Computer Design (ICCD 2016), Phoenix, USA, October 3-5, 2016.

  44. Shohei Sassa, Kenji Kanazawa, Shaowei Cai, Moritoshi Yasunaga: An FPGA Solver for Partial MaxSAT Problems Based on Stochastic Local Search. SIGARCH Computer Architecture News 44(4): 32-37 (2016)

  45. Chuan Luo, Shaowei Cai*, Wei Wu, Zhong Jie, Kaile Su: CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability, IEEE Transactions on Computers (ToC) 64(7): 1830-1843 (2015).

  46. Shaowei Cai*, Chuan Luo, Kaile Su: Improving WalkSAT By Effective Tie-breaking and Efficient Implementation, The Computer Journal (2015) 58 (11): 2864-2875.

  47. Chuan Luo, Shaowei Cai, Kaile Su, Wei Wu: Clause States Based Configuration Checking in Local Search for Satisfiability, IEEE Transactions on Cybernetics, 45(5): 1014-1027 (2015).

  48. Lijun Wu, Huijia Huang, Kaile Su, Shaowei Cai, Xiaosong Zhang: An I/O Efficient Model Checking Algorithm for Large-Scale Systems, IEEE Transactions on VLSI systems, 23(5): 905-915 (2015).

  49. Lijun Wu, Kaile Su, Shaowei Cai, Xiaosong Zhang, Chenyi Zhang, Shupeng Wang: An I/O Efficient Approach for Detecting All Accepting Cycles, IEEE Transactions Software Engineering. (TSE) 41(8): 730-744 (2015).

  50. Shaowei Cai, Zhong Jie, Kaile Su: An effective variable selection heuristic in SLS for weighted Max-2-SAT. Journal of Heuristics 21(3): 433-456 (2015)

  51. Shaowei Cai: Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs, 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina, July 25-31, 2015.

  52. Shaowei Cai*, Jinkun Lin, Kaile Su: Two Weighting Local Search for Minimum Vertex Cover, Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015), Austin Texas, USA, January 25–30, 2015.

  53. Jinkun Lin, Chuan Luo, Shaowei Cai, Kaile Su, Dan Hao, Lu Zhang: TCA: An Efficient Two-Mode Meta-Heuristic Algorithm for Combinatorial Test Generation, 30th IEEE/ACM International Conference on Automated Software Engineering (ASE 2015), Lincoln, Nebraska, USA, November 9–13, 2015.

  54. Shaowei Cai*, Chuan Luo, Kaile Su: CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability, 18th International Conference on Theory and Applications of Satisfiability Testing (SAT 2015), Austin, Texas, USA, September 24-27, 2015.

  55. Shaowei Cai, Chuan Luo, Kaile Su: Scoring Functions Based on Second Level Score for k-SAT with Long Clauses, Journal of Artificial Intelligence Research (JAIR) 51, pp.413-441 (2014).

  56. Shaowei Cai*, Chuan Luo, John Thornton, Kaile Su: Tailoring Local Search for Partial MaxSAT, Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI 2014), Québec Convention Center, Québec City, Québec, Canada, July 27–31, 2014.

  57. Chuan Luo, Shaowei Cai*, Wei Wu, Kaile Su: Double Configuration Checking in Stochastic Local Search for Satisfiability, Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI 2014), Québec Convention Center, Québec City, Québec, Canada, July 27–31, 2014.

  58. Shaowei Cai*, Kaile Su: Local Search for Boolean Satisfiability with Configuration Checking and Subscore, Artificial Intelligence (AIJ) 204, pp.75-98 (2013).

  59. Shaowei Cai*, Kaile Su: Comprehensive Score: Towards Efficient Local Search for SAT with Long Clauses, 23th International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China, August 3–9, 2013.

  60. Shaowei Cai*, Kaile Su, Chuan Luo: Improving WalkSAT for Random k-Satisfiability Problem with k>3, Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 13), Bellevue, Washington, USA, July 14–18, 2013.

  61. 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).

  62. Chuan Luo, Shaowei Cai*, Wei Wu, Kaile Su: Focused Random Walk with configuration Checking and Break Minimum for Satisfiability, 19th International Conference on Principles and Practice of Constraint Programming (CP 2013), Uppsala, Sweden, September 16-20, 2013.

  63. Shaowei Cai, Kaile Su: Configuration Checking with Aspiration in Local Search for SAT, Twenty-Sixth Conference on Artificial Intelligence (AAAI 2012), Toronto, Ontario, Canada, July 22–26, 2012.

  64. Shaowei Cai, Kaile Su, Abdul Sattar: Two New Local Search Strategies for Minimum Vertex Cover, Twenty-Sixth Conference on Artificial Intelligence (AAAI 2012), Toronto, Ontario, Canada, July 22–26, 2012.

  65. Chuan Luo, Kaile Su*, Shaowei Cai: Improving Local Search for Random 3-SAT Using Quantitative Configuration Checking, 20th European Conference on Artificial Intelligence (ECAI 2012), Montpellier, France, Aug 27-31, 2012.

  66. 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), pp. 16721696 (2011).

  67. Shaowei Cai, Kaile Su: Local Search with Configuration Checking for SAT, IEEE 23rd International Conference on Tools with Artificial Intelligence (ICTAI 2011), Boca Raton, FL, USA, November 7-9, 2011

  68. Shaowei Cai, Kaile Su, Qingliang Chen: EWLS: A New Local Search for Minimum Vertex Cover, Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), Atlanta, Georgia, USA, July 11–15, 2010.