[4P2-OS-17b] OS-17

[4P2-OS-17b-05] An efficient weighting local search for large-scale binary integer programs

〇SHUNJI UMETANI¹ (1. Recruit Co., Ltd.)

Keywords:combinatorial optimization, integer program, metaheuristics

We present a data mining approach for reducing the search space of local search algorithms (LS) in large-scale binary integer programs (BIPs). Larger neighborhood search improves the quality of locally optimal solutions, while it also increases the computation time exponentially. To overcome this, many researchers have found useful features from the formulation of individual problems for efficient neighborhood search. However, due to the generality of BIPs, its formulation has few useful features for improving performance of algorithms.
We accordingly extract variable associations from the input datajust to be solved currently (not the problem formulation) in order to identify promising pairs of flipping variables simultaneously in the neighborhood search. Based on this, we develop a 4-flip neighborhood local search algorithm that incorporates an efficient incremental evaluiation 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.