Real-like MAX-SAT instances and the landscape structure across the phase transition

Details

Serval ID
serval:BIB_DB5A1A8DB1AB
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
Real-like MAX-SAT instances and the landscape structure across the phase transition
Title of the conference
Proceedings of the Genetic and Evolutionary Computation Conference
Author(s)
Tomassini Marco
Publication state
In Press
Peer-reviewed
Oui
Pages
207-215
Language
english
Abstract
In contrast with random uniform instances, industrial SAT instances of large size are solvable today by state-of-the-art algorithms. It is believed that this is the consequence of the non-random structure of the distribution of variables into clauses. In order to produce benchmark instances resembling those of real-world formulas with a given structure, generative models have been proposed. In this paper we study the MAX-3SAT problem with model-generated instances having a power-law distribution.
Specifically, we target the regions in which computational difficulty undergoes an easy/hard phase transition as a function of clause density and of the power-law exponent. Our approach makes use of a sampling technique to build a graph (local optima network) in which nodes are local optima and directed edges are transitions between optima basins. The objective is to relate the structure of the instance fitness landscape with problem difficulty through the transition.
We succeed in associating the transition with straightforward network metrics, thus providing a novel and original fitness landscape view of the computational features of the power-law model and of its phase transition.
Create date
10/07/2021 18:35
Last modification date
11/07/2021 6:36
Usage data