Please use this identifier to cite or link to this item:
Title: Learning variable ordering heuristics for solving constraint satisfaction problems
Authors: Song, Wen
Cao, Zhiguang
Zhang, Jie
Xu, Chi
Lim, Andrew
Keywords: Engineering::Computer science and engineering
Issue Date: 2022
Source: Song, W., Cao, Z., Zhang, J., Xu, C. & Lim, A. (2022). Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, 109, 104603-.
Project: A19C1a0018 
Journal: Engineering Applications of Artificial Intelligence
Abstract: Backtracking search algorithms are often used to solve the Constraint Satisfaction Problem (CSP), which is widely applied in various domains such as automated planning and scheduling. The efficiency of backtracking search depends greatly on the variable ordering heuristics. Currently, the most commonly used heuristics are hand-crafted based on expert knowledge. In this paper, we propose a deep reinforcement learning based approach to automatically discover new variable ordering heuristics that are better adapted for a given class of CSP instances, without the need of relying on hand-crafted features and heuristics. We show that directly optimizing the search tree size is not convenient for learning, and propose to optimize the expected cost of reaching a leaf node in the search tree. To capture the complex relations among the variables and constraints, we design a representation scheme based on Graph Neural Network that can process CSP instances with different sizes and constraint arities. Experimental results on random CSP instances show that on small and medium sized instances, the learned policies outperform classical hand-crafted heuristics with smaller search tree (up to 10.36% reduction). Moreover, without further training, our policies directly generalize to instances of larger sizes and much harder to solve than those in training, with even larger reduction in the search tree size (up to 18.74%).
ISSN: 0952-1976
DOI: 10.1016/j.engappai.2021.104603
Rights: © 2021 Elsevier Ltd. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Nov 30, 2022

Web of ScienceTM
Citations 50

Updated on Nov 26, 2022

Page view(s)

Updated on Dec 3, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.