Policy Gradient MaxSAT Solver

被引：0

作者：

Gutierrez-De-La-Paz, Omar ^{[1
]}

Menchaca-Mendez, Ricardo ^{[1
]}

Zamora-Gomez, Erik ^{[1
]}

Corona-Bermudez, Uriel ^{[1
]}

Menchaca-Mendez, Rolando ^{[1
]}

Gutierrez-De-La-Paz, Bruno ^{[1
]}

机构：

[1] Inst Politecn Nacl, Ctr Invest Comp, Mexico City, Mexico

来源：

COMPUTACION Y SISTEMAS | 2024年 / 28卷 / 02期

关键词：

MaxSAT problem; policy gradient; NP-hard;

D O I：

10.13053/CyS-28-2-4723

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents a comparative study of various elements and strategies that can be incorporated into an autoregressive model to address the MaxSAT problem. Building upon a sequential architecture as our foundation, we optimize the model's parameters by maximizing the expected number of satisfied clauses. This optimization enables the model, given a SAT formula, to predict a distribution over potential solutions using the policy gradient method. Our controlled experiments pinpoint elements that guide the optimization process towards superior results(1) .

引用

页码：353 / 366

页数：14

共 27 条

[1] Optuna: A Next-generation Hyperparameter Optimization Framework
Akiba, Takuya
Sano, Shotaro
Yanase, Toshihiko
Ohta, Takeru
Koyama, Masanori
[J]. KDD'19: PROCEEDINGS OF THE 25TH ACM SIGKDD INTERNATIONAL CONFERENCCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2019, : 2623 - 2631
[2] Avellaneda F., 2020, MaxSAT Evaluation, V8
[3] Bacchus F., 2022, Department of Computer Science Series of Publications B, V2, P17
[4] Bello I., 2017, ARXIV, DOI [10.48550/arXiv.1611.09940, DOI 10.48550/ARXIV.1611.09940]
[5] Machine learning for combinatorial optimization: A methodological tour d'horizon
Bengio, Yoshua
Lodi, Andrea
Prouvost, Antoine
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 290 (02) : 405 - 421
[6] Core-Boosted Linear Search for Incomplete MaxSAT
Berg, Jeremias
Demirovic, Emir
Stuckey, Peter J.
[J]. INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2019, 2019, 11494 : 39 - 56
[7] Bergstra James S., 2011, Advances in Neural Information Processing Systems
[8] Cho Kyunghyun, 2014, P C EMP METH NAT LAN
[9] Dai HJ, 2017, ADV NEUR IN, V30
[10] Davies Jessica, 2013, Solving MAXSAT by Decoupling Optimization and Satisfaction

← 1 2 3 →