Learning When to Apply Diving Heuristics, Feasibility Pump and Cutting Planes in Mixed-Integer Linear Programming

Primal heuristics, such as diving heuristics, are fundamental to the performance of modern mixed-integer linear programming (MILP) solvers, playing an essential role in obtaining feasible integer solutions. However, the efficacy of these heuristics depends on the characteristics of the MILP problem solved. To assist solvers in selecting the best heuristics, a recommendation system based on machine learning is proposed. According to the characteristics of the problem, the system recommends which diving heuristic to use and whether it should be combined with feasibility pump and/or cutting planes. To train the model, a dataset was built from 320 optimization problems using 207 features and evaluated using a hybrid diving heuristic approach that enables combining feasibility pump and cutting planes to produce feasible solutions. Computational results show that the recommendation system leads to producing feasible solutions for 87% of the possible cases. This is equivalent to 10% more problem instances than the best diving heuristic combined with feasibility pump and cutting planes, requiring only 52.7% of the runtime.