Proceedings of the First International Conference on Artificial Intelligence, Smart Technologies and Communications (AISTC 2025)

<Previous Article In Volume
Next Article In Volume>

Enhancing Constraint Satisfaction Problem Solving with a Restart-Nogood-Based Approach

Authors
Fatima Ait Hatrit1, *, Kamal Amroun1
1University of Bejaia, Faculty of Exacts Sciences, Laboratory of Medical Informatics and Intelligent and Dynamic Environments (LIMED), 06000, Bejaia, Algeria
*Corresponding author. Email: fatima.aithatrit@univ-bejaia.dz
Corresponding Author
Fatima Ait Hatrit
Available Online 5 August 2025.
DOI
10.2991/978-94-6463-805-9_16How to use a DOI?
Keywords
Constraint Satisfaction Problems; n-ary Constraints; Backtracking; Nogood; Artificial Intelligence
Abstract

Efficiently solving Constraint Satisfaction Problems (CSPs) remains a major challenge in artificial intelligence and operations research. The complexity increases significantly for non-binary CSPs, where constraints involve multiple variables. Generalized Hypertree Decomposition (GHD) has proven to be an effective structural decomposition method for addressing these problems. However, the performance of GHD-based algorithms, such as Forward Checking-based GHD, heavily depends on the order in which clusters are processed. In this paper, we introduce a novel approach, the Nogood-Restart GHD (NG-RGHD) algorithm, which integrates a nogood mechanism with a restart technique triggered by dynamic backtrack thresholds to adaptively adjust the cluster processing order. Our experiments demonstrate that this approach significantly enhances computational performance and robustness.

Copyright
© 2025 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

<Previous Article In Volume
Next Article In Volume>
Volume Title
Proceedings of the First International Conference on Artificial Intelligence, Smart Technologies and Communications (AISTC 2025)
Series
Advances in Intelligent Systems Research
Publication Date
5 August 2025
ISBN
978-94-6463-805-9
ISSN
1951-6851
DOI
10.2991/978-94-6463-805-9_16How to use a DOI?
Copyright
© 2025 The Author(s)
Open Access
Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Cite this article

risenwbib
TY  - CONF
AU  - Fatima Ait Hatrit
AU  - Kamal Amroun
PY  - 2025
DA  - 2025/08/05
TI  - Enhancing Constraint Satisfaction Problem Solving with a Restart-Nogood-Based Approach
BT  - Proceedings of the First International Conference on Artificial Intelligence, Smart Technologies and Communications (AISTC 2025)
PB  - Atlantis Press
SP  - 141
EP  - 148
SN  - 1951-6851
UR  - https://doi.org/10.2991/978-94-6463-805-9_16
DO  - 10.2991/978-94-6463-805-9_16
ID  - Hatrit2025
ER  -