Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

14. Constraint Programming

verfasst von : Eugene C. Freuder, Mark Wallace

Erschienen in: Search Methodologies

Verlag: Springer US

Einloggen

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

search-config
loading …

Abstract

Constraint satisfaction problems are ubiquitous. A simple example that we will use throughout the first half of this chapter is the following scheduling problem: Choose employees A or B for each of three tasks, X, Y, Z, subject to the work rules that the same employee cannot carry out both tasks X and Y, the same employee cannot carry out both tasks Y and Z, and only employee B is allowed to carry out task Z. (Many readers will recognize this as a simple coloring problem.)

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 Very Large-Scale Neighborhood Search
Nächstes Kapitel Multi-objective Optimization
Literatur
Amilhastre J, Fargier H, Marquis P (2002) Consistency restoration and explanations in dynamic CSPs—application to configuration. Artif Intell 135:199–234CrossRef
Bacchus F, Chen X, van Beek P, Walsh T (2002) Binary vs non-binary constraints. Artif Intell 140:1–37CrossRef
Bessière C, Régin J (2001) Refining the basic constraint propagation algorithm. In: Proc. 17th IJCAI, Seattle, pp 309–315
Bistarelli S, Fargier H, Montanari U, Rossi F, Schiex T, Verfaille G (1996) Semiring-based CSPs and valued CSPs: basic properties. In: Jampel M et al (eds) Over-constrained systems. LNCS 1106. Springer, Berlin, pp 111–150
Cheeseman P, Kanefsky B, Taylor W (1991) Where the really hard problems are. In: Proc. 12th IJCAI, Sydney. Morgan Kaufmann, San Mateo, pp 331–337
Cheng B, Choi K, Lee J, Wu J (1999) Increasing constraint propagation by redundant modeling: an experience report. Constraints 4:167–192CrossRef
Cohen C, Jeavons P, Jefferson C, Petrie K, Smith B (2006) Symmetry definitions for constraint satisfaction problems. Constraints 11:115–137CrossRef
Debruyne R, Bessière C (2001) Domain filtering consistencies. J Artif Intell Res 14:205–230
Dechter R (1990) Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition. Artif Intell 41:273–312CrossRef
Dechter R (2003) Constraint processing. Morgan Kaufmann, San Mateo
Dechter R, Dechter A (1988) Belief maintenance in dynamic constraint networks. In: Proc. 7th AAAI, Saint Paul, pp 37–42
Dechter R, Frost D (2002) Backjump-based backtracking for constraint satisfaction problems. Artif Intell 136:147–188CrossRef
Dechter R, Meiri I, Pearl J (1991) Temporal constraint networks. Artif Intell 49:61–95CrossRef
de Givry S, Jeannin L (2006) A unified framework for partial and hybrid search methods in constraint programming. Comput OR 33:2805–2833CrossRef
Deransart P, Hermenegildo M, Maluszynski J (eds) (2000) Analysis and visualization tools for constraint programming. LNCS 1870. Springer, Berlin
Fourer R, Gay DM, Kernighan BW (2002) AMPL: a modeling language for mathematical programming. Duxbury, Pacific Grove
Freuder E (1978) Synthesizing constraint expressions. Commun ACM 11:958–966CrossRef
Freuder E (1982) A sufficient condition for backtrack-free search. J Assoc Comput Mach 29:24–32CrossRef
Freuder E (1985) A sufficient condition for backtrack-bounded search. J Assoc Comput Mach 32:755–761CrossRef
Freuder E (1991) Eliminating interchangeable values in constraint satisfaction problems. In: Proc. 9th AAAI, Anaheim, pp 227–233
Freuder E, Wallace R (1992) Partial constraint satisfaction. Artif Intell 58:21–70CrossRef
Frisch A, Grum M, Jefferson C, Martinez M, Miguel I (2007) The design of ESSENCE: a constraint language for specifying combinatorial problems. In: Proc. 20th IJCAI, Hyderabad, pp 80–87
Gomes C, Selman B, Crato N (1997) Heavy-tailed distributions in combinatorial search. In: Principles and practice of constraint programming-CP97. LNCS 1330. Springer, Berlin
Harvey W, Ginsberg M (1995) Limited discrepancy search. In: Proc. 14th IJCAI 1995, Montreal, pp 607–615
Jaffar J, Lassez J-L (1987) Constraint logic programming. In: Proceedings of the annual ACM symposium on principles of programming languages, Munich. ACM, New York, pp 111–119
Jeavons P, Cooper M (1995) Tractable constraints on ordered domains. Artif Intell 79:327–339CrossRef
Junker U (2004) QUICKXPLAIN: preferred explanations and relaxations for over-constrained problems. In: Proc. 16th AAAI 2004, San Jose, pp 167–172
Katsirelos G, Bacchus F (2005) Generalized NoGoods in CSPs. In: Proceedings of the AAAI, Pittsburgh, pp 390–396
Kondrak G, van Beek P (1997) A theoretical evaluation of selected backtracking algorithms. Artif Intell 89:365–387CrossRef
Laburthe F, Caseau Y (1998) SALSA: a language for search algorithms. In: Proceedings of the 4th international conference on the principles and practice of constraint programming, Pisa, pp 310–324
Mackworth A (1977) Consistency in networks of relations. Artif Intell 8:99–118CrossRef
Marriott K, Nethercote N, Rafeh R, Stuckey PJ, Garcia de la Banda M, Wallace M (2008) The design of the Zinc modelling language. Constraints 13:229–267CrossRef
Minton S, Johnston MD, Philips AB, Laird P (1992) Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling. Artif Intell 58:161–205CrossRef
Nieuwenhuis R, Oliveras A, Tinelli C (2005) Abstract DPLL and abstract DPLL modulo theories. In: Logic for programming, artificial intelligence, and reasoning. LNCS 3452. Springer, Berlin, pp 36–50
O’Sullivan B (2010) Automated modelling and solving in constraint programming. In: Proceedings of the 24th National Conference on Artificial Intelligence, Atlanta, AAAI Palo Alto, pp 1493–1497
O’Sullivan B (2012) Opportunities and challenges for constraint programming. In: Proceedings of the 26th National Conference on Artificial Intelligence, Atlanta, Toronto, AAAI Palo Alto, pp 2148–2152
Refalo P (2004) Impact-based search strategies for constraint programming. In: Proceedings of the international conference on constraint programming (CP 2004), Toronto. LNCS 3258. Springer, Berlin, pp 557–571
Régin J-C (1994) A filtering algorithm for constraints of difference in CSPs. In: Proc. 12th AAAI, Seattle, pp 362–367
Régin J-C (2001) Minimization of the number of breaks in sports scheduling problems using constraint programming. In: Freuder E, Wallace R (eds) Constraint programming and large scale discrete optimization. DIMACS 57. AMS, Providence, pp 115–130
Sabin D, Freuder E (1997) Understanding and improving the MAC algorithm. In: Principles and practice of constraint programming—Proc CP 1997, Linz. LNCS 1330. Springer, Berlin, pp 167–181
Schrijvers T, Tack G, Wuille P, Samulowitz H, Stuckey PJ (2011) Search combinators. In: Proceedings of the international conference on constraint programming (CP 2011), Perugia. LNCS 6876. Springer, Berlin, pp 774–788
Selman B, Levesque H, Mitchell D (1992) A new method for solving hard satisfiability problems. In: Proc. 10th AAAI, San Jose, pp 440–446
Stuckey P (2010) Lazy clause generation: combining the power of SAT and CP (and MIP?) solving. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. LNCS 6140. Springer, Berlin, pp 5–9
Stuckey PJ, Garcia de la Banda M, Maher M, Marriott K, Slaney J, Somogyi Z, Wallace M, Walsh T (2005) The G12 project: mapping solver independent models to efficient solutions. Logic programming, 21st international conference. LNCS 3668. Springer, Berlin, pp 9–13
Tsang E (1993) Foundations of constraint satisfaction. Academic, London
Van Hentenryck P (1999) The OPL optimization programming language. MIT, Cambridge
Van Hentenryck P, Michel L (2009) Constraint-based local search. MIT, Cambridge
Van Hentenryck P, Simonis H, Dincbas M (1992) Constraint satisfaction using constraint logic programming. Artif Intell 58:113–159CrossRef
Walsh T (2002) Stochastic constraint programming. In: Proceedings of the ECAI-2002, Lyon. IOS, Amsterdam, pp 111–115
Walsh T (2012) Symmetry breaking constraints: recent results. In: Proc. 26th AAAI, Toronto, pp 2192–2198
Yokoo M, Durfee E, Ishida T, Kuwabara K (1998) The distributed CSP: formalization and algorithms. IEEE Trans Knowl Data Eng 10:673–685CrossRef
Metadaten
Titel
Constraint Programming
verfasst von
Eugene C. Freuder
Mark Wallace
Copyright-Jahr
2014
Verlag
Springer US
Buch
Search Methodologies

Print ISBN: 978-1-4614-6939-1

Electronic ISBN: 978-1-4614-6940-7

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-1-4614-6940-7_14