|
Vol.14, No.3, August 2025. ISSN: 2217-8309 eISSN: 2217-8333
TEM Journal
TECHNOLOGY, EDUCATION, MANAGEMENT, INFORMATICS Association for Information Communication Technology Education and Science |
Learning When to Apply Diving Heuristics, Feasibility Pump and Cutting Planes in Mixed-Integer Linear Programming
Thiago Alcântara Luiz, Samuel Souza Brito, Haroldo Gambini Santos, Marcone Jamilson Freitas Souza, Túlio Ângelo Machado Toffolo
© 2025 Thiago Alcântara Luiz, published by UIKTEN. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. (CC BY-NC-ND 4.0)
Citation Information: TEM Journal. Volume 14, Issue 3, Pages 1948-1957, ISSN 2217-8309, DOI: 10.18421/TEM143-04, August 2025.
Received: 25 October 2024. Revised: 10 May 2025.
Abstract:
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.
Keywords – Diving heuristics, feasibility pump, cutting planes, machine learning, mixed-integer linear programming. |
|
----------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------- |