research-article

Reducing the cost of partition crossover on large MAXSAT problems: the PX-preprocessor

Authors:

Preston Dunton,

Darrell WhitleyAuthors Info & Claims

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 694 - 702

https://doi.org/10.1145/3512290.3528748

Published: 08 July 2022 Publication History

Abstract

Combining Iterated Local Search with Partition Crossover (PX) has the potential to be a powerful hybrid search strategy for MAX-kSAT problems. The disadvantage of standard Partition Crossover is that it touches every variable and every clause. This paper borrows strategies from WalkSAT to improve Partition Crossover such that it only touches a fraction of clauses by focusing on unsatisfied clauses. On average, it is possible to speed up Partition Crossover by one or two orders of magnitude. The PX-preprocessor also simplifies the interface between Partition Crossover and local search. Partition Crossover is compared with and without the PX-preprocessor on 478 SAT instances from the 2014 SAT competition; PX is particularly effective on application problems and larger problem instances.

Supplemental Material

ZIP File

Supplemental material.

Download
19.18 KB

References

[1]

A Balint and A Fröhlich. 2010. Improving stochastic local search for SAT with a new probability distribution. In SAT 2010. Springer.

Digital Library

[2]

A Belov, D Diepold, M Heule, and M Järvisalo. 2014. The 2014 Sat Competition Benchmarks. http://www.satcompetition.org/2014/downloads.shtml . December 1, 2021.

[3]

W Chen and D Whitley. 2017. Decomposing SAT instances MAX-kSAT with Pseudo Backbones. In European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, LNCS 10197, 75--90.

[4]

W. Chen, D. Whitley, R. Tinós, and F. Chicano. 2018. Tunneling between Plateaus: Improving on a state-of-the-art MAXSAT Solver using Partition Crossover. In Genetic and Evolutionary Computation Conference (GECCO). ACM, 921--928.

[5]

N Eén and A Biere. 2006. Effective preprocessing in SAT through variable and clause elimination. In SAT 2006, LNCS 3569. Springer, 61--75.

[6]

J. Frank, P. Cheeseman, and J. Stutz. 1997. When Gravity Fails: Local Search Topology. Journal of Artificial Intelligence Research 7 (1997), 249--281.

Digital Library

[7]

A Hagberg, D Schult, and P Swart. 2008. Exploring network structure, dynamics, and function using NetworkX. In The 7th Python in Science Conference (SciPy2008). SciPy, 11--15.

[8]

H.H. Hoos and Th. Stützle. 2004. Stochastic Local Search: Foundations and Applications. Morgan Kaufman.

[9]

H. H. Hoos. 1999. On the run-time behaviour of stochastic local search algorithms for SAT. In Proc of AAAI. 661--666.

[10]

Z Lei, S Cai, C Luo, and H Hoos. 2021. Efficient Local Search for Pseudo Boolean Optimization. In Theory and Applications of Satisfiability Testing. Springer, LNCS 12831, 332--348.

[11]

C Lin, W Wei, and H Zhang. 2007. Combining adaptive noise and look-ahead in local search for SAT. In SAT 2007. Springer, 121--133.

[12]

Bart Selman, Henry Kautz, and Bram Cohen. 1996. Local Search Strategies for Satisfiability Testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science, David S. Johnson and Michael A. Trick (Eds.). Vol. 26. AMS.

[13]

B. Selman, H. Levesque, and D. Mitchell. 1992. A New Method for Solving Hard Satisfiability Problems. In The National Conference on Artificial Intelligence (AAAI). San Jose, CA, 44--446.

[14]

R. Tinós, D. Whitley, and F. Chicano. 2015. Partition Crossover for Pseudo-Boolean Optimization. In Foundations of Genetic Algorithms, (FOGA-15). 137--149.

[15]

Dave A. D. Tompkins and Holger H. Hoos. 2005. UBCSAT: An Implementation and Experimentation Environment for SLS Algorithms for SAT and MAX-SAT. In Theory and Applications of Satisfiability Testing: Revised Selected Papers of the Seventh International Conference (SAT 2004) (Lecture Notes in Computer Science), Holger H. Hoos and David G. Mitchell (Eds.), Vol. 3542. Springer Verlag, Berlin, Germany, 306--320.

[16]

D. Whitley, A. Howe, and D. Hains. 2013. Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT. In The National Conference on Artificial Intelligence (AAAI). 940--946.

Cited By

Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Whitley DOchoa GChicano F(2024)Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_24(393-408)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_24
Whitley DOchoa GFloyd NChicano F(2024)Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under RecombinationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-57712-3_8(113-128)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57712-3_8

Index Terms

Reducing the cost of partition crossover on large MAXSAT problems: the PX-preprocessor
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Tunneling between plateaus: improving on a state-of-the-art MAXSAT solver using partition crossover
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

There are two important challenges for local search algorithms when applied to Maximal Satisfiability (MAXSAT). 1) Local search spends a great deal of time blindly exploring plateaus in the search space and 2) local search is less effective on ...
Partition Crossover can Linearize Local Optima Lattices of k-bounded Pseudo-Boolean Functions
FOGA '23: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

When Partition Crossover is used to recombine two parents which are local optima, the offspring are all local optima in the smallest hyperplane subspace that contains the two parents. The offspring can also be organized into a non-planar hypercube "...
Partition Crossover for Pseudo-Boolean Optimization
FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

A partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

July 2022

1472 pages

ISBN:9781450392372

DOI:10.1145/3512290

Editor:
Jonathan E. Fieldsend
University of Exeter
,
General Chair:
Markus Wagner
The University of Adelaide

Copyright © 2022 ACM.

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]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Data Availability

Supplemental material. https://dl.acm.org/doi/10.1145/3512290.3528748#p694-dunton-suppl.zip

Conference

GECCO '22

Sponsor:

SIGEVO

GECCO '22: Genetic and Evolutionary Computation Conference

July 9 - 13, 2022

Massachusetts, Boston

Acceptance Rates

Overall Acceptance Rate 1,223 of 3,289 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
55
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Whitley DOchoa GChicano F(2024)Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_24(393-408)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_24
Whitley DOchoa GFloyd NChicano F(2024)Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under RecombinationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-57712-3_8(113-128)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57712-3_8

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.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents