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

Lluís Miquel Munguía, Shabbir Ahmed, David A. Bader, George L. Nemhauser, Yufen Shao, Dimitri J. Papageorgiou

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)21-34
Number of pages14
JournalComputers and Operations Research
Volume111
DOIs
StatePublished - Nov 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Keywords

  • Discrete optimization
  • Large neighborhood search
  • Maritime inventory routing
  • Parallel computing
  • Primal heuristics

Fingerprint

Dive into the research topics of 'Tailoring parallel alternating criteria search for domain specific MIPs: Application to maritime inventory routing'. Together they form a unique fingerprint.

Cite this