More Web Proxy on the site http://driver.im/

Article

Efficient and experimental meta-heuristics for MAX-SAT problems

Authors:

Dalila Boughaci,

Habiba DriasAuthors Info & Claims

WEA'05: Proceedings of the 4th international conference on Experimental and Efficient Algorithms

Pages 501 - 512

https://doi.org/10.1007/11427186_43

Published: 10 May 2005 Publication History

Abstract

Many problems in combinatorial optimization are NP-Hard. This has forced researchers to explore meta-heuristic techniques for dealing with this class of complex problems and finding an acceptable solution in reasonable time. The satisfiability problem, SAT, is studied by a great number of researchers the three last decades. Its wide application to the domain of AI in automatic reasoning and problem solving for instance and other domains like VLSI and graph theory motivates the huge interest shown for this problem. In this paper, tabu search, scatter search, genetic algorithms and memetic evolutionary meta-heuristics are studied for the NP-Complete satisfiability problems, in particular for its optimization version namely MAX-SAT. Experiments comparing the proposed approaches for solving MAX-SAT problems are represented. The empirical tests are performed on DIMACS benchmark instances.

References

[1]

D. Boughaci H. Drias "Solving Weighted Max-Sat Optimization Problems Using a Taboo Scatter Search Meta-heuristic". In proceedings of ACM Sac 2004, pp35-36, 2004.

Digital Library

[2]

D. Boughaci, H. Drias "PTS: A Population-based Tabu Search for the Maximum Satisfiability Problems", in the Proceedings of the 2 IEEE GCC conferences, pp 622-625, 2004.

[3]

D. Boughaci, Drias H and Benhamou B. 2004. "Solving Max-Sat Problems Using a memetic evolutionary Meta-heuristic", in proceedings of 2004 IEEE CIS, pp 480-484, 2004.

[4]

D. Boughaci and H. Drias, "Taboo Search as an Intelligent Agent for Bid Evaluation", in proceedings of CE2003, book1, pages 43-48, Portugal, 2003.

[5]

S.Cook. "The Complexity of Theorem Proving Procedures", in the Proceedings of the 3rdAnnual ACM Symposium on the Theory of Computing, 1971.

Digital Library

[6]

M. Davis, G. Putnam, and D. Loveland. "A machine program for theorem proving", communication of the ACM, 394-397, Jul 1962.

Digital Library

[7]

H. Drias. "Scatter search with walk strategy for solving hard Max-W-Sat problems", in proceedings of IEA- AIE2001, lectures note in computer science, LNAI-2070, Springer, Budapest, 35-44, 2001.

Digital Library

[8]

J. Frank, "A study of genetic algorithms to find approximate solutions to hard 3CNF problems", in proceedings of Golden West international conference on artificial intelligence, 1994.

[9]

MR. Garey, S. Johnson. "Computer and intractability, a guide to the theory of NPCompleteness, Freeman company Sanfranscsco, 1978.

Digital Library

[10]

F. Glover, "Future paths for integer programming and links to Artificial intelligence", operational search, vol 31, 1986.

Digital Library

[11]

F. Glover, "Tabu search": Part I, ORSA, journal on computing, 1989.

[12]

D. E Goldberg,."Genetic Algorithms in search, Optimization & Machine Learning". Wokingham, Addison-Wesley. 1989)

Digital Library

[13]

P. Greistorfer, "A Tabu Scatter search meta-heuristic for the arc routing problem", submitted to Elsevier Science February 2002.

[14]

P. Hansen P; B. Jaumard. "Algorithms for the Maximum Satisfiability", journal of computing 44-279-303, 1990.

Digital Library

[15]

H. H. Hoos and T. Stutzle. SATLIB: An online resource for research on SAT. In I. Gent, H. van Maaren, and T. Walsh, editors, SAT2000: Highlights of Satisfiability Research in theYear 2000, Frontiers in Artificial Intelligence and Applications, pages 283-292. Kluwer Academic, 2000.

[16]

S. Johnson. "Approximation algorithms for combinatorial problems", Journal of Computer and System Sciences 9, 256-278, 1974.

Digital Library

[17]

SA. Kauffman, Levin." Towards a general theory of adaptive walks on rugged landscapes", J theory. Biol, 128,pp, 11, 1987.

[18]

M. Laguna, F. Glover "Scatter Search", Graduate school of business, University of Colorado, Boulder, 1999.

[19]

M. Laguna., R. Marti and V Campos, "Scatter Search for the linear ordering problem", University of Colorado, Boulder, 1999.

[20]

CM. Li., "Exploiting yet more the power of unit clause propagation to solve 3-sat problem", in ECAI 96, workshop on advances in propositional deduction, pqges 11-16, Boudapest, Hungray, 1996.

[21]

CMLi and. Anbulagan, "Heuristic based on unit propagation for satisfiability", in Proceedings of CP 97, springer-Verlag, LNCS 1330, pp 342-356, Austria, 1997.

[22]

B. Mazure, L. Sais and E. Greroire,." A Tabu search for Sat", in proceedings of AAAI 1997.

Digital Library

[23]

P. Moscato. "On evolution, search, optimization, genetic algorithms and martial arts: toward memetic algorithms", 1989.

[24]

PM. Pardalos, L. Pitsoulis and MGC. Resende. "A Parallel GRASP for MAX-SAT Problems. PARA96 Workshop on Applied Parallel Computing in Industrial Problems and Optimization", Lynghy. Denmark August 18-21, 1996.

Digital Library

[25]

B. Selman, A. Henry, Z. Kautz and B.Cohen. "Local Search Strategies for Satisfiability Testing", presented at the second DIMACS Challenge on Cliques, Coloring, and Satisfiability, October 1993

[26]

E. Taillard, "Parallel Taboo search techniques for Job Shop Scheduling problem", ORSA Journal on Computing, 6:108-117, 1994.

[27]

N. A. Wassan, and I. H. Osman, "Tabu search variants for the mix fleet vehicle routing problem", Tech. rep., School of Business, American University of Beirut, forthcoming in J. Opl Res. Soc, 2002.

Cited By

Watanabe OYamamoto M(2010)Average-case analysis for the MAX-2SAT problemTheoretical Computer Science10.1016/j.tcs.2009.12.020411:16-18(1685-1697)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.12.020
Sudholt D(2009)The impact of parametrization in memetic evolutionary algorithmsTheoretical Computer Science10.1016/j.tcs.2009.03.003410:26(2511-2528)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.03.003

Efficient and experimental meta-heuristics for MAX-SAT problems

Recommendations

A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033-1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile ...
Solving weighted Max-Sat optimization problems using a Taboo Scatter Search metaheuristic
SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

In the last three decades, many researchers have focused on the Satisfiability problem and on many of its variants, in particular, on the Weighted Maximum Satisfiability problem (Max-W-Sat). The latter is known to be difficult to solve, due to a high ...
Guided Local Search for Solving SAT and Weighted MAX-SAT Problems

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

WEA'05: Proceedings of the 4th international conference on Experimental and Efficient Algorithms

May 2005

621 pages

ISBN:3540259201

Editor:
Sotiris E. Nikoletseas
CTI and Univ. of Patras, Greece

Sponsors

FLAGS: EU-FET R&D project "Foundational Aspects of Global Computing Systems"
DELIS: EU-FET R&D project "Dynamically Evolving, Large-Scale Information Systems"
Ministry of Natural Education and Religious Affairs: Ministry of Natural Education and Religious Affairs
RACTI: Research Academic Computer Technology Institute

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 May 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Watanabe OYamamoto M(2010)Average-case analysis for the MAX-2SAT problemTheoretical Computer Science10.1016/j.tcs.2009.12.020411:16-18(1685-1697)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.12.020
Sudholt D(2009)The impact of parametrization in memetic evolutionary algorithmsTheoretical Computer Science10.1016/j.tcs.2009.03.003410:26(2511-2528)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.03.003

View Options

View options

Media

Figures

Other

Tables

View Table of Contents