nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Soft-Regular with a Prefix-Size Violation Measure

verfasst von : Minh Thanh Khong, Christophe Lecoutre, Pierre Schaus, Yves Deville

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose a variant of the global constraint soft-regular by introducing a new violation measure that relates a cost variable to the size of the longest prefix of the assigned variables, which is consistent with the constraint automaton. This measure allows us to guarantee that first decisions (assigned variables) respect the rules imposed by the automaton. We present a simple algorithm, based on a Multi-valued Decision Diagram (MDD), that enforces Generalized Arc Consistency (GAC). We provide an illustrative case study on nurse rostering, which shows the practical interest of our approach.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Horizontally Elastic Not-First/Not-Last Filtering Algorithm for Cumulative Resource Constraint

Nächstes Kapitel Constraint and Mathematical Programming Models for Integrated Port Container Terminal Operations

Régin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of AAAI 1994, pp. 362–367 (1994)

Beldiceanu, N., Contejean, E.: Introducing global constraints in CHIP. Math. Comput. Modell. 20(12), 97–123 (1994)CrossRef

Van Hentenryck, P., Carillon, J.-P.: Generality versus specificity: an experience with AI and OR techniques. In: Proceedings of AAAI 1988, pp. 660–664 (1988)

Régin, J.-C.: Generalized arc consistency for global cardinality constraint. In: Proceedings of AAAI 1996, pp. 209–215 (1996)

Hooker, J.N.: Integrated Methods for Optimization. Springer, Heidelberg (2012). https://doi.org/10.1007/978-1-4614-1900-6CrossRefMATH

Aggoun, A., Beldiceanu, N.: Extending chip in order to solve complex scheduling and placement problems. Math. Comput. Modell. 17(7), 57–73 (1993)CrossRef

Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 482–495. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30201-8_36CrossRefMATH

Schaus, P.: Variable objective large neighborhood search: a practical approach to solve over-constrained problems. In: 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 971–978. IEEE (2013)

van Hoeve, W.: Over-constrained problems. In: van Hentenryck, P., Milano, M. (eds.) Hybrid Optimization, pp. 191–225. Springer, New York (2011). https://doi.org/10.1007/978-1-4419-1644-0_6CrossRef

10.

Petit, T., Régin, J.-C., Bessière, C.: Specific filtering algorithms for over-constrained problems. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 451–463. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45578-7_31CrossRef

11.

van Hoeve, W., Pesant, G., Rousseau, L.-M.: On global warming: flow-based soft global constraints. J. Heuristics 12(4–5), 347–373 (2006)CrossRef

12.

He, J., Flener, P., Pearson, J.: Underestimating the cost of a soft constraint is dangerous: revisiting the edit-distance based soft regular constraint. J. Heuristics 19(5), 729–756 (2013)CrossRef

13.

He, J., Flener, P., Pearson, J.: An automaton constraint for local search. Fundamenta Informaticae 107(2–3), 223–248 (2011)MathSciNetMATH

14.

Montanari, U.: Network of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95–132 (1974)MathSciNetCrossRef

15.

Dechter, R.: Constraint Processing. Morgan Kaufmann, Burlington (2003)MATH

16.

Lecoutre, C.: Constraint Networks: Techniques and Algorithms. ISTE/Wiley, Hoboken (2009)CrossRef

17.

Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 107–122. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30201-8_11CrossRefMATH

18.

Hadzic, T., Hansen, E.R., O’Sullivan, B.: On automata, MDDs and BDDs in constraint satisfaction. In: Proceedings of ECAI 2008 Workshop on Inference methods based on Graphical Structures of Knowledge (2008)

19.

Cheng, K., Yap, R.: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15(2), 265–304 (2010)MathSciNetCrossRef

20.

Perez, G., Régin, J.-C.: Improving GAC-4 for table and MDD constraints. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 606–621. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10428-7_44CrossRef

21.

Perez, G., Régin, J.-C.: Soft and cost MDD propagators. In: Proceedings of AAAI 2017, pp. 3922–3928 (2017)

22.

Khong, M.T., Deville, Y., Schaus, P., Lecoutre, C.: Efficient reification of table constraints. In: 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE (2017)

23.

Burke, E., De Causmaecker, P., Berghe, G.V., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7(6), 441–499 (2004)MathSciNetCrossRef

24.

Ernst, A., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: a review of applications, methods and models. Eur. J. Oper. Res. 153(1), 3–27 (2004)MathSciNetCrossRef

25.

Curtois, T., Qu, R.: Computational results on new staff scheduling benchmark instances. Technical report, ASAP Research Group, School of Computer Science, University of Nottingham, 06 October 2014

26.

Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-49481-2_30CrossRef

Titel: Soft-Regular with a Prefix-Size Violation Measure
verfasst von: Minh Thanh Khong
Christophe Lecoutre
Pierre Schaus
Yves Deville
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-319-93030-5

Electronic ISBN: 978-3-319-93031-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93031-2_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"