Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining
Abstract
Making good decisions at the top of a search tree is important for finding good solutions early in constraint optimization. In this paper, we propose a method employing frequent pattern mining (FPM), a classic datamining technique, to find good subtrees for solving constraint optimization problems. We demonstrate that applying FPM in a small number of random high-quality feasible solutions enables us to identify subtrees containing optimal solutions in more than 55% of problem instances for four real world benchmark problems. The method works as a plugin that can be combined with any search strategy for branch-and-bound search. Exploring the identified subtrees first, the method brings substantial improvements for four efficient search strategies in both total runtime and runtime of finding optimal solutions.
Cite
Text
Li et al. "Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I02.5518Markdown
[Li et al. "Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/li2020aaai-finding/) doi:10.1609/AAAI.V34I02.5518BibTeX
@inproceedings{li2020aaai-finding,
title = {{Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining}},
author = {Li, Hongbo and Lee, Jimmy and Mi, He and Yin, Minghao},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {1577-1584},
doi = {10.1609/AAAI.V34I02.5518},
url = {https://mlanthology.org/aaai/2020/li2020aaai-finding/}
}