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