Tabu search for maximal constraint satisfaction problems

1. P. Cheeseman, B. Kanefsky and W.M. Taylor, “Where the really hard problems are”, Proc. of the 12th IJCAP90, ppl63–169, 1991.

   Google Scholar 

2. D.A. Clark, J. Frank, I.P. Gent, E. MacIntyre, N. Tomov, T. Walsh, “Local search and the number of solutions”, Proc. of CP97, pp119–133, 1996.

   Google Scholar 

3. C. Fleurent and J.A. Ferland, “Genetic and hybrid algorithms for graph coloring”, to appear in G. Laporte, I. H. Osman, and P. L. Hammer (Eds.), Special Issue Annals of Operations Research, “Metaheuristics in Combinatorial Optimization”.

   Google Scholar 

4. E.C. Freuder and R.J. Wallace, “Partial constraint satisfaction”, Artificial Intelligence, Vol.58(1–3) pp21–70, 1992.

   Google Scholar 

5. F. Glover and M. Laguna, “Tabu Search”, in C. R. Reeves (Ed.), Modern heuristics for combinatorial problems, Blackwell Scientific Publishing, Oxford, GB, 1993.

   Google Scholar 

6. J.K. Hao and R. Dorne, “Empirical studies of heuristic local search for constraint solving”, Proc. of CP-96, LNCS 1118, pp194–208, Cambridge, MA, USA, 1996.

   Google Scholar 

7. P. Hensen and B. Jaumard, “Algorithms for the maximum satisfiability problem”, Computing Vol.44, pp279–303, 1990.

   Google Scholar 

8. A. Hertz and D. de Werra, “Using Tabu search techniques for graph coloring”. Computing Vol.39, pp345–351, 1987.

   Google Scholar 

9. T. Hogg, B.A. Huberman and C.P. Williams, Artificial Intelligence, Special Issue on the Phase Transition and Complexity. Vol 82, 1996.

   Google Scholar 

10. D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, “How easy is local search?” Journal of Computer and System Sciences, Vol.37(1), pp79–100, Aug. 1988.

    Google Scholar 

11. S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, “Optimization by simulated annealing”, Science No.220, pp671–680, 1983.

    Google Scholar 

12. J. Larrosa and P. Meseguer, “Optimization-based heuristics for maximal constraint satisfaction”, Proc. of CP-95, pp190–194, Cassis, France, 1995.

    Google Scholar 

13. A.K. Mackworth, “Constraint satisfaction”, in S.C. Shapiro (Ed.) Encyclopedia on Artificial Intelligence, John Wiley & Sons, NY, 1987.

    Google Scholar 

14. S. Minton, M.D. Johnston and P. Laird, “Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems”, Artificial Intelligence, Vol.58(1–3), pp161–206, 1992.

    Google Scholar 

15. P. Morris, “The Breakout method for escaping from local minima”, Proc. of AAAI-93, pp40–45, 1993.

    Google Scholar 

16. C.H. Papadimitriou and K. Steiglitz, “Combinatorial optimization — algorithms and complexity”, Prentice Hall, 1982.

    Google Scholar 

17. B. Selman and H.Kautz, “Domain-independent extensions to GSAT: solving large structured satisfiability problems”, Proc. of IJCAI-93, Chambery, France, 1993.

    Google Scholar 

18. B.M. Smith, “Phase transition and the mushy region in constraint satisfaction problems”, Proc. of ECAI94, pp100–104, 1994.

    Google Scholar 

19. E. Tsang, “Foundations of constraint satisfaction”, Academic Press, 1993.

    Google Scholar 

20. R.J. Wallace, “Enhancements of branch and bound methods for the maximal constraint satisfaction problem”, Proc. of AAAI-96, ppl88–196, Portland, Oregon, USA, 1996.

    Google Scholar 

21. R.J. Wallace, “Analysis of heuristics methods for partial constraint satisfaction problems”, Proc. of CP-96, LNCS 1118, pp308–322, Cambridge, MA, USA, 1996.

    Google Scholar 

22. N. Yugami, Y. Ohta and H. Hara, “Improving repair-based constraint satisfaction methods by value propagation”, Proc. of AAAI-94, pp344–349, Seattle, WA, 1994.

    Google Scholar 

Download references