Solving non-binary constraint satisfaction problems using GHD and restart.
The non-binary instances of the Constraint Satisfaction Problem (CSP) could be efficiently solved if their constraint hypergraphs have small generalized hypertree widths. Several algorithms based on Generalized Hypertree Decomposition (GHD) have been proposed in the literature to solve instances of...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Technology and Education Galileo da Amazônia
2025-01-01
|
| Series: | ITEGAM-JETIA |
| Online Access: | http://itegam-jetia.org/journal/index.php/jetia/article/view/1415 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825207053587578880 |
|---|---|
| author | Fatima AIT HATRIT Kamal AMROUN, Professor |
| author_facet | Fatima AIT HATRIT Kamal AMROUN, Professor |
| author_sort | Fatima AIT HATRIT |
| collection | DOAJ |
| description |
The non-binary instances of the Constraint Satisfaction Problem (CSP) could be efficiently solved if their constraint hypergraphs have small generalized hypertree widths. Several algorithms based on Generalized Hypertree Decomposition (GHD) have been proposed in the literature to solve instances of CSPs. One of these algorithms, called Forward Checking based on Generalized Hypertree Decomposition (FC-GHD+NG+DR), combines the advantages of an enumerative search algorithm with those of Generalized Hypertree Decomposition. However, like all structural decomposition methods, FC-GHD+NG+DR depends on the order in which the clusters are processed. In this paper, we propose a new version of the FC-GHD+NG+DR algorithm with a restart technique that allows changing the order of the nodes of GHD to improve performance. The experiments carried out are very promising, particularly on the satisfiable instances where we achieved better results using the restart method in 52.63% of the modified Renault satisfiable benchmarks and an average time resolution of for the normalized Pret and normalized Dubois benchmarks.
|
| format | Article |
| id | doaj-art-cf45ff0723c54d00bf389df7fabc823c |
| institution | Kabale University |
| issn | 2447-0228 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Institute of Technology and Education Galileo da Amazônia |
| record_format | Article |
| series | ITEGAM-JETIA |
| spelling | doaj-art-cf45ff0723c54d00bf389df7fabc823c2025-02-06T23:51:51ZengInstitute of Technology and Education Galileo da AmazôniaITEGAM-JETIA2447-02282025-01-01115110.5935/jetia.v11i51.1415Solving non-binary constraint satisfaction problems using GHD and restart.Fatima AIT HATRIT0Kamal AMROUN, Professor1Université de Bejaia, Faculté des Sciences Exactes, Laboratoire d'Informatique Médicale et des Environnements Dynamiques et intelligents (LIMED)Université de Bejaia, Faculté des Sciences Exactes, Laboratoire d'Informatique Médicale et des Environnements Dynamiques et intelligents (LIMED), 06000 Bejaia, Algérie. The non-binary instances of the Constraint Satisfaction Problem (CSP) could be efficiently solved if their constraint hypergraphs have small generalized hypertree widths. Several algorithms based on Generalized Hypertree Decomposition (GHD) have been proposed in the literature to solve instances of CSPs. One of these algorithms, called Forward Checking based on Generalized Hypertree Decomposition (FC-GHD+NG+DR), combines the advantages of an enumerative search algorithm with those of Generalized Hypertree Decomposition. However, like all structural decomposition methods, FC-GHD+NG+DR depends on the order in which the clusters are processed. In this paper, we propose a new version of the FC-GHD+NG+DR algorithm with a restart technique that allows changing the order of the nodes of GHD to improve performance. The experiments carried out are very promising, particularly on the satisfiable instances where we achieved better results using the restart method in 52.63% of the modified Renault satisfiable benchmarks and an average time resolution of for the normalized Pret and normalized Dubois benchmarks. http://itegam-jetia.org/journal/index.php/jetia/article/view/1415 |
| spellingShingle | Fatima AIT HATRIT Kamal AMROUN, Professor Solving non-binary constraint satisfaction problems using GHD and restart. ITEGAM-JETIA |
| title | Solving non-binary constraint satisfaction problems using GHD and restart. |
| title_full | Solving non-binary constraint satisfaction problems using GHD and restart. |
| title_fullStr | Solving non-binary constraint satisfaction problems using GHD and restart. |
| title_full_unstemmed | Solving non-binary constraint satisfaction problems using GHD and restart. |
| title_short | Solving non-binary constraint satisfaction problems using GHD and restart. |
| title_sort | solving non binary constraint satisfaction problems using ghd and restart |
| url | http://itegam-jetia.org/journal/index.php/jetia/article/view/1415 |
| work_keys_str_mv | AT fatimaaithatrit solvingnonbinaryconstraintsatisfactionproblemsusingghdandrestart AT kamalamrounprofessor solvingnonbinaryconstraintsatisfactionproblemsusingghdandrestart |