Software: Backbone Guided WalkSAT for SAT and Max-SAT with Dynamic Noise Ratio Here is the package of programs we developed for the backbone guided WalkSAT algorithm with dynamic noise ratio for SAT and Max-SAT. Our software was built on top of the WalkSAT local search algorithm and software (downloaded from Henry Kautz’s homepage). The original idea of the dynamic noise ratio method was due to Holger Hoos. We implemented (after some struggling effort) and tested it on 3-SAT and Max-3-SAT. To learn more about the backbone guided local search method with dynamic noise ratio, take a look at a paper presented at IJCAI-03. The package can be downloaded as a gzipped tar file or a WinZip file. Use ”tar -zxvf filename” to unzip the package. See the README file for details on installation and usage. We used a Linux box for the development and test. Note: The README file should be sufficient for a quick installation and use of the software. We cannot guarantee any support. (Source:

References in zbMATH (referenced in 22 articles )

Showing results 1 to 20 of 22.
Sorted by year (citations)

1 2 next

  1. Jarvis, Padraigh; Arbelaez, Alejandro: Cooperative parallel SAT local search with path relinking (2020)
  2. Zhang, Yueling; Zhang, Min; Pu, Geguang; Song, Fu; Li, Jianwen: Towards backbone computing: a greedy-whitening based approach (2018)
  3. Chen, Wenxiang; Whitley, Darrell: Decomposing SAT instances with pseudo backbones (2017)
  4. Karimi, Hamed; Rosenberg, Gili: Boosting quantum annealer performance via sample persistence (2017)
  5. Jäger, Gerold; Climer, Sharlee; Zhang, Weixiong: The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability (2016)
  6. Ries, Jana; Beullens, Patrick; Salt, David: Instance-specific multi-objective parameter tuning based on fuzzy logic (2012)
  7. Albrecht, A. A.; Lane, P. C. R.; Steinhöfel, K.: Analysis of local search landscapes for (k)-SAT instances (2010)
  8. Marques-Silva, Joao; Janota, Mikoláš; Lynce, Inês: On computing backbones of propositional theories (2010)
  9. Riff, María Cristina; Montero, Elizabeth; Neveu, Bertrand: C-strategy: a dynamic adaptive strategy for the CLONALG algorithm (2010)
  10. Gao, Yong: Data reductions, fixed parameter tractability, and random weighted (d)-CNF satisfiability (2009)
  11. Helsgaun, Keld: General (k)-opt submoves for the Lin-Kernighan TSP heuristic (2009)
  12. Boughaci, Dalila; Benhamou, Belaïd; Drias, Habiba: Scatter search and genetic algorithms for MAX-SAT problems (2008)
  13. Jiang, He; Zhang, XianChao; Chen, GuoLiang; Li, MingChu: Backbone analysis and algorithm design for the quadratic assignment problem (2008)
  14. Loudni, Samir; Boizumault, Patrice: Combining VNS with constraint programming for solving anytime optimization problems (2008)
  15. Fourdrinoy, Olivier; Grégoire, Éric; Mazure, Bertrand; Saïs, Lakhdar: Eliminating redundant clauses in SAT instances (2007)
  16. Jiang, He; Chen, Guoliang: Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem (2007)
  17. Richter, Dirk; Goldengorin, Boris; Jäger, Gerold; Molitor, Paul: Improving the efficiency of Helsgaun’s Lin-Kernighan heuristic for the symmetric TSP (2007)
  18. Cadoli, Marco; Mancini, Toni: Automated reformulation of specifications by safe delay of constraints (2006)
  19. Streeter, M. J.; Smith, S. F.: How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines (2006)
  20. Prestwich, Steven: Random walk with continuously smoothed variable weights (2005)

1 2 next