Reactive search, a history-sensitive heuristic for MAX-SAT

ABSTRACT

The Reactive Search (RS) method proposes the integration of a simple history-sensitive (machine learning) scheme into local search for the on-line determination of free parameters. In this paper a new RS algorithm is proposed for the approximated solution of the Maximum Satisfiability problem: a component based on local search with temporary prohibitions (Tabu Search) is complemented with a reactive scheme that determines the appropriate value of the prohibition parameter by monitoring the Hamming distance along the search trajectory. The proposed algorithm (H-RTS) can therefore be characterized as a dynamic version of Tabu Search.In addition, the non-oblivious functions recently introduced in the framework of approximation algorithms are used to discover a better local optimum in the initial part of the searchThe algorithm is developed in two phases. First the bias-diversification properties of individual candidate components are analyzed by extensive empirical evaluation, then a reactive scheme is added to the winning component, based on Tabu Search.The final tests on a benchmark of random MAX-3-SAT and MAX-4-SAT problems demonstrate the superiority of H-RTS with respect to alternative heuristics.

REFERENCES

• 1: {1} E. H. L. Aarts, J.H.M. Korst, and P.J. Zwietering, "Deterministic and randomized local search," in <i>Mathematical Perspectives on Neural Networks</i>, edited by M. Mozer P. Smolensky and D. Rumelhart (Hillsdale,NJ:Lawrence Erlbaum Publishers, to appear).
• 2: {2} A. V. Aho, D. S. Johnson, R. M. Karp, S. R. Kosaraju, C. C. McGeoch, C. H. Papadimitriou, and P. Pevzner, "Theory of Computing: Goals and Directions," University of Washington Tech. Rep. CSE-93-03, to appear in <i>Computing Surveys</i>.
• 3: Paolo Alimonti, New local search approximation techniques for maximum generalized satisfiability problems, Proceedings of the second Italian conference on Algorithms and complexity, p.40-53, March 1994, Rome, Italy
• 4: G. Ausiello , P. Crescenzi , M. Protasi, Approximate solution of NP optimization problems, Theoretical Computer Science, v.150 n.1, p.1-55, Oct. 16, 1995 [doi>10.1016/0304-3975(94)00291-P]
• 5: {5} R. S. Barr, B. L. Golden, J. P. Kelly, M. G. C. Resende, and W. Stewart, "Designing and Reporting on Computational Experiments with Heuristic Methods," <i>Journal of Heuristics</i> <b>1(1)</b> (1996), 9-32.
• 6: {6} R. Battiti, "Reactive Search: Toward Self-Tuning Heuristics," in <i>Modern Heuristic Search Methods</i>, edited by V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, and G. D. Smith (John Wiley and Sons Ltd, 1996), 61-83.
• 7: {7} R. Battiti and M. Protasi, "Solving MAX-SAT with non-oblivious functions and history-based heuristics," DIMACS Workshop on Satisfiability, March 11-13, 1996, Rutgers University.
• 8: {8} R. Battiti and M. Protasi, "Reactive local search for the Maximum Clique problem," Tech. Rept. TR-95- 052, International Computer Science Institute, Berkeley, CA, 1995.
• 9: {9} R. Battiti and G. Tecchiolli, "The reactive tabu search," <i>ORSA Journal on Computing</i> <b>6(2)</b> (1994), 126- 140.
• 10: {10} I.P. Gent and T. Walsh, "Towards an understanding of hill-climbing procedures for SAT," Preprint, 1993.
• 11: {11} F. Glover, "Tabu search-part I," <i>ORSA Journal on Computing</i> <b>1(3)</b> (1989), 190-260.
• 12: {12} M. K. Goldberg and D. L. Hollinger, "Learning Better Algorithms for the Maximum Clique Problem," Tech. Report, Rensselaer Polytechnic Institute, Jan 1996.
• 13: Jun Gu, Parallel algorithms and architectures for very fast AI search, University of Utah, Salt Lake City, UT, 1991
• 14: Jun Gu, Efficient local search for very large-scale satisfiability problems, ACM SIGART Bulletin, v.3 n.1, p.8-12, Jan. 1992 [doi>10.1145/130836.130837]
• 15: {15} J. Gu, P. W. Purdom, J. Franco, and B.W. Wah, "Algorithms for the Satisfiability (SAT) Problem: a Survey," Preliminary version, 1996.
• 16: {16} D.S. Johnson, "Approximation algorithms for combinatorial problems," <i>J. of Computer and System Sciences </i> <b>9</b> (1974), 256-278.
• 17: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991 [doi>10.1287/opre.39.3.378]
• 18: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 19: Pierre Hansen , Brigitte Jaumard, Algorithms for the maximum satisfiability problem, Computing, v.44 n.4, p.279-303, Feb. 4, 1990 [doi>10.1007/BF02241270]
• 20: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 21: {21} J. Hooker, "Testing Heuristics: We Have it All Wrong," <i>Journal of Heuristics</i> <b>1(1)</b> (1996), 33-42.
• 22: {22} S.Khanna, R.Motwani, M.Sudan, and U.Vazirani, "On syntactic versus computational views of approximability," <i>Proceedings 35th Ann. IEEE Symp. on Foundations of Computer Science</i>, (1994), 819-836,.
• 23: Long-Ji Lin, Self-Improving Reactive Agents Based on Reinforcement Learning, Planning and Teaching, Machine Learning, v.8 n.3-4, p.293-321, May 1992 [doi>10.1007/BF00992699]
• 24: {24} S. Minton, M. D. Johnston, A. B. Philips, and P. Laird, "Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method," <i>Proceedings AAAI-90</i>, (1990), 17-24.
• 25: {25} S. Minton, "Automatically Configuring Constraint Satisfaction Programs: A Case Study," <i>Constraints, An International Journal</i> <b>1</b> (1996), 7-43.
• 26: {26} D. Mitchell, B. Selman, and H. Levesque, "Hard and easy distributions of sat problems," <i>Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Jose, Ca</i> (1992), 459-465.
• 27: {27} P. Pardalos, "Continuous approaches to discrete optimization problems," in <i>Nonlinear optimization and applications</i>, edited by G. Di Pillo and F. Giannessi, (Plenum Publishing, 1995).
• 28: {28} B. Selman and H.A. Kautz, "An empirical study of greedy local search for satisfiability testing," <i>Proceedings of the eleventh national Conference on Artificial Intelligence (AAAI-93), Washington, D. C.</i>, 1993.
• 29: Bart Selman , Henry A. Kautz , Bram Cohen, Noise strategies for improving local search, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.337-343, October 1994, Seattle, Washington, United States
• 30: {30} B. Selman, H.A. Kautz, and B. Cohen, "Local search strategies for satisfiability testing," <i>Proceedings of the Second DIMACS Algorithm Implementation Challenge on Cliques, Coloring and Satisfiability, Oct. 1993</i>, edited by M. Trick and D. S. Johnson, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, to appear.
• 31: {31} B. Selman, H. Levesque, and D. Mitchell, "A new method for solving hard satisfiability problems," <i>Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), San Jose, Ca</i>, (9992), 440-446.
• 32: {32} S. Singh and D. Bertsekas, "Reinforcement Learning for Dynamic Channel Allocation in Cellular Telephone Systems," <i>Proceedings of NIPS96</i>, in press.
• 33: {33} I.P. Gent and T. Walsh, "An empirical analysis of search in GSAT," <i>Journal of Artificial Intelligence Research</i> <b>1</b> (1993), 47-59.
• 34: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods