2017年11月
Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
- 巻
- 263
- 号
- 1
- 開始ページ
- 72
- 終了ページ
- 81
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.ejor.2017.05.025
- 出版者・発行元
- ELSEVIER SCIENCE BV
We present a data mining approach for reducing the search space of local search algorithms in a class of binary integer programs including the set covering and partitioning problems. The quality of locally optimal solutions typically improves if a larger neighborhood is used, while the computation time of searching the neighborhood increases exponentially. To overcome this, we extract variable associations from the instance to be solved in order to identify promising pairs of flipping variables in the neighborhood search. Based on this, we develop a 4-flip neighborhood local search algorithm that incorporates an efficient incremental evaluation of solutions and an adaptive control of penalty weights. Computational results show that the proposed method improves the performance of the local search algorithm for large-scale set covering and partitioning problems. (C) 2017 The Author(s). Published by Elsevier B.V.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.ejor.2017.05.025
- ISSN : 0377-2217
- eISSN : 1872-6860
- Web of Science ID : WOS:000405157300006