An automaton Constraint for Local Search

• Autorzy: He J. , Flener P. , Pearson J.
• Języki publikacji: EN

Abstrakty

EN

We explore the idea of using automata to implement new constraints for local search. This is already a successful approach in constraint-based global search. We show how to maintain the violations of a constraint and its variables via a deterministic finite automaton that describes a ground checker for that constraint. We extend the approach to counter automata, which are often much more convenient than finite automata, if not more independent of the constraint instance. We establish the practicality of our approach on several real-life combinatorial problems.

Słowa kluczowe

EN

automaton constraint; counter automaton; local search

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 2/3
• Strony: 223--248
• Opis fizyczny: Bibliogr. 20 poz., tab., wykr.

Twórcy

autor

He J.

autor

Flener P.

autor

Pearson J.

• Department of Information Technology Uppsala University, Box 337, SE-751 05 Uppsala, Sweden,

Bibliografia

• [1] Ǻgren,M., Flener, P., Pearson, J.: Generic incremental algorithms for local search, Constraints, 12(3), September 2007, 293-324.
• [2] Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers, Proceedings of CP'04 (M. Wallace, Ed.), LNCS 3258, Springer-Verlag, 2004, 107-122.
• [3] Beldiceanu, N., Carlsson, M., Rampon, J.-X.: Global constraint catalogue: Past, present, and future, Constraints, 12(1), March 2007, 21-62, The catalogue is at http://www.emn.fr/x-info/sdemasse/gccat.
• [4] Cheng, K. C. K., Yap, R. H. C.: Maintaining generalized arc consistency on ad hoc r-ary constraints, Proceedings of CP'08 (P. J. Stuckey, Ed.), LNCS 5202, Springer-Verlag, 2008, 509-523.
• [5] Dincbas, M., Simonis, H., Van Hentenryck, P.: Solving the car-sequencing problem in constraint logic programming, Proceedings of ECAI'88 (Y. Kodratoff, Ed.), Pitman, 1988, 290-295.
• [6] He, J., Flener, P., Pearson, J.: Toward an automaton constraint for local search, Proceedings of LSCS'09, the 6th International Workshop on Local Search Techniques in Constraint Satisfaction (Y. Deville, C. Solnon, Eds.), Electronic Proceedings in Theoretical Computer Science 5, 2009, 13-25.
• [7] Hopcroft, J. E., Motwani, R., Ullman, J. D.: Introduction to Automata Theory, Languages, and Computation, 3rd edition, Addison-Wesley, 2007.
• [8] Lagerkvist, M. Z.: Techniques for Efficient Constraint Propagation, KTH - Royal Institute of Technology, Stockholm, Sweden, November 2008, Licentiate Thesis.
• [9] Laporte, G.: The art and science of designing rotating schedules, Journal of the Operational Research Society, 50(10), October 1999, 1011-1017.
• [10] Michel, L., Van Hentenryck, P.: Localizer: A modeling language for local search, Proceedings of CP'97 (G. Smolka, Ed.), LNCS 1330, Springer-Verlag, 1997, 237-251.
• [11] Pesant, G.: A regular language membership constraint for finite sequences of variables, Proceedings of CP'04 (M. Wallace, Ed.), LNCS 3258, Springer-Verlag, 2004, 482-495.
• [12] Pralong, B.: Implementation de la contrainte Regular en Comet, Master Thesis, École Polytechnique de Montreal, Canada, 2007.
• [13] Van Hentenryck, P., Michel, L.: Constraint-Based Local Search, The MIT Press, 2005.
• [14] Van Hentenryck, P., Michel, L.: Differentiable invariants, Proceedings of CP'06 (F. Benhamou, Ed.), LNCS 4204, Springer-Verlag, 2006, 604-619.
• [15] Van Hentenryck, P., Michel, L., Liu, L.: Constraint-based combinators for local search, Proceedings of CP'04 (M. Wallace, Ed.), LNCS 3258, Springer-Verlag, 2004, 47-61.
• [16] Van Hentenryck, P., Saraswat, V., Deville, Y.: Design, implementation, and evaluation of the constraint language cc(FD), Technical Report CS-93-02, Brown University, Providence, USA, January 1993.
• [17] Van Hoeve, W.-J., Pesant, G., Rousseau, L.-M.: On global warming: Flow-based soft global constraints, Journal of Heuristics, 12(4-5), September 2006, 347-373.
• [18] Van Hoeve, W.-J., Pesant, G., Rousseau, L.-M., Sabharwal, A.: Revisiting the sequence constraint, Proceedings of CP'06 (F. Benhamou, Ed.), LNCS 4204, Springer-Verlag, 2006, 620-634.
• [19] Vanhoucke, M., Maenhout, B.: On the characterization and generation of nurse scheduling problem instances, European Journal of Operational Research, 196(2), 2009, 457-467, NSPLib is at www.projectmanagement.ugent.be/nsp.php.
• [20] Zanarini, A., Pesant, G.: Solution counting algorithms for constraint-centered search heuristics, Constraints, 14(3), 2009, 392-413.