Authors: Matijević, Luka 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: General Variable Neighbourhood Search Approach to MAX-3SAT Problem
First page: 29
Last page: 30
Conference: The 8TH International Conference on Logic and Applications - LAP 2019
Issue Date: 2019
Rank: M34
URL: http://imft.ftn.uns.ac.rs/math/cms/uploads/Main/LAP_2019_Book_of_Abstracts.pdf
Abstract: 
MAX-3SAT problem is a version of MAX-SAT problem where every clause
has exactly three literals. It is one of the most important problems of compu-
tational complexity theory, and as such, many solvers have been developed for
it. Since it belongs to the class of NP-complete problems, it is usually solved
by implementing heuristic methods.
In this paper we used general variable neighbourhood search (GVNS) to
obtain the best possible solution in a given amount of time. GVNS is neighbor-
hood based search algorithm that involves two main steps: perturbation and
improvement. We defined two sets of neighbourhoods, each of them used in the
perturbation step with a predefined probability p. For the improvement step we
used variable neighbourhood descent (VND), which is a local search heuristic
that explores several neighborhood structures in a deterministic way.
The proposed GVNS approach is tested on a set of benchmark instances
found at: https://www.cs.ubc.ca/ hoos/SATLIB/benchm.html, and compared
with state-of-the-art WalkSAT implementation:
http://www.cs.rochester.edu/u/kautz/walksat/. We concluded that for smaller
instances our approach gives similar results as aforementioned WalkSAT imple-
mentation, but it performed better for larger instances, given that it finds very
good solutions very quickly.
Keywords: satisfiability problem | NP-completeness | incomplete solvers | stochastic algorithms | metaheuristic approach
Publisher: University Center Dubrovnik, Croatia,
Project: Representations of logical structures and formal languages and their application in computing 

Show full item record

Page view(s)

13
checked on Dec 3, 2021

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.