Prediction-Based Adaptive Variable Ordering Heuristics for Constraint Satisfaction Problems
Authors: Jitao Xu, Yaling Wu, Hongbo Li, Minghao Yin
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments show that the Long Short Term Memory model and Gradient Boosting Decision Tree models trained with the search trees sampled from easy instances are effective in identifying efficient VOHs for hard instances. The models capture some common structure properties hidden in the search trees of different problems. Our approach outperforms the state-of-the-art adaptive VOHs in terms of the number of solved instances and the PAR2 score of runtime. |
| Researcher Affiliation | Academia | Jitao Xu1,2, Yaling Wu1, Hongbo Li1*, Minghao Yin1 1College of Information Science and Technology, Northeast Normal Univerisity, Changchun, China. 2Department of Computer Science, Old Dominion University, Norfolk, Virginia 23508. EMAIL |
| Pseudocode | Yes | Algorithm 1: RECONSTRUCTION Input: An array seq storing an NPD sequence; Output: The topology of a binary search tree; 1 initialize a root node ROOT; 2 current Node ROOT; 3 for i = 0 to array.length 1 do 4 p seq[i]; 5 if p 1 then 6 for j = 1 to p do 7 generate the left branch of current Node; 8 if j < p then 9 current Node current Node.left Child; 10 mark current Node.left Child as a failure leaf; 11 generate the right branch of current Node; 12 current Node current Node.right Child; 14 mark current Node as a failure leaf; 15 while current Node is the right Child of its parent do 16 current Node current Node.parent; 17 mark current Node as an internal failure node; 18 generate the right brother of current Node; 19 current Node current Node.right Brother; 20 return the binary tree rooted at ROOT; |
| Open Source Code | Yes | The source codes and the trained models are available at https: //github.com/lihb905/pbavoh. |
| Open Datasets | Yes | To examine the performance of the proposed approach, we perform extensive experimentation with the Mini Zinc benchmark suite. ... Stuckey, P. J.; Feydy, T.; Schutt, A.; Tack, G.; and Fischer, J. 2014. The Mini Zinc Challenge 2008 2013. AI Magazine, 35(2): 55 60. |
| Dataset Splits | Yes | There are 937 easy instances solved during the probing phase and are used for the training task. They are randomly divided into the ones for training and validation with a ratio of 9:1. ... The All rows contain all involved instances, and the Hard contains 356 instances which are not solved in the probing phase and 25 more instances solved by AST and TSS. |
| Hardware Specification | Yes | The environment is JDK8 under Cent OS 6.4 with 4 Intel Xeon CPU E74820@2.00GHz processors (40 CPU cores in total). Each run is allocated with 1 CPU core and 1 GB RAM. ... It costs less than 30 minutes to train the LSTM model (the one used in Table 2, Table 3 and Table 5) with a single NVIDIA 3060 GPU with 12GB RAM. It costs less than 5 minutes to train the decision trees with one core of an i5-10400F @2.90GHz CPU. |
| Software Dependencies | Yes | The experiments3 were run in Choco solver (Prud homme, Fages, and Lorca 2017). The environment is JDK8 under Cent OS 6.4 with 4 Intel Xeon CPU E74820@2.00GHz processors (40 CPU cores in total). |
| Experiment Setup | Yes | The two approaches run the same probing procedure with round Limit = 100... The original label of each data point is the total failure number. We normalize original labels between 0 and 1. The labels of data points from each instance are grouped and normalized as follows, N(y) = S(y), y < P10 Zscore(y) < 1 1, y > P10 Zscore(y) 1 (5) where the P10 represents 10th percentile, and S(y) is a scaling function. ... In the experiments, we set max and min to 0.99 and 0 respectively. ... To prevent overfitting, we apply the dropout operator (Hinton et al. 2012) with a rate of 0.1 after a fully connected layer... We train the model by minimizing the binary crossentropy loss function (Cox 1958). This loss function is commonly used in binary classification tasks and measures the difference between the predicted probability distribution and the true probability distribution of binary outcomes. The calculation formula for binary cross-entropy loss is as follows: i=1 (p yi log(g(ˆy)) + (1 yi) log(1 g(ˆy))) where B denotes the batch size, yi is the label, g(ˆy) is the outputs of the model, and p is set to 0.1. |