TY - JOUR AU - Umetani, Shunji PY - 2015/02/16 Y2 - 2024/03/28 TI - Exploiting Variable Associations to Configure Efficient Local Search in Large-Scale Set Partitioning Problems JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: Heuristic Search and Optimization DO - 10.1609/aaai.v29i1.9366 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9366 SP - AB - <p> We present a data mining approach for reducing the search space of local search algorithms in large-scale set partitioning problems (SPPs). We construct a k-nearest neighbor graph by extracting variable associations from the instance to be solved, in order to identify promising pairs of flipping variables in the large neighborhood search. We incorporate the search space reduction technique into a 2-flip neighborhood local search algorithm with an efficient incremental evaluation of solutions and an adaptive control of penalty weights. We also develop a 4-flip neighborhood local search algorithm that flips four variables alternately along 4-paths or 4-cycles in the k-nearest neighbor graph. According to computational comparison with the latest solvers, our algorithm performs effectively for large-scale SPP instances with up to 2.57 million variables. </p> ER -