Integer linear programming models a wide range of practical combinatorial
optimization problems and has significant impacts in industry and management
sectors. This work develops the first standalone local search solver for
general integer linear programming validated on a large heterogeneous problem
dataset. We propose a local search framework that switches in three modes,
namely Search, Improve, and Restore modes, and design tailored operators
adapted to different modes, thus improve the quality of the current solution
according to different situations. For the Search and Restore modes, we propose
an operator named tight move, which adaptively modifies variables' values
trying to make some constraint tight. For the Improve mode, an efficient
operator lift move is proposed to improve the quality of the objective function
while maintaining feasibility. Putting these together, we develop a local
search solver for integer linear programming called Local-ILP. Experiments
conducted on the MIPLIB dataset show the effectiveness of our solver in solving
large-scale hard integer linear programming problems within a reasonably short
time. Local-ILP is competitive and complementary to the state-of-the-art
commercial solver Gurobi and significantly outperforms the state-of-the-art
non-commercial solver SCIP. Moreover, our solver establishes new records for 6
MIPLIB open instances.

该论文开发了第一个独立的本地搜索模型，使用紧密移动和提升移动两种算子，解决了复杂的整数线性规划问题，并在 MIPLIB 数据集上实现了比市场上同类解决方案更好的结果。