Exploiting Variable Associations to Configure Efficient Local Search in Large-Scale Set Partitioning Problems

Authors

  • Shunji Umetani Osaka University

DOI:

https://doi.org/10.1609/aaai.v29i1.9366

Keywords:

local search, set partitioning problem

Abstract

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.

Downloads

Published

2015-02-16

How to Cite

Umetani, S. (2015). Exploiting Variable Associations to Configure Efficient Local Search in Large-Scale Set Partitioning Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9366

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization