poster

Complexity of Max-SAT using stochastic algorithms

Authors:

Mohamed Qasem,

Adam Prugel-BennettAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 615 - 616

https://doi.org/10.1145/1389095.1389219

Published: 12 July 2008 Publication History

Get Access

Abstract

Hill-climbing has been shown to be more effective than exhaustive search in solving satisfiability problems. Also, it has been used either by itself or in combination with other methods to solve the most difficult region of SAT, the phase transition. We show that hill-climbing also finds SAT problems difficult around the phase transition. It too follows an easy-hard-eays transition.

References

[1]

J. M. Crawford and L. D. Auton. Experimental results on the crossover point in random 3-SAT. Artificial Intelligence, 81(1-2):31--57, 1996.

Digital Library

Google Scholar

[2]

D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. pages 459--465, San Jose, CA, USA, 1992. Publ by AAAI, Menlo Park, CA, USA.

Google Scholar

[3]

R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic ‘phase transitions'. Nature, 400(6740):133--7, 1999.

Crossref

Google Scholar

[4]

B. Selman. Stochastic search and phase transitions: AI meets physics. volume vol.1 of IJCAI-95. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 998--1002, Montreal, Que., Canada, 1995. Morgan Kaufmann Publishers.

Digital Library

Google Scholar

[5]

Z. Weixiong. Phase transitions and backbones of 3-SAT and maximum 3-SAT. Principles and Practice of Constraint Programming -- CP 2002. 7th International Conference, CP 2001. Proceedings (Lecture Notes in Computer Science Vol.2239), pages 153--67, Paphos, Cyprus, 2001. Springer-Verlag.

Digital Library

Google Scholar

Cited By

View all

Najaran M(2021)How to exploit fitness landscape properties of timetabling problem: A new operator for quantum evolutionary algorithmExpert Systems with Applications10.1016/j.eswa.2020.114211168(114211)Online publication date: Apr-2021
https://doi.org/10.1016/j.eswa.2020.114211
Tayarani-N. MPrügel-Bennett A(2015)Quadratic assignment problem: a landscape analysisEvolutionary Intelligence10.1007/s12065-015-0132-z8:4(165-184)Online publication date: 22-May-2015
https://doi.org/10.1007/s12065-015-0132-z
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Show More Cited By

Index Terms

Complexity of Max-SAT using stochastic algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
2. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Regular Random k-SAT: Properties of Balanced Formulas

We consider a model for generating random k -SAT formulas, in which each literal occurs approximately the same number of times in the formula clauses (regular random and k -SAT). Our experimental results show that such regular random k -SAT instances ...
A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

Given a CNF (conjunctive normal form) Boolean expression with clauses of size at most two, the Max-2-SAT problem asks to find a truth assignment to the Boolean variables that makes true the maximum number of clauses. In this paper, we describe an ...
Iterative SAT Solving for Minimum Satisfiability
ICTAI '12: Proceedings of the 2012 IEEE 24th International Conference on Tools with Artificial Intelligence - Volume 01

Minimum Satisfiability (MinSAT) denotes one of the optimization versions of the Boolean Satisfiability (SAT) problem. In some settings MinSAT is preferred to using Maximum Satis-fiability (MaxSAT). Several encodings and dedicated branch and bound ...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
114
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Najaran M(2021)How to exploit fitness landscape properties of timetabling problem: A new operator for quantum evolutionary algorithmExpert Systems with Applications10.1016/j.eswa.2020.114211168(114211)Online publication date: Apr-2021
https://doi.org/10.1016/j.eswa.2020.114211
Tayarani-N. MPrügel-Bennett A(2015)Quadratic assignment problem: a landscape analysisEvolutionary Intelligence10.1007/s12065-015-0132-z8:4(165-184)Online publication date: 22-May-2015
https://doi.org/10.1007/s12065-015-0132-z
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Qasem MPrügel-Bennett A(2010)Learning the large-scale structure of the MAX-SAT landscape using populationsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.203357914:4(518-529)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1109/TEVC.2009.2033579
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6
Qasem MPrügel-Bennett A(2009)Improving Performance in Combinatorial Optimisation Using Averaging and ClusteringProceedings of the 9th European Conference on Evolutionary Computation in Combinatorial Optimization10.1007/978-3-642-01009-5_16(180-191)Online publication date: 10-Apr-2009
https://dl.acm.org/doi/10.1007/978-3-642-01009-5_16

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Regular Random k-SAT: Properties of Balanced Formulas

A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

Iterative SAT Solving for Minimum Satisfiability

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations