Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining
Authors: Hongbo Li, Jimmy Lee, He Mi, Minghao Yin1577-1584
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We have tested FPMS on the Uncapacitated Warehouse Location Problem (Uncap WLP), the Multidimensional-Knapsack Problem (MKnap), the Traveling Tournament Problem with Predefined Venues (TTPPV) and the Traveling Salesman Problem (TSP). The results show that the method finds the subtrees involving optimal solutions in more than 55% of problem instances for four real world benchmark problems. |
| Researcher Affiliation | Academia | Hongbo Li,1 Jimmy H.M. Lee,2 He Mi,1 Minghao Yin1* 1School of Information Science and Technology, Northeast Normal University, Changchun, China {lihb905, mih221, ymh}@nenu.edu.cn 2Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong jlee@cse.cuhk.edu.hk |
| Pseudocode | Yes | Algorithm 1: FPMS; Algorithm 2: GENERATESUBTREE(top FPs); Algorithm 3: SEARCHSTRATEGY(subtree, heu) |
| Open Source Code | No | The paper does not contain any statement about releasing the source code for the methodology described, nor does it provide a link to a code repository. |
| Open Datasets | Yes | Uncap WLP: the 15 instances from OR-Library2. [...] MKnap: the 55 instances of mknap1 and mknap2 from OR-Library. [...] TTPPV: the balanced 8-team instances under the 5 predefined venues from CSPLib3. [...] TSP: the 15 instances are real world problems from TSPLib5. |
| Dataset Splits | No | The paper mentions the use of various benchmark datasets (OR-Library, CSPLib, TSPLib) but does not provide explicit details on how these datasets were split into training, validation, or test sets for their experiments, nor does it specify exact percentages or sample counts for such splits. |
| Hardware Specification | Yes | The environment is JDK8 under Cent OS 6.4 with Intel Xeon CPU E7-4820@2.00GHz processor and 58 GB RAM. |
| Software Dependencies | Yes | The experiments were run in Choco 4.10 (Prud homme, Fages, and Lorca 2017). |
| Experiment Setup | Yes | Given d the maximum domain size of decision variables, the number m of solutions in Tr% is set to 20d. The initial support threshold is set to 20. To avoid some lucky patterns being frequent, the minimum support threshold is set to 3. To make the found frequent patterns having suitable basic scores (useful lengths and sufficient supports), the max length is set to 5 and the min length of frequent patterns is set to 3 (or 2 if the number of variables in less than 20). Timeout of total runtime is 1 hour and timeout of MINING procedure is 1 minute. If the mining is timeout, it returns the best found frequent patterns so far. If not specified, the random seed is 0. |