Tailoring parallel alternating criteria search for domain specific MIPs: Application to maritime inventory routing

Abstract

Parallel Alternating Criteria Search (PACS) relies on the combination of computer parallelism and Large Neighborhood Searches to attempt to deliver high quality solutions to any generic Mixed-Integer Program (MIP) quickly. While general-purpose primal heuristics are widely used due to their universal application, they are usually outperformed by domain-specific heuristics when optimizing a particular problem class. In this paper, we focus on the fast development of domain-specific parallel primal heuristics. Our approach entails specializing PACS to better adapt to the target problem structure. We showcase its application to two classes of the Maritime Inventory Routing Problem, an important application of MIPs to real world problems. We computationally compare the proposed modified framework with state-of-the art specialized algorithms and MIP solvers. Results show the effectiveness of our approach, and how the modular nature of PACS can provide a platform for the rapid prototyping of parallel domain-specific heuristics.

Publication
Computers & Operations Research