Enhancing the ACS Heuristic: Parameter Tuning and Computational Experiments for Solving MIP Problems

This thesis focuses on enhancing the Alternating Criteria Search (ACS) heuristic for solving large and complex Mixed Integer Programming (MIP) problems. While the Parallel ACS (PACS) approach has proven effective in generating high-quality solutions through large-scale parallelization, it remains limited by reliance on specialized hardware and by the need for manual parameter calibration. To overcome these issues, this work develops a refined PACS framework that adapts automatically to different problem instances and computing environments. The improvements center on a dynamic mechanism for adjusting the variable fixing strategy, a lightweight initialization method that avoids parameter tuning, and a reformulation of subproblems that leverages slack-based constraints for greater efficiency. Extensive computational experiments on hard instances from MIPLIB 2017 confirm that the refined PACS consistently achieves better solution quality than the baseline approach, while remaining robust, architecture-agnostic, and easy to integrate into modern MIP solvers.