×

zbMATH — the first resource for mathematics

Analysis of local search landscapes for \(k\)-SAT instances. (English) Zbl 1205.90237
Summary: Stochastic local search is a successful technique in diverse areas of combinatorial optimisation and is predominantly applied to hard problems. When dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase is helpful for an appropriate parameter adjustment of local search-based procedures. In the present paper, we address parameter estimations in the context of landscapes induced by \(k\)-SAT instances: at first, we utilise a sampling method devised by J. Garnier and L. Kallel [SIAM J. Discrete Math. 15, No. 1, 122–141 (2001; Zbl 0992.68039)] for approximations of the number of local maxima in landscapes generated by individual \(k\)-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. The procedure provides good approximations of the actual number of local maxima, with a deviation typically around 10%. Secondly, we provide a method for obtaining upper bounds for the average number of local maxima in \(k\)-SAT instances. The method allows us to obtain the upper bound \(2^{n-O(\sqrt{n/k})}\) for the average number of local maxima, if \(m\) is in the region of \(2 k \cdot n/k\).
MSC:
90C27 Combinatorial optimization
68R99 Discrete mathematics in relation to computer science
Software:
BG-WalkSAT; ChainSAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achlioptas D., Peres Y.: . J. Am. Math. Soc. 17, 947–973 (2004) · Zbl 1093.68075
[2] Alava M., Ardelius J., Aurell E., Kaski P., Krishnamurthy S., Orponen P., Seitz S.: Circumspect descent prevails in solving random constraint satisfaction problems. PNAS USA 105, 15253–15257 (2008)
[3] Albrecht A.A.: A stopping criterion for logarithmic simulated annealing. Computing 78, 55–79 (2006) · Zbl 1130.90021
[4] Albrecht, A.A., Lane, P.C.R., Steinhöfel, K.: Combinatorial landscape analysis for k-SAT instances. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 2498–2504 (2008)
[5] Albrecht A.A., Skaliotis A., Steinhöfel K.: Stochastic protein folding simulation in the d-dimensional HP-model. Comput. Biol. Chem. 32, 248–255 (2008) · Zbl 1159.92016
[6] Barvinok, A.: On the number of matrices and a random matrix with prescribed row and column sums and 0–1 entries. arXiv:0806.1480v2 (2008) · Zbl 1191.15031
[7] Brueggemann T., Kern W.: An improved local search algorithm for 3-SAT. Theor. Comput. Sci. 329, 303–313 (2004) · Zbl 1086.68051
[8] Canfield E.R., Greenhill C., McKay B.D.: Asymptotic enumeration of dense 0–1 matrices with specified line sums. J. Comb. Theory (Series A) 115, 32–66 (2008) · Zbl 1132.05005
[9] Dantsin, E., Wolpert, A.: An improved upper bound for SAT. In: Proceedings of SAT 2005, LNCS, vol. 3569, pp. 400–407 (2005) · Zbl 1128.68460
[10] Garnier J., Kallel L.: Efficiency of local search with multiple local optima. SIAM J. Discrete Math. 15, 122–141 (2002) · Zbl 0992.68039
[11] Gerevini A., Serina I.: Planning as propositional CSP: From WalkSAT to local search techniques for action graphs. Constraints 8, 389–413 (2003) · Zbl 1074.68612
[12] Greenberg H.J., Hart W.E., Lancia G.: Opportunities for combinatorial optimization in computational biology. INFORMS J. Comput. 16, 211–231 (2004) · Zbl 1239.90003
[13] Hagerup T., Rüb C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 33, 305–308 (1990) · Zbl 0702.60021
[14] Hoos H.H., Stützle T.: Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif. Intell. 112, 213–232 (1999) · Zbl 0996.68069
[15] Kaski, P.: Barriers and local minima in energy landscapes of stochastic local search. arXiv:cs/0611103v1 (2006)
[16] Martin O.C., Monasson R., Zecchina R.: Statistical mechanics methods and phase transitions in optimization problems. Theor. Comput. Sci. 265, 3–67 (2001) · Zbl 1032.90075
[17] Mézard M., Zecchina R.: Random K-satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E 66, 056126-1–056126-27 (2002)
[18] Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: Proceedings of 10th National Conference on Artificial Intelligence, pp. 459–465 (1992)
[19] Monasson R., Zecchina R.: Statistical mechanics of the random K-SAT problem. Phys. Rev. E 56, 1357–1361 (1997)
[20] Montanari A., Parisi G., Ricci-Tersenghi F.: Instability of one-step replica-symmetry-broken phase in satisfiability problems. J. Phys. A: Math. Gen. 37, 2073–2091 (2004) · Zbl 1116.82308
[21] Paturi R., Pudlák P., Saks M.E., Zane F.: An improved exponential-time algorithm for k-SAT. J. ACM 52, 337–364 (2005) · Zbl 1297.68217
[22] Reeves C.R., Eremeev A.V.: Statistical analysis of local search landscapes. J. Oper. Res. Soc. 55, 687–693 (2004) · Zbl 1095.90098
[23] Reidys C.M., Stadler P.F.: Combinatorial landscapes. SIAM Rev. 44, 3–54 (2002) · Zbl 0996.92026
[24] Robbins H.: A remark on Stirling’s formula. Am. Math. Mon. 62, 26–29 (1955) · Zbl 0068.05404
[25] Schöning U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32, 615–623 (2002) · Zbl 1050.68049
[26] Schuler P.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms 54, 40–44 (2005) · Zbl 1090.68052
[27] Schuurmans D., Southey F.: Local search characteristics of incomplete SAT procedures. Artif. Intell. 132, 121–150 (2001) · Zbl 0983.68180
[28] Seitz, S., Alava, M., Orponen, P.: Threshold behaviour of WalkSAT and focused Metropolis search on random 3-satisfiability. In: Proceedings of SAT 2005, LNCS, vol. 3569, pp. 475–481 (2005) · Zbl 1128.68482
[29] Seitz S., Orponen P.: An efficient local search method for random 3-satisfiability. Electron. Notes Discrete Math. 16, 71–79 (2003) · Zbl 1179.68147
[30] Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of AAAI, pp. 337–343. MIT Press, Cambridge (1994)
[31] Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: Proceedings of AAAI, pp. 440–446 (1992)
[32] Steinhöfel K., Skaliotis A., Albrecht A.A.: Relating time complexity of protein folding simulation to approximations of folding time. Comput. Phys. Commun. 176, 165–170 (2007)
[33] Wales D.: Energy Landscapes. Cambridge University Press, Cambridge (2003)
[34] Zhang W.: Configuration landscape analysis and backbone guided local search. Part I: satisfiability and maximum satisfiability. Artif. Intell. 158, 1–26 (2004) · Zbl 1085.68678
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.