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
Neural Computing and Applications
Erschienen in: Neural Computing and Applications 1/2019

03.05.2017 | Original Article

Saving constraint checks in maintaining coarse-grained generalized arc consistency

Erschienen in: Neural Computing and Applications | Sonderheft 1/2019

Einloggen

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

search-config
loading …

Abstract

Constraint check plays a central role in establishing generalized arc consistency which is widely used to solve constraint satisfaction problems. In this paper, we propose a new generalized arc consistency algorithm, called GTR, which ensures that the tuples that have been checked to be allowed by a constraint will never be checked again. For each constraint, GTR maintains a dynamic list of the tuples that were checked to be allowed by this constraint and check their validities to identify some values with supports. It is equipped with a mechanism avoiding redundant validity checks. The basic GAC3 algorithm is employed to find a support for the rest values and to add new tuples to the dynamic list. The experiments show that maintaining GTR during search saves a number of constraint checks. It also brings some improvements over cpu time while solving some CSPs with tight constraints.
Vorheriger Artikel New approaches in metaheuristics to solve the fixed charge transportation problem in a fuzzy environment
Nächster Artikel Differential evolution-based efficient multi-objective optimal power flow

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

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

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+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
Fußnoten
Literatur
1.
Bessière C (1994) Arc-consistency and arc-consistency again. Artif Intell 65:179–190CrossRef
2.
Bessière C, Fargier H, Lecoutre C (2013) Global inverse consistency for interactive constraint satisfaction Proceedings of CP’13, pp 159–174
3.
Bessière C, Freuder EC, Régin JC (1999) Using constraint metaknowledge to reduce arc consistency computation. Artif Intell 107:125–148MathSciNetCrossRefMATH
4.
Bessière C, Régin JC (1997) Arc consistency for general constraint networks: preliminary results Proceedings of IJCAI’97, pp 398–404
5.
Bessière C, Régin JC, Yap R, Zhang Y (2005) An optimal coarse-grained arc consistency algorithm. Artif Intell 165:165–185MathSciNetCrossRefMATH
6.
Boussemart F, Hemery F, Lecoutre C, Sais L (2004) Boosting systematic search by weighting constraints Proceedings of ECAI’04, pp 146–150
7.
Gomes C, Selman B, Kautz H (1998) Boosting combinatorial search through randomization Proceedings of AAAI’98, pp 431–437
8.
9.
Lecoutre C, Boussemart F, Hemery F (2003) Exploiting multidirectionality in coarsegrained arc consistency algorithms Proceedings of CP’03, pp 480–494
10.
Lecoutre C, Hemery F (2007) A study of residual supports in arc consistency Proceedings of IJCAI’07, pp 125–130
11.
Lecoutre C, Likitvivatanavong C, Shannon S, Yap R, Zhang Y (2008) Maintaining arc consistency with multiple residues. Constraint Program Lett 2:3–19
12.
13.
Li H, Liang Y, Guo J, Li Z (2013) Making simple tabular reduction works on negative table constraints Proceedings of AAAI’13, pp 1629–1630
14.
Likitvivatanavong C, Zhang Y, Bowen J, Freuder EC (2004) Arc consistency in MAC a new perspective Proceedings of CPAI’04 workshop held with CP’04, pp 93–107
15.
Likitvivatanavong C, Zhang Y, Shannon C, Bowen J, Freuder EC (2007) Arc consistency during search Proceedings of IJCAI’07, pp 137–142
16.
17.
Mohr R, Henderson TC (1986) Arc and path consistency revisited. Artif Intell 28:225–233CrossRef
18.
Sabin D, Freuder EC (1994) Contradicting conventional wisdom in constraint satisfaction Proceedings of ECAI’94, pp 125–129
19.
20.
van Dongen MRC (2004) Saving support-checks does not always save time. Artif Intell Rev 21:317–334
21.
Wang R, Xia W, Yap R, Li Z (2016) Optimizing simple table reduction with bitwise representation Proceedings of IJCAI’16, pp 787–793
22.
Walsh T (1999) Search in a small world Proceedings of IJCAI’99, pp 1172–1177
Metadaten
Titel
Saving constraint checks in maintaining coarse-grained generalized arc consistency
Publikationsdatum
03.05.2017
Erschienen in
Neural Computing and Applications / Ausgabe Sonderheft 1/2019
Print ISSN: 0941-0643
Elektronische ISSN: 1433-3058
DOI
https://doi.org/10.1007/s00521-017-3015-7

Weitere Artikel der Sonderheft 1/2019

Neural Computing and Applications 1/2019 Zur Ausgabe

S.I. : Machine Learning Applications for Self-Organized Wireless Networks

Video crowd detection and abnormal behavior model detection based on machine learning method

S.I. : Machine Learning Applications for Self-Organized Wireless Networks

A neural computing approach to the construction of information credibility assessments for online social networks

S.I. : Machine Learning Applications for Self-Organized Wireless Networks

Robust object tracking with the inverse relocation strategy

Original Article

Probabilistic soft sets and dual probabilistic soft sets in decision-making

S.I. : Machine Learning Applications for Self-Organized Wireless Networks

Research on mining collaborative behaviour patterns of dynamic supply chain network from the perspective of big data

Machine Learning Applications for Self-Organized Wireless Networks

Research on data fusion of multi-sensors based on fuzzy preference relations