Back to Search
Start Over
[Untitled]
- Source :
- Journal of Automated Reasoning. 24:205-223
- Publication Year :
- 2000
- Publisher :
- Springer Science and Business Media LLC, 2000.
-
Abstract
- In this paper, we show how Guided Local Search (GLS) can be applied to the SAT problem and show how the resulting algorithm can be naturally extended to solve the weighted MAX-SAT problem. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real-life problems, such as the traveling salesman problem, BT"s workforce scheduling problem, the radio link frequency assignment problem, and the vehicle routing problem. We present empirical results of applying GLS to instances of the SAT problem from the DIMACS archive and also a small set of weighted MAX-SAT problem instances and compare them with the results of other local search algorithms for the SAT problem.
- Subjects :
- Mathematical optimization
business.industry
Iterated local search
2-opt
Function problem
Computational Theory and Mathematics
Artificial Intelligence
Cutting stock problem
Local search (optimization)
Guided Local Search
Computational problem
business
Software
Generalized assignment problem
Mathematics
Subjects
Details
- ISSN :
- 01687433
- Volume :
- 24
- Database :
- OpenAIRE
- Journal :
- Journal of Automated Reasoning
- Accession number :
- edsair.doi...........5a2a238d18f63da214cfc2e4500203d7