Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algorithm for computing approximate solutions in Theta(N) for the maximum exact 3-satisfiability (MAX-E-3-SAT) problem by using supervised learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random conjunctive normal form instances of the MAX-E-3-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art maximum satisfiability solvers, it can solve substantially larger and more complicated problems than it ever saw during training.
Learning from survey propagation: a neural network for MAX-E-3-SAT / Raffaele Marino. - In: MACHINE LEARNING: SCIENCE AND TECHNOLOGY. - ISSN 2632-2153. - ELETTRONICO. - 2:(2021), pp. 035032.1-035032.14. [10.1088/2632-2153/ac0496]
Learning from survey propagation: a neural network for MAX-E-3-SAT
Raffaele Marino
2021
Abstract
Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algorithm for computing approximate solutions in Theta(N) for the maximum exact 3-satisfiability (MAX-E-3-SAT) problem by using supervised learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random conjunctive normal form instances of the MAX-E-3-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art maximum satisfiability solvers, it can solve substantially larger and more complicated problems than it ever saw during training.File | Dimensione | Formato | |
---|---|---|---|
Marino_2021_Mach._Learn.%3A_Sci._Technol._2_035032.pdf
accesso aperto
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Open Access
Dimensione
567.56 kB
Formato
Adobe PDF
|
567.56 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.