收藏切换
Incremental Information Interaction-Based Algorithm for Enumerating MUSes
收藏切换
Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang*
Journal of Computer Research and Development | 2025, 62(5) : 1226 - 1234
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(5): 1226-1234
• Artificial Intelligence •
Incremental Information Interaction-Based Algorithm for Enumerating MUSes
Full
Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang*
Affiliations
  • College of Computer Science and Technology, Jilin University, Changchun 130012
  • Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012
  • born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

    born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

    born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

    born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

    born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

About Author:

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

Published: 2025-05-01 doi: 10.7544/issn1000-1239.202440326
Outline
收藏切换

Enumerating minimal unsatisfiable subsets (MUS) is an important issue in theoretical computer science. Given an unsatisfiable Boolean formula, the number of its MUS is exponentially related to the formula’s scale. Contemporary methods aim to identify MUSes as many as possible within appropriate time limits. Dealing with the huge search space and choosing a suitable node to expand can markedly reduce the time consumption on shrink and grow operations, thereby the algorithm could obtain better performance. We introduce an incremental information interaction-based MUS solving algorithm, denoted as MARCO-MSS4MUS, which utilizes the duality and complementary relationships among MUS, minimal correction set (MCS), and maximal satisfiable subset (MSS). Based on the framework of MARCO algorithm, the proposed algorithm selects a more suitable node to expand via intersection and union information of previously identified MSSes during the search, i.e., the incremental MSS information is employed as a heuristic for node selection to accelerate the enumeration of MUS. This process also benefits in identifying more MSSes, in turn, the incremental MSS information helps select a better node for next exploration, thereby achieving an interaction of incremental information. Two theorems and two corollaries regarding interactive incremental information are proposed and the feasibility of our MARCO-MSS4MUS algorithm is theoretically analyzed. Experiments on standard MUS benchmark instances show the superiority of the proposed algorithm over state-of-the-art algorithms. Both the enumeration efficiency and the number of enumerated wins of the proposed algorithm are significantly improved compared with existing algorithms.

minimal unsatisfiable subset (MUS)  /  maximal satisfiable subset (MSS)  /  infeasibility analysis  /  hitting set  /  duality
蒋璐宇, 欧阳丹彤, 张奇, 太然, 张立明. 基于增量信息交互的极小不可满足子集求解算法. 计算机研究与发展, 2025 , 62 (5) : 1226 -1234 . DOI: 10.7544/issn1000-1239.202440326
Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang. Incremental Information Interaction-Based Algorithm for Enumerating MUSes[J]. Journal of Computer Research and Development, 2025 , 62 (5) : 1226 -1234 . DOI: 10.7544/issn1000-1239.202440326
Year 2025 volume 62 Issue 5
117
51
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202440326
  • Receive Date:2024-05-21
  • Online Date:2026-11-10
  • Published:2025-05-01
Article Data
Affiliations
History
  • Received:2024-05-21
  • Revised:2024-09-29
  • Accepted:2024-10-15
Affiliations
    College of Computer Science and Technology, Jilin University, Changchun 130012
    Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440326
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT